Adding waypoints to A* graph search

I have the ability to calculate the best route between a start and end point using A*. Right now, I am including waypoints between my start and end points by applying A* to the pairs in all permutations of my points.

Example:

I want to get from point 1 to point 4. Additionally, I want to pass through points 2 and 3.

I calculate the permutations of (1, 2, 3, 4):

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 开发者_如何学JAVA3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Then, for each permutation, I calculate the A* route from the first to the second, then append it to the route from the second to the third, then the third to the fourth.

When I have this calculated for each permutation, I sort the routes by distance and return the shortest.

Obviously, this works but involves a lot of calculation and totally collapses when I have 6 waypoints (permutations of 8 items is 40320 :-))

Is there a better way to do this?

First of all, you should store all intermediate calculations. Once you calculated the route from 1 to 2, you should never recalculate it again, just look up in a table. Second, if your graph is undirected, a route from 2 to 1 has exactly the same distance as a route from 1 to 2, so you should not recalculate it either.

And finally, in any case you will have an algorithm that is exponential to the number of points you need to pass. This is very similar to the traveling salesman problem, and it will be exactly this problem if you include all available points. The problem is NP-complete, i.e. it has complexity, exponential to the number of waypoints.

So if you have a lot of points that you must pass, exponential collapse is inevitable.

As a previous answer mentioned, this problem is the NP-complete Traveling Salesperson Problem.

There is a better method than the one you use. The state-of-the-art TSP solver is due to Georgia Tech's Concorde solver. If you can't simply use their freely available program in your own or use their API, I can describe the basic techniques they use.

To solve the TSP, they start with a greedy heuristic called the Lin-Kernighan heuristic to generate an upper bound. Then they use branch-and-cut on a mixed integer programming formulation of the TSP. This means they write a series of linear and integer constraints which, when solved, gives you the optimal path of the TSP. Their inner loop calls a linear programming solver such as Qsopt or Cplex to get a lower bound.

As I mentioned, this is the state-of-the-art so if you're looking for a better way to solve the TSP than what you're doing, here is the best. They can handle over 10,000 cities in a few seconds, especially on the symmmetric, planar TSP (which I suspect is the variant you're working on).

If the number of waypoints you need to eventually handle is small, say on the order of 10 to 15, then you may be able to do a branch-and-bound search using the minimum spanning tree heuristic. This is a textbook exercise in many introductory AI courses. More waypoints than that you will probably outlive the actual running time of the algorithm, and you will have to use Concorde instead.