我正在研究图形搜索算法(为了这个问题,让我们只在 DFS、BreadthFS、ID 上限制算法)。
所有这些算法都可以实现为前向搜索(从开始节点到结束节点)或向后搜索(从结束节点到开始节点)。
我的问题是,什么时候后向搜索会比前向搜索更好?对此有一般规则吗?
我正在研究图形搜索算法(为了这个问题,让我们只在 DFS、BreadthFS、ID 上限制算法)。
所有这些算法都可以实现为前向搜索(从开始节点到结束节点)或向后搜索(从结束节点到开始节点)。
我的问题是,什么时候后向搜索会比前向搜索更好?对此有一般规则吗?
通过广度优先搜索或迭代深化,我认为您问题的数学答案涉及顶点周围“球”的概念。定义 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 实现,编码也不是那么难。
至于深度优先搜索,我实际上不知道确定哪个更快的好方法,因为在最坏的情况下,两种搜索都可以在找到路径之前探索整个图。如果有人对如何确定哪个更好有很好的解释,那么如果他们能发布它会很棒。