algorithm - 探索网格并找到旗帜的最快方式

Question

我有一个带有块形式障碍物的 nxn 网格。我需要从一个随机点开始在这个网格的某个地方找到一个标志。您可以向左、向右或向前/向后移动。

在网格中的每个点，您都有关于您的四个块（上、下、左、右）的信息。BFS 似乎是一个很好的解决方案。但这让我想知道是否有更快或更好的探索算法？

任何想法将不胜感激。

Answer 1

BFS 确实是您需要的算法。作为额外的好处，您会发现越过标志的单元格的最短路径。另请注意，您不需要以任何“常规方式”存储整个图形，在这种情况下，网格足以表示图形本身。我的许多学生都无法理解这一点。

Answer 2

这似乎是网格上的正常探索问题。如果您使用 BFS，那么您会找到距离 <= 起点和标志之间距离的所有点。

但是，我建议使用一些优化。

如果您知道标志的坐标（您的问题不清楚），您可以使用 A*。

如果您没有标志坐标，您可以尝试利用您从块中获得的信息。在方形网格上，BFS 创建圆形搜索前沿，这意味着您可以获得起点周围圆形区域内点的所有信息。这意味着您将评估该区域中的所有点。您可以尝试通过优先评估点来最大化您的探索，这些点可以为您提供有关图表的更多信息 = 具有许多未知邻居的点。

这将重定向您的搜索以尽快评估新点。找到标志后，您就有了距离的上限，您可以探索图形中可能改善界限的未知部分。您还可以在优先级函数中考虑到起点的距离，以避免搜索过远。优先功能中的平衡将取决于您的网格和障碍物的数量。