带步行代理的“最短路径”算法

Question

我正在寻找一种最短路径算法，其中代理（必须从起点移动到终点的东西）只能看到可行走区域的有限部分。假设我们有一个由瓷砖组成的迷宫，有一个起点和目标点。如下所示: 然后代理可能每个方向（上、下、左、右）只能看到一个格子，但他具有 无限的内存。我想以尽可能少的步骤到达目标作为度量标准。 是否有这样的算法呢？

如果有，那么是否有一种更一般的问题的算法？例如：一个图，多个目标和起点和返回已见节点的函数，并且内存受限？

一种使用总视野的 A* 算法的解决方案如下图所示：

- Xanlantos

Answer 1

一个非常简单的替代方法是：

walk to an undiscovered tile using a star
if it is the goal stop
if not repeat
if there aren't any undiscovered tiles stop and fail

- Torben Ammelt

Answer 2

过了一会儿，我脑海中浮现出一些想法和相似之处。

这与微型机器人需要解决的问题非常接近，大多数情况下使用泛洪填充算法。

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. ElseIf the color of node is not equal to target-color, return.
 3. Else Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

- Xanlantos

Answer 3

基本上，A*算法仍然有效，但您需要找到一个新的启发式方法，我建议您包括瓷砖之间的旅行时间来实现这一点。

- TorAmm

---

您应该更详细地解释您的答案，因为不清楚阅读此答案的人如何将其应用于解决问题。 - AlBlue

Answer 4

由于能见度受限，你不能指望找到最短路径，因为要么你可以看到通向目标的路径，要么你就看不到，除非你很幸运看到多条路径。

然而，你可以使用启发式算法来改善搜索。例如，你会想要探索未被探索的方块，优先考虑靠近目标的方块，从最近的方块开始。当能见度仅为1时，你基本上是盲目的，但如果你的能见度稍微高一点，你可以优先探索周围的目标，直到找到连接到你已经探索过的区域的路径。

这让我想起了双向路径追踪技术，它是渲染中一种在相机和光源之间追踪路径直到它们连接的技术。http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html

- frodo2975

---

除非您完全了解迷宫，否则无法确定最短路径。对于双向搜索，基本上您正在寻找连接目标和当前可见路径之一的路径，因此您可以优先从末尾或当前位置开始搜索。 - frodo2975

你错了，我不需要看整个迷宫，只需要看能够提供更短路径的部分。因此，A算法需要一个适当的启发式函数，例如哈密顿距离。而且找到的第一条路径也将是最短的路径。请仔细查看https://en.wikipedia.org/wiki/A_search_algorithm。你很难轻松地找到步数最少的路径。无论如何，这就是我要找的。 - Xanlantos

你不能真的期望找到最短路径，一个简单的广度优先路径搜索可以在没有完全了解迷宫的情况下找到最短路径。A*算法可以更高效地实现这一点。 - c0der

@c0der 你没有理解重点。由于它是一个行走代理，目标是减少步数，因此无法进行广度优先搜索。 - frodo2975

使用BFS找到“一个”解决方案是可以的，但通常不会使用最少的步骤。除非实验室是单一路径，但说实话，我们为什么要关心那种情况呢？DFS有更好的机会以最小的步骤找到目标，因为它可以在任何实验室中幸运地首先扩展最小的路径，在这种情况下，代理使用的步骤也将是最小的，但这种情况发生的可能性非常小。 - Xanlantos