How could we solve the TSP using a hill-climbing approach?


I will give you a basic idea of an approach.

The basic idea behind hill climbing algorithms is to find local neighbouring solutions to the current one and, eventually, replace the current one with one of these neighbouring solutions.

So, you first need to model your problem in a way such that you can find neighbouring solutions to the current solution (as efficiently as possible). But what is a solution to a TSP? It is a sequence of nodes (or vertices), such that the first node is equal to the last one (given that the travelling salesman needs to return to its initial position), no other vertex is repeated, and all vertices of the graph are included.

So, given a sequence of nodes $x_1, x_2, \dots, x_{n}, x_1$, how can you create a neighbouring solution that is valid, that is, there is not repeated vertex (apart from the initial and the last one) and all vertices are included?

Hint: recall that, in the case of TSP, we can assume that every node (or city) is connected to every other node.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.