无限网格中不可到达目标的星型算法提前停止

Question

我正在按照维基百科上的伪代码来实现具有优先队列的 A* 算法，以在 无限大网格 中找到从一个源到另一个目的地的最短路径。当目标无法到达时，问题就出来了，例如被墙包围（没有无限长的墙），算法不会停止，所以陷入无限循环。我的解决方案的直观想法是在搜索之前做一些预处理工作，例如根据源和目的地添加边界，或者检查目的地是否被包围（这并不容易）。对无法到达的提前停止有什么建议吗？谢谢。

Answer 1

只有当您知道起点和终点位于图表的不同部分时，您才能停止。假设您没有无限长的墙，只有当起点或终点被完全封闭时才会发生这种情况。但是检查它并不是微不足道的，因为你不知道什么时候停止检查。

如前所述，该问题似乎没有简单的解决方案。如果您可以提供有关您的设置的更多详细信息，您也许可以做更多的事情。例如，如果墙壁都是线段，那么您可以使用计算几何算法（角度扫描？）来查看一个点是否被墙壁包围。

Answer 2

只要你没有无限墙，你就可以运行从源头到目的地A*，同时从目的地到目的地运行A*资源。

如果目的地被墙包围，那么最终目的地->源A*将运行没有选择。

如果源被墙包围，那么最终源->目标 A* 将 运行 无选择。

否则他们会在某个时候见面的。每当发生这种情况时，您都可以使用一个的路径长度作为另一个的完美启发式。