我要计算使用A *一个起点和终点之间的最佳路径的能力。现在，我包括应用A *到对在我点的所有排列我的起点和终点之间的航点。

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.

例如：

我想从1点到4点。另外，我想通过点2和3。

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

余计算的排列（1，2，3，4）：

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

然后，对于每个排列，我计算A *从第一到第二路径，然后将其附加到路径从第二到第三，那么第三到第四

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.

显然，这工作，但涉及到大量的计算，完全倒塌时，我有6个航点（8个项目的排列是40320： - ））

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?

推荐答案

首先，你应该存储所有中间计算。一旦你计算出从1路线2，你永远不应该再重新计算，只要看看在一个表中。 第二，如果你是无向图，从2比1的路由具有完全相同的距离，从1到2的路线，所以你不应该重新计算它的。

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.

最后，在任何情况下，你将有一种算法，是指数到需要传递的点数。这是非常相似的旅行推销员问题，它会完全此问题，如果你包括所有可用的点。该问题是NP完全，也就是说，它具有复杂的，指数的航点的数目。

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.