5

I have the ability to calculate the best route between a start and end point using A*. Right now, I am including waypoints between my start and end points by applying A* to the pairs in all permutations of my points.

Example:

I want to get from point 1 to point 4. Additionally, I want to pass through points 2 and 3.

I calculate the permutations of (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

Then, for each permutation, I calculate the A* route from the first to the second, then append it to the route from the second to the third, then the third to the fourth.

When I have this calculated for each permutation, I sort the routes by distance and return the shortest.

Obviously, this works but involves a lot of calculation and totally collapses when I have 6 waypoints (permutations of 8 items is 40320 :-))

Is there a better way to do this?

4

2 回答 2

2

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

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

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

于 2010-06-18T20:30:23.673 回答
1

正如前面提到的答案，这个问题是 NP-complete Traveling Salesperson Problem。

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

为了解决 TSP，他们从称为 Lin-Kernighan 启发式的贪婪启发式开始，以生成上限。然后他们在 TSP 的混合整数规划公式上使用分支和切割。这意味着他们编写了一系列线性和整数约束，解决这些约束后，将为您提供 TSP 的最佳路径。它们的内部循环调用线性规划求解器（例如 Qsopt 或 Cplex）来获得下限。

正如我所提到的，这是最先进的，所以如果您正在寻找一种比您正在做的更好的解决 TSP 的方法，这里是最好的。他们可以在几秒钟内处理超过 10,000 个城市，尤其是在对称平面 TSP 上（我怀疑这是您正在研究的变体）。

如果您最终需要处理的路点数量很少，例如大约 10 到 15 个，那么您可以使用最小生成树启发式进行分支定界搜索。这是许多 AI 入门课程中的教科书练习。比这更多的航点可能会比算法的实际运行时间更长，您将不得不使用协和飞机。

于 2010-06-23T08:52:00.040 回答