在A*图搜索中添加航路点

Question

在A*图搜索中添加航路点

algorithmsearchroutesgrapha-star

5

我有能力使用A*算法计算起点和终点之间的最佳路径。目前，我在我的起点和终点之间加入航点，通过对所有点对应用A*算法来实现。

例如:

我想从点1到达点4，此外，我还想通过点2和点3。

我计算(1, 2, 3, 4)的排列组合：

然后，对于每个排列，我计算从第一个到第二个的A*路线，然后将其附加到从第二个到第三个的路线，再附加到第三个到第四个的路线。

当我对每个排列都这样计算完毕后，我按距离排序路线并返回最短路线。

显然，这种方法可行，但涉及大量计算，并且在有6个航点时完全崩溃（8个项目的排列是40320：-））

有更好的方法吗？

- klm902

1

为什么你要包含不以1开始且以4结束的路径呢？如果你有充分的理由这样做，并且你的地形是前后行进花费相同的情况下，你不必计算反向路径（1234和4321）。 - Justin L.

1

你只需要排列你必须经过的点。在你的情况下，你只需要尝试 1 -> 2 -> 3 -> 4 和 1 -> 3 -> 2 -> 4。 - IVlad

2个回答

1

正如之前的回答所提到的，这个问题是NP完全的旅行商问题。

有一种比你使用的更好的方法。最先进的TSP求解器归功于乔治亚理工学院的Concorde求解器。如果您不能简单地在自己的计算机上使用他们免费提供的程序或使用他们的API，则我可以描述他们使用的基本技术。

为了解决TSP，他们从贪婪启发式算法Lin-Kernighan启动以生成上界。然后他们在TSP的混合整数规划公式上使用分支定界。这意味着他们编写一系列线性和整数约束条件，当解决时，会给出TSP的最佳路径。他们的内循环调用线性规划求解器，例如Qsopt或Cplex，以获得下界。

正如我所提到的，这是最先进的技术，因此如果您正在寻找比您现在使用的更好的方法来解决TSP，那么这是最好的方法。他们可以在几秒钟内处理超过10,000个城市，特别是对于对称的、平面的TSP（我猜测这是您正在处理的变体）。

如果你最终需要处理的航点数量很少，比如大约10至15个，那么你可以尝试使用最小生成树启发式算法进行分支定界搜索。这是许多初级AI课程中的标准练习。如果航点数超过了这个范围，则算法的实际运行时间可能会超出你的寿命，此时你就需要使用Concorde算法来解决问题。

- Eric

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Degvik · Accepted Answer

首先，您应该存储所有中间计算。一旦您计算出从1到2的路径，就不应再次计算它，只需在表中查找即可。其次，如果您的图是无向的，则从2到1的路径与从1到2的路径具有完全相同的距离，因此您也不应再次计算它。最后，在任何情况下，您将拥有一个与需要通过的点数呈指数关系的算法。这非常类似于旅行商问题，如果包括所有可用点，则会恰好成为此问题。该问题是NP完全问题，即其复杂度与航路点数呈指数关系。因此，如果您必须经过许多点，则指数崩溃是不可避免的。