将航点添加到A *图搜索

我有能力使用A *计算起点和终点之间的最佳路线。现在，我在我的起点和终点之间加入了一个航点，通过将A *应用于我所有点的排列中。将航点添加到A *图搜索

实施例：

我想从点1至点4中。另外，我要通过点2和3

余计算的（1，2，3，4的排列）：

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

当我对每个排列进行计算时，我按距离排序路线并返回最短路线。

显然，这工作，但涉及到很多计算的，当我有6个航点完全倒塌（8项排列为40320 :-)）

有没有更好的方式来做到这一点？

来源

2010-06-18 klm902

为什么包含不以1开始并以4结尾的路径？而且，如果您有足够的理由这么做，如果您的地形是向前一个方向的成本与向后的成本相同，则不必计算反向路径（1234和4321） – 2010-06-18 20:30:58

您只需要排列你必须经过的点。在你的情况下，你只需要尝试1→2→3→4→1→3→2→4。 – IVlad 2010-06-18 20:36:11

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

最后，无论如何，你将有一个算法，指数的点数你需要通过。这与旅行商问题非常相似，如果包含所有可用点，则会出现这个问题。问题是NP完全的，即它具有复杂性，指向航点的数量。

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

来源

2010-06-18 20:30:23 Degvik

记忆FTW！ – 2010-06-18 20:33:41

您可以在旅行推销员问题上看到[维基百科文章]（http://en.wikipedia.org/wiki/Traveling_Salesman_Problem）。请注意，您可以尝试使用元启发式。我个人很喜欢实现[蚁群优化]（http://en.wikipedia.org/wiki/Ant_colony_optimization） – 2010-06-19 07:56:44

作为前面提到的答案，这个问题是NP完全旅行销售人员问题。

有一个比你使用的更好的方法。最先进的TSP解算器是由于Georgia Tech's Concorde solver。如果你不能简单地使用他们自己的免费程序或使用他们的API，我可以描述他们使用的基本技术。

为了解决TSP问题，他们从一个叫做Lin-Kernighan启发式的贪心启发式开始，生成一个上界。然后他们在TSP的混合整数规划公式中使用分支和剪切。这意味着他们编写了一系列线性和整数约束条件，这些约束条件在求解时为您提供了TSP的最佳路径。他们的内部循环调用线性规划解算器，如Qsopt或Cplex来获得下限。

正如我所说，这是最先进的，所以如果你正在寻找一种更好的解决TSP问题的方法，那么这里是最好的。他们可以在几秒钟内处理超过10,000个城市，特别是在对称的平面TSP上（我怀疑这是您正在开发的变体）。

如果您最终需要处理的航点的数量很少（例如10至15的数量级），那么您可以使用minimum spanning tree heuristic进行分支定界搜索。这是许多介绍性AI课程的教科书练习。更多的路点可能会超过该算法的实际运行时间，您将不得不使用Concorde。

来源

2010-06-23 08:52:00 Eric

将航点添加到A *图搜索

回答

相关问题