algorithm - 何时终止在无限网格中搜索路径

Question

我正在学习 Dijkstra 算法、BFS 等最短路径算法。我知道在二维有限网格上存在有助于终止算法并将其保持在特定范围/范围内的边界条件(即网格大小)。但是，当将其扩展到无限二维网格时，我不明白什么时候(比如使用 BFS 作为示例)得出结论，如果算法不无限运行，则简单路径不存在，因为我不能使用网格大小作为边界条件。在这些情况下是否可以使用某种公式？此外，请考虑到路径上也可能存在障碍物，因此路径距离可能会因不同的起点和目的地而异。

我考虑过尝试取坐标点之间差值的绝对值并将其提升到某个幂，作为在考虑路径一定不存在之前设置所采取步骤的上限的一种方法，但这种方法是直截了本地说显然是缺乏和不正确的，因为它在很多情况下都不起作用。

如果我的问题令人困惑，我深表歉意。我将在这里重申一下:基本上，我怎么知道何时假定无限二维网格中不存在从起点到终点的路径？

Answer 1

简而言之，您不需要。

这是一个更长的版本。假设我为您提供了一个程序，用于识别要切割网格中的哪些点，而您的工作是找出是否存在从 A 到 B 的路径。我可以轻松地为您提供一个程序 X，使得当且仅当程序 Y 最终停止时，路径才会存在。 (只要画一条长度为 2* 程序运行时间 Y + 1 的水平线，然后要求你从 (0, -1) 到 (0, 1)。)如果你能成功地编写你的程序，那么我们之间刚刚解决了the Halting Problem ，这是众所周知的不可能。