什么时候向后搜索比向前搜索更好？
我正在研究图搜索算法（为了这个问题，让我们仅将算法限制在 DFS、BreadthFS、ID 上）。
所有这些算法都可以实现为向前搜索（从起始节点到结束节点）或向后搜索（从结束节点到起始节点）。
我的问题是，向后搜索什么时候会比向前搜索表现更好？有一般规则吗？
I'm studying graph search algorithms (for this question sake, lets limit algorithms only on DFS, BreadthFS, ID).
All these algorithms can be implemented as either forward search (from start node to end node) or backward search (from end node to start node).
My question is, when will backward search perform better than forward? Is there a general rule for that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
通过广度优先搜索或迭代深化，我认为您问题的数学答案涉及顶点周围“球”的概念。定义 Ball(v, n) 为距节点 v 至多为 n 的节点集合，并令起始节点 s 到目标节点 t 的距离为 d。那么在最坏的情况下，如果|Ball(s, d)|，则向前搜索将比向后搜索执行得更好。 < |球(t, d)|。这是正确的，因为广度优先搜索（最坏情况下是 ID）总是在访问任何深度为 k + 1 的节点之前扩展出距起始节点一定距离 k 的所有节点。因此，如果周围的节点数量较少开始比目标向前搜索应该更快，而如果目标周围的节点数量比开始和向后搜索应该更快。不幸的是，很难预先知道这个数字。您通常必须运行搜索来确定是哪种情况。您可以使用两个节点周围的分支因子作为该值的启发式方法，但它不会不一定保证一次搜索会更快。
您可能想要考虑探索的一个有趣的算法是双向广度优先搜索，它同时进行搜索从源节点和目标节点。它往往比标准广度优先搜索快得多（特别是，使用分支因子 b 和节点之间的距离 d，BFS 大约需要 O(bd) 时间，而双向 BFS 需要 O （bd/2））。一旦有了良好的 BFS 实现，编写代码也不难。
至于深度优先搜索，我实际上不知道有什么好方法来确定哪个会更快，因为在最坏的情况下，两个搜索都可以在找到路径之前探索整个图。如果有人对如何确定哪个更好有一个很好的解释，那么他们可以发布它，那就太好了。
With a breadth-first search or iterative deepening, I think the mathematical answer to your question involves the notion of a "ball" around a vertex. Define Ball(v, n) to be the set of nodes at distance at most n from node v, and let the distance from the start node s to the destination node t be d. Then in the worst case a forward search will perform better than a backward search if |Ball(s, d)| < |Ball(t, d)|. This is true because breadth-first search always (and ID in the worst case) expands out all nodes of some distance k from the start node before ever visiting any nodes of depth k + 1. Consequently, if there's a smaller number of nodes around the start than the target a forward search should be faster, whereas if there's a smaller number of nodes around the target than the start and backward search should be faster. Unfortunately, it's hard to know this number a priori; you usually either have to run the search to determine which is the case. You could potentially use the branching factor around the two nodes as a heuristic for this value, but it wouldn't necessarily guarantee one search would be faster.
One interesting algorithm you might want to consider exploring is bidirectional breadth-first search, which does a search simultaneously from the source and target nodes. It tends to be much faster than the standard breadth-first search (in particular, with a branching factor b and distance d between the nodes, BFS takes roughly O(bd) time while bidirectional BFS takes O(bd/2)). It's also not that hard to code up once you have a good BFS implementation.
As for depth-first search, I actually don't know of a good way to determine which will be faster because in the worst-case both searches could explore the entire graph before finding a path. If someone has a good explanation about how to determine which will be better, it would be great if they could post it.