9

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?

Community
  • 1
  • 1
gruszczy
  • 40,948
  • 31
  • 128
  • 181
  • 1
    Nothing. I am not trying to develop anything, just trying to understand well, how A* is applied to real problems. – gruszczy Mar 17 '11 at 20:31
  • 1
    Are you sure it was A* or Generalized Adaptive A* which I imagine could be applied using a similar approach to the one described in larsmans answer. (see http://www.aamas-conference.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0026.pdf) – HasaniH Mar 17 '11 at 21:22
  • 2
    @Spaceghost - huh? "In this paper, we show how to do that, result- ing in Generalized Adaptive A* (GAA*) that finds shortest paths in state spaces where the action costs can increase or decrease over time." - what does this have to do with this problem? – dfb Mar 17 '11 at 21:56
  • 1
    By the way, someone found a solution in the duplicate question: http://stackoverflow.com/a/10247947/852592 – Lenar Hoyt Apr 25 '14 at 18:50
  • 1
    I m pretty sure this is a duplicate and so correctly marked as such. It would be nice to post the link to the original though as this was the first result on my google search... – ntg Nov 27 '18 at 16:54

4 Answers4

13

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..

dfb
  • 13,133
  • 2
  • 31
  • 52
  • 1
    +1, except that nodes should really be paths rather than sets of cities. See my answer for hints as to the heuristic. – Fred Foo Mar 17 '11 at 20:54
  • 4
    @larsmans - I'm not 100% sure here, but I disagree. Much like in a regular shortest path, how we get to node X and {nodes Y,Z and T} is irrelevant *to the rest of the path* whether we visited YZT or TZY, etc. We would , however, need to store the maximal value to reconstruct the path. The dynamic programming approach also suggests this is true, if we construct an algorithm TSP(node,visited) = min TSP(node2,visited+node) + cost(node,node2) over all node2 not in visited and memoize it, we have a solution that is o(2^n) rather than N! – dfb Mar 17 '11 at 20:58
  • 1
    yes, I think you're right. A (set,length) combination may be all the algorithm needs, which immediately gives you the necessary symmetry breaking. – Fred Foo Mar 17 '11 at 21:09
  • 1
    A possible heuristic would be the minimal spanning tree (MST) plus the length of the shortest edges connecting the MST to the already fixed segment. – Pedro Dusso Aug 02 '13 at 07:40
  • 1
    You do not really need a new graph for each step. Just to know the status of each node (visited/not visited), and what was your last move which means that for each state you need at least O(n) state, (still not insignificant...)... – ntg Nov 27 '18 at 16:55
9

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 1
    But how is this any different from Dijkstra's algorithm? Without a heuristic A* is no different from Dijkstra's algorithm. – John Leidegren Mar 17 '11 at 20:55
  • 1
    I did post a possible heuristic, or at least a sketch of it. The use of approximations to steer the A* algorithm into the right direction is a pretty common practice. – Fred Foo Mar 17 '11 at 20:56
  • 1
    Maybe I misunderstood but isn't the memory requirement for something like that huge? – John Leidegren Mar 17 '11 at 20:57
  • 1
    @larsmans - Didn't you just get the defintion of admissible heuristic wrong? From Wikipedia "a heuristic is admissible if it never overestimates the cost of reaching the goal". – John Leidegren Mar 17 '11 at 21:21
  • @John: typo, thanks! Forget what I said about memory cost. It's huge, but with @spinning_plate's suggestion of storing only sets of cities rather than routes and memoizing, I think its memory use is asymptotically equal to that the dynamic programming solution. There's a tradeoff between memory, time, and optimality here. – Fred Foo Mar 17 '11 at 21:31
  • 3
    An admissible heuristic would be the minimum distance from the last city added to the set to a city not already visited. Another (easily computed beforehand) would be the minimum distance from the last city added to any other city. – Ted Hopp Mar 18 '11 at 07:46
  • Could you comment on the consequences of trying to use A* with the graph of cities? Does it reduce to a simple greedy search with f(n) = g(n), because h(n) would be the same for any node in the graph given that all of the other nodes remain? – alwaysLearningABC May 11 '18 at 23:06
  • Edelkamp and Schrödl suggest to use minimal spanning trees as an admissible heuristik for TSP as clearly every TSP solution is also a spanning tree the weight of which cannot be higher than the weight of a minimal spanning tree. – fuz Mar 20 '19 at 15:48
5

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, ...

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
1

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.

Community
  • 1
  • 1
John Leidegren
  • 59,920
  • 20
  • 131
  • 152