TransWikia.com

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

Artificial Intelligence Asked by dua fatima on January 6, 2021

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

One Answer

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.

Correct answer by nbro on January 6, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP