将航点添加到 A* 图形搜索 [英] Adding waypoints to A* graph search

问题描述

我有能力使用 A* 计算起点和终点之间的最佳路线.现在，我通过将 A* 应用于点的所有排列中的对来包括起点和终点之间的航点.

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.

示例:

我想从第 1 点到达第 4 点.另外，我想通过第 2 点和第 3 点.

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

我计算 (1, 2, 3, 4) 的排列:

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

然后，对于每个排列，我计算从第一个到第二个的 A* 路由，然后将其附加到从第二个到第三个，然后是第三个到第四个的路由中.

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.

显然，这可行，但涉及大量计算，并且当我有 6 个航点时完全崩溃(8 个项目的排列为 40320 :-))

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?

推荐答案

首先，您应该存储所有中间计算.一旦你计算了从 1 到 2 的路线，你就不应该再重新计算它，只需在表格中查找即可.其次，如果你的图是无向图，从 2 到 1 的路线与从 1 到 2 的路线的距离完全相同，所以你也不应该重新计算它.

First of all, you should store all intermediate calculations. Once you calculated the route from 1 to 2, you should never recalculate it again, just look up in a table. Second, if your graph is undirected, a route from 2 to 1 has exactly the same distance as a route from 1 to 2, so you should not recalculate it either.

最后，在任何情况下，您都将拥有一个与您需要通过的点数呈指数关系的算法.这与旅行商问题非常相似，如果您将所有可用点都包括在内，这将正是这个问题.该问题是 NP 完全问题，即它具有复杂性，与航点数量呈指数关系.

And finally, in any case you will have an algorithm that is exponential to the number of points you need to pass. This is very similar to the traveling salesman problem, and it will be exactly this problem if you include all available points. The problem is NP-complete, i.e. it has complexity, exponential to the number of waypoints.

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

So if you have a lot of points that you must pass, exponential collapse is inevitable.

这篇关于将航点添加到 A* 图形搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！