如何在双向搜索中构建发现的路径

Question

我正在尝试在图中实现双向搜索。我正在使用“开始节点”和“目标节点”的两个广度首次搜索。已检查的状态存储在两个哈希表中（封闭列表）。当我发现其中一个搜索所检查的状态位于另一个搜索中时，我该如何获得解决方案（从开始到目标的路径）？

编辑

这是本书的解释：“双向搜索是通过对每个节点进行扩展之前检查它是否在另一个搜索树的边缘之前检查它是否在每个节点之前检查的双向搜索；如果是的，则找到了一个解决方案...在另一个搜索树中，可以用散布表进行恒定时间...”

以前有一些页面：“节点是用于表示搜索树的布尔克保存数据结构。一个状态对应于世界的配置……如果该状态是通过两个不同的搜索路径生成的，则两个不同的节点可以包含相同的世界状态。” 因此，我得出的结论是，如果将节点保存在哈希表中，那么从启动节点开始的BFS节点就不会匹配从目标节点启动的其他BFS构建的节点。

后来，在一般图形搜索算法中，状态存储在封闭列表中，而不是节点中，但在我看来，即使状态也保存在哈希表中，之后从那里检索了节点。

Answer 1

让我尝试这个问题。我不确定我是否确实了解它，所以我正在考虑发表评论，但最后，我更喜欢尝试解释。希望能帮助到你！

拉斐尔（Raphael）已经提出了一个解决方案（所以我投票给他的评论），即使您仅存储状态而不是节点。要明确说明：

• 状态: ：原始问题中的那些。这些是独一无二的
• 节点: ：通过您的搜索算法列举的那些（在您的情况下，双向广度优先搜索）。如您的书中所述”如果通过两个不同的搜索路径生成该状态，则两个不同的节点可以包含相同的世界状态“因此，很有可能有比州更多的节点（因为前者以不同的路径区分国家 - 可能是指数的 - 导致同一状态的状态）。

显然，从开始状态$ s $到目标$ t $的路径是通过将路径从$ s $到$ n $以及从$ n $到$ n $的路径来计算的，其中$ n $是找到的节点在相反搜索的哈希表中。

现在，假设您使用了一致的效果（启发式函数$ h（n）$在且仅当它满足三角形不平等$ h（n） leq c（n，m）时才保持一致（m）$ c（n，m）$是运营商的费用，从节点$ n $到其后代$ m $之一）或根本没有启发式功能（因此您的BFS是盲目的搜索）我建议以下程序：

让我假设WLG是$ n $是由远期搜索（即从开始状态$ s $）生成的，并且在向后搜索的哈希表中找到了它（即，从目标节点发出的）。在这种情况下，足以扩展节点$ n $并选择 任何 后代也出现在向后搜索的哈希表中。您可以在两个哈希表中存储所有状态（而不是节点），因此可以做到这一点。无论节点和状态之间的差异，如果您在向后搜索中生成$ n $（这是由于它存储在哈希表中的事实），它必须通过其父母之一来完成，现在可以恢复作为其后代之一（假设您正在穿越无向图，否则只需应用逆操作员来恢复父母）即可。这样的行动您最终将到达目标节点。

相同的机制适用于正向搜索---即，无需使用每个节点的路径到启动节点，只需将实现的封闭列表作为哈希表即可。反向上一段中获得的路径，将其串联，并且您有一个解决方案路径。

如果您不使用一致的启发式函数，则应沿着哈希表中的每个节点存储其值$ g（n）$ --- IE，从其相应的根节点（$ s $或$ t $。这样做，通过选择$ g $ value为$ g（n）-1 $的父（现在是继任者）的父（现在是继任者）来稍作修改。但是，如果您正在寻找（似乎）从$ s $到$ t $的任何路径，这甚至不是必需的。

双向搜索是启发式搜索中最有趣的“范式”之一。没有人找到一种简单的方式，使其像盲目搜索一样高效（显然是赢家）。

希望这可以帮助，

Answer 2

只需一个字典存储，每个节点都来自其中。因此，每次展开节点时，都会标记其所有邻居来自邻居来自节点的邻居。
例如面包屑[邻居] =节点

然后，当您达到目标时，您只需循环浏览字典回到开始即可。