最佳优先搜索，在未分配成本的网格上查找从起点到目标的路径。启发值

Question

我正在尝试回答这个挑战：

考虑在如图所示的网格中寻找从位置𝑠到位置𝑔的路径的问题：

一块可以在网格上水平或垂直移动，一次移动一格。任何台阶都不得进入禁止的阴影区域。

使用最佳优先搜索，节点从 𝑠 扩展到 𝑔。应使用曼哈顿距离作为评价函数。两点之间的曼哈顿距离是 𝑥 方向的距离加上 𝑦 方向的距离。它对应于沿网格排列的城市街道行驶的距离。假设多路径修剪。找到的第一条路径是什么？

我尝试了以下方法，但我不确定，因为没有给出启发式值：

如何确定找到的第一条路径是什么？

Answer 1

假设您指的是维基百科上描述的贪婪最佳优先搜索，您将达到以下状态：

在曼哈顿距离 3 和 2 寻找有希望的单元之后，我们无法进一步扩展距离 2 的单元：

距离最小的可扩展单元的距离为 3，并且向右扩展。之后，我们在距离 4 处有两个节点，它们扩展到它们的邻居，这三个节点在距离 5 处都是三个。然后这些节点被扩展，这给了我们这样的状态：

这里我们有一个距离为 4 的单元格，它比其他距离为 6 的单元格具有优先级。因此，我们将该节点扩展到两个距离为 5 的邻居。这两个单元现在是具有优先级的单元格，我们将它们扩展到三个新的单元格细胞：

我们再次得到一些距离为 6 的单元格，但有一个新的距离为 4 的单元格，因此它获得优先级，并扩展到距离为 5 的单元格。后一个单元格现在具有优先级并扩展到距离为 4 的单元格，哪个优先。此时很明显，我们永远不会扩展任何距离为 6 的节点，因为我们将在网格左侧扩展的新节点的距离都将具有更小的距离：

左侧距离为 4 的节点扩展为距离为 3 的单元格，获得优先级。它扩展到两个距离为 2 的单元格，获得优先级：

这两个单元格将扩展为两个单元格，包括“g”的左邻居。这取决于这 2 个单元扩展的顺序以及注册的路径。我在这里假设下面的 2 个单元将首先扩展：

现在已经找到了目标单元格，我们可以从每个涉及的单元格扩展的方向重建最短路径，沿着相反方向的箭头回到源单元格。所以我们得到了这条路径：

同样，从 3 到 2 的步骤也可以采用另一种方式。这取决于您未提供的信息：当单元格具有相同优先级时展开的顺序。

另请注意，网格右侧和底部的单元格没有进一步扩展，因为它们的优先级永远不够高。