将航点添加到A*图搜索

Question

我有能力使用A*计算起点和终点之间的最佳路线.现在,我通过在我的点的所有排列中对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 完全问题，即它具有复杂性，与路径点的数量呈指数关系。

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