How can the A* algorithm be applied to the traveling salesman problem? [duplicate]

Question

Possible Duplicate:
Using A* to solve Travelling Salesman Problem

I have recently learned that the A* algorithm can be applied to the travelling salesman problem. Bot how exactly do we define the start and the goal here, and how do we apply weights to nodes (what is the heuristic)?

Would someone explain to me how A* can be applied here?

Answer 1

A* is a derivative of Dijsktra, which I don't think can be used in this fashion. First, the TSP generally starts from any node. More importantly though, these algorithms seek to find the shortest path between two points, irrespective of the number of nodes visited. In fact, they depend on the fact that the shortest path from S to T via some node A, the path from S to A is irrelevant if it's the same cost.

The only way I see this functioning is if you generated a new graph representing nodes visited. For example, in your priority queue, you'd place the set of nodes visited and current node. This would lead to possibly examining $n2^n$ nodes (which is not coindientally the running time of the dynamic programming solution to the TSP http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM). So far, not great, but by using A* instead of Dijsktra, you might be able to find a heuristic that runs in a reasonable amount of time.

To implement this, your starting node would be (1,{}) and your ending node would be (1,{1..n}). You would mimic the edge weights of the original graph. As for suggestions on the heuristic, you're on your own..

Answer 2

A* can be applied here, though it might not be the best algorithm.

You'll have to step away from the graph of cities and roads between them. Instead, define a directed graph where partial routes are the nodes and two nodes x and y are connected iff y can be constructed from x by adding a single "step" in the original cities graph. The start node is an empty path. The goal node is a path through that visits all cities. (Optimality of this path is guaranteed by the properties of the heuristic and the A* algorithm itself.)

[EDIT: At first I thought a path should be an ordered list of cities, but I now believe @spinning_plate's suggestion of representing the path by a pair (length, set of cities) is enough.]

The path cost is the total distance travelled. The heuristic would have to be some admissible estimate (usually, an underestimate) of the total minimal travel length.

A good candidate for such an estimate might be a fast approximation of the TSP (the solution of a relaxed problem). You'd run the approximation algorithm for each node (partial route), on the set of cities not yet covered. That gives the algorithm the necessary upper bound on the distance the salesman still has to go.

Answer 3

If I have a hammer (A* search), every problem (TSP) is a nail (pathfinding).

Yes, in theory it's possible to transform the TSP problem into a much bigger graph and use A* search on it. But regrettably it's useless because it won't scale (see spinning_plate's comment). Even small instances might take years to solve that way on modern hardware.

TSP is NP-complete, pathfinding isn't.

If it's screw (NP complete problem), use a screwdriver (metaheurstics, ...).

Use algorithms such as metaheuristics (tabu search, genetic algorithms, simulated annealing, ...). For software examples, see Drools Planner, openTS, jgap, cpsolver, ...

Answer 4

A* is an extension of Dijkstra's algorithm where the optimal solution of traversing a directional graph is taken into account. I'm not sure this applies to the TSP problem.

The TSP problem states that you want to minimize the traveling distance while visiting each destination exactly once. The A* algorithm needs a heuristic to guide it's way where the optimal solution is known to be a straight line (you have to be careful with the A* heuristic to not overestimate the distance to the goal). This dose not apply to the TSP problem.

This question also contains information about the A* algorithm and TSP problem.