我能够使用 A* 计算起点和终点之间的最佳路线。现在，我通过将 A* 应用于我的点的所有排列中的对来包括起点和终点之间的航路点。
示例：
我想从点 1 到点 4。此外，我想通过点 2 和 3。
我计算 (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 * 从第一个到第二个的路线，然后将其附加到从第二个到第三个的路线，然后从第三个到第四个的路线。
当我为每个排列计算出这个值时，我会按距离对路线进行排序并返回最短的路线。
显然，这可行，但涉及大量计算，并且当我有 6 个路点时完全崩溃（8 个项目的排列是 40320 :-)）
是否有更好的方法来做到这一点？
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 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
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?
发布评论
评论（2）
首先，您应该存储所有中间计算。一旦计算出从 1 到 2 的路线，就不再需要重新计算，只需查表即可。
其次，如果您的图是无向的，则从 2 到 1 的路线与从 1 到 2 的路线具有完全相同的距离，因此您也不应该重新计算它。
最后，无论如何，您都会有一个与您需要通过的点数呈指数关系的算法。这与旅行商问题非常相似，如果包含所有可用点，则正是这个问题。该问题是 NP 完全问题，即它具有复杂性，与路径点的数量呈指数关系。
因此，如果你有很多必须通过的点，指数崩溃是不可避免的。
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.
正如之前的答案提到的，这个问题是NP完全旅行商问题。
有一种方法比您使用的方法更好。最先进的 TSP 求解器归功于佐治亚理工学院的 Concorde 求解器。如果您不能简单地在自己的程序中使用他们的免费程序或使用他们的 API，我可以描述他们使用的基本技术。
为了解决 TSP，他们从称为 Lin-Kernighan 启发式的贪婪启发式开始，以生成上限。然后他们在 TSP 的混合整数规划公式上使用分支剪切法。这意味着他们编写了一系列线性和整数约束，解决这些约束后，将为您提供 TSP 的最佳路径。它们的内部循环调用线性规划求解器（例如 Qsopt 或 Cplex）来获得下限。
正如我提到的，这是最先进的，因此如果您正在寻找比您正在做的更好的方法来解决 TSP，那么这里是最好的。他们可以在几秒钟内处理超过 10,000 个城市，尤其是在对称的平面 TSP 上（我怀疑这是您正在研究的变体）。
如果您最终需要处理的路点数量很少，例如 10 到 15 个，那么您可以使用 最小生成树启发式。这是许多人工智能入门课程中的教科书练习。更多的航路点可能会超过算法的实际运行时间，因此您将不得不使用协和式飞机。
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.