我正在研究图形搜索算法（为了这个问题，让我们只在 DFS、BreadthFS、ID 上限制算法）。
所有这些算法都可以实现为前向搜索（从开始节点到结束节点）或向后搜索（从结束节点到开始节点）。
我的问题是，什么时候后向搜索会比前向搜索更好？对此有一般规则吗？
问问题
3310 次
1 回答
2
通过广度优先搜索或迭代深化，我认为您问题的数学答案涉及顶点周围“球”的概念。定义 Ball(v, n) 为距离节点 v 最多为 n 的节点集合，令起始节点 s 到目的节点 t 的距离为 d。那么在最坏的情况下，如果 |Ball(s, d)|，前向搜索将比后向搜索执行得更好。< |球（t，d）|。这是真的，因为在访问深度为 k + 1 的任何节点之前，广度优先搜索始终（以及最坏情况下的 ID）扩展了距起始节点一定距离 k 的所有节点。因此，如果周围的节点数量较少start 比 target 前向搜索应该更快，而如果目标周围的节点数量少于 start 和后向搜索应该更快。不幸的是，很难先验地知道这个数字。您通常要么必须运行搜索来确定是哪种情况。您可能会使用围绕两个节点的分支因子作为该值的启发式，但不一定保证一次搜索会更快。
您可能要考虑探索的一个有趣算法是双向广度优先搜索，它同时从源节点和目标节点进行搜索。它往往比标准的广度优先搜索快得多（特别是，对于分支因子 b 和节点之间的距离 d，BFS 大约需要 O(b d ) 时间，而双向 BFS 需要 O(b d/2 )） . 一旦你有一个好的 BFS 实现，编码也不是那么难。
至于深度优先搜索，我实际上不知道确定哪个更快的好方法，因为在最坏的情况下，两种搜索都可以在找到路径之前探索整个图。如果有人对如何确定哪个更好有很好的解释，那么如果他们能发布它会很棒。
于 2011-02-08T19:52:56.463 回答