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

  • 2
    $\begingroup$ I am sure someone could help you if you present your understanding of the problem and showed where you are stuck. Otherwise, on the surface this looks like a coursework dump . . . please use edit to add details relevant to your attempts at solving this problem $\endgroup$ – Neil Slater Mar 29 '19 at 8:47

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.

| improve this answer | |

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.