Hamiltonian cycle and TSP: A backtracking approach

Abstract

Backtracking is one of the strategies to reduce the complexity of a problem. Backtracking mainly useful when there is a no solution by going forward in that direction so we required backtracking from it to reduce the complexity and save the time. Backtracking has ability to give same result in far fewer attempts than the exhaustive or brute force method trials. This paper gives the recursive algorithm for Hamiltonian cycle and TSP (travelling salesman problem) based on the backtracking approach. If at any stage it is detected that the particular input or combination will not lead to an optimal solution than we can discard and a new input can be selected.