带有传送器的网格上的 A* 可接受的启发式方法? [英] A* admissible heuristics on a grid with teleporters?

问题描述

假设您有一个 2D 单元格网格，其中一些被墙填充.角色可以从一个方格走一步到与其水平或垂直一步的任何方格，但不能跨墙.

Suppose that you have a 2D grid of cells, some of which are filled in with walls. Characters can take a step from one square to any square that is one step horizontal or vertical from it, but cannot cross walls.

给定一个开始位置和一个结束位置，我们可以通过使用具有可接受启发式的 A* 算法找到从开始位置到结束位置的最短路径.在当前设置中，曼哈顿距离是可以接受的，因为它永远不会高估到目的地的距离.

Given a start position and an end position, we can find the shortest path from the start position to the end position by using the A* algorithm with an admissible heuristic. In this current setup, the Manhattan distance would be admissible, since it never overestimates the distance to the destination.

现在假设除了墙壁之外，世界还有成对的传送器.踏上传送器会立即将角色传送到链接的传送器.传送器的存在打破了上面给出的可接受的启发式方法，因为通过使用传送器缩短距离，可能比采取最佳曼哈顿距离步行更快地到达目的地.例如，考虑这个线性世界，传送器标记为 T，起始位置标记为 S，结束位置标记为 E:

Now suppose that in addition to walls, the world has pairs of teleporters. Stepping onto a teleporter immediately transports a character to the linked teleporter. The existence of teleporters breaks the admissible heuristic given above, since it might be possible to get to the destination faster than taking the optimal Manhattan distance walk by using a teleporter to cut down on the distance. For example, consider this linear world with teleporters marked T, start position marked S, and end position marked E:

T . S . . . . . . . . . . . . . E . T

在这里，最好的路线是走到左边的传送门，然后向左走两步.

Here, the best route is to walk to the teleporter on the left, then take two steps to the left.

我的问题是:在具有传送器的网格世界中，对于 A* 来说，什么是好的可接受启发式?

谢谢！

推荐答案

形成传送器的图形:

• 每个传送器都有一个节点，终点位置有一个节点.
• 你有一条边将每个节点连接到其他节点，形成一个全连接图.
• 对于边权重，请使用每个节点的目标单元格(您进入传送器时到达的那个单元格)与所有其他节点之间的曼哈顿距离.

使用 Dijkstra 算法计算每个节点到终点的最短距离.

Use Dijkstra's algorithm to calculate the shortest distance from each node to the end.

您现在可以使用特定位置和所有节点之间的最小距离加上预先计算的从节点到末端的距离作为启发式函数.Dijkstra 算法只需作为预处理步骤运行一次.但是，如果传送器的数量占单元数量的很大百分比，则使用更简单的启发式函数可能无法获得任何好处.

You can now use the minimum of the distance between a particular position and all the nodes plus the pre-calculated distance from the node to the end as a heuristic function. Dijkstra's algorithm only has to be run once as a pre-processing step. However, if the number of teleporters is a large perecentage of the number of cells, you may not get any benefit over using a simpler heuristic function.

这篇关于带有传送器的网格上的 A* 可接受的启发式方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！