我可以使用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 :-)，它完全崩溃了
有一个更好的方法吗？
最佳答案
首先，您应该存储所有中间计算。一旦计算出从1到2的路线，就不再需要重新计算，只需在表中查找即可。
其次，如果您的图形是无向的，则从2到1的路线与从1到2的路线具有完全相同的距离，因此您也不应重新计算它。
最后，无论如何，您将拥有一种算法，该算法与您需要通过的点数成指数关系。这与旅行商问题非常相似，如果您包括所有可用积分，也将恰好是此问题。这个问题是NP完全的，即它的复杂性与航路点的数量成指数关系。
因此，如果您必须通过许多要点，则指数折叠是不可避免的。
关于algorithm - 将航路点添加到A *图形搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3072809/