algorithm - 将路标添加到 A* 图搜索

Question

我有能力使用 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 :-))

有更好的方法吗？

Answer 1

首先，您应该存储所有中间计算。一旦计算出从 1 到 2 的路线，就不要再重新计算它，只需查表即可。 其次，如果您的图形是无向的，则从 2 到 1 的路线与从 1 到 2 的路线的距离完全相同，因此您也不应该重新计算它。

最后，无论如何，您将拥有一个与您需要通过的点数成指数关系的算法。这与旅行商问题非常相似，如果您包括所有可用点，它就是这个问题。该问题是 NP 完全问题，即它具有复杂性，与路径点的数量成指数关系。

所以如果你有很多点必须通过，指数崩溃是不可避免的。