algorithm - 什么时候向后搜索比向前搜索更好？

Question

我正在研究图搜索算法(为了这个问题，让我们将算法限制在 DFS、BreadthFS、ID 上)。

所有这些算法都可以实现为正向搜索(从起始节点到结束节点)或反向搜索(从结束节点到起始节点)。

我的问题是，什么时候向后搜索会比向前搜索执行得更好？对此有一般规则吗？

Answer 1

通过广度优先搜索或迭代加深，我认为您问题的数学答案涉及顶点周围“球”的概念。定义 Ball(v, n) 为距节点 v 至多 n 处的节点集，设起始节点 s 到目的节点 t 的距离为 d。那么在最坏的情况下，如果 |Ball(s, d)|，则前向搜索将比向后搜索执行得更好。 < |球(t，d)|。这是真的，因为广度优先搜索总是(在最坏的情况下是 ID)在访问任何深度为 k + 1 的节点之前，从起始节点展开一段距离为 k 的所有节点。因此，如果周围的节点数量较少开始比目标向前搜索应该更快，而如果目标周围的节点数量少于开始和向后搜索应该更快。不幸的是，很难先验地知道这个数字。您通常要么必须运行搜索以确定是哪种情况。您可能会使用 branching factor围绕两个节点作为此值的启发式方法，但这不一定保证一次搜索会更快。

您可能想要考虑探索的一个有趣算法是 bidirectional breadth-first search ，它同时从源节点和目标节点进行搜索。它往往比标准广度优先搜索快得多(特别是，对于分支因子 b 和节点之间的距离 d，BFS 大约需要 O(b^d) 时间，而双向 BFS 需要 O (b^d/2))。一旦您拥有良好的 BFS 实现，编写代码也不难。

至于深度优先搜索，我实际上不知道有什么好方法可以确定哪个更快，因为在最坏的情况下，两种搜索都可以在找到路径之前探索整个图。如果有人对如何确定哪个会更好有很好的解释，如果他们能发布它就太好了。