我了解 DFS 和 BFS 之间的区别,但我很想知道什么时候使用其中一种比另一种更实用?
有人能举例说明 DFS 如何优于 BFS,反之亦然吗?
这在很大程度上取决于搜索树的结构以及解决方案(又称搜索项)的数量和位置。
如果你知道某个解决方案离搜索树的根不远,那么广度优先搜索(BFS 广度优先搜索 (BFS) 可能会更好。
如果树很深,解决方案很少,那么深度优先搜索(DFS (DFS) 可能要花费很长的时间,但 BFS 可能更快。
如果树非常宽,BFS 可能需要太多内存,因此完全不切实际。 可能完全不切实际。
如果解很频繁,但位于树的深处,那么 BFS 不切实际。
如果搜索树很深,则需要限制深度优先搜索(DFS)的搜索深度。 深度优先搜索 (DFS) 的搜索深度(例如使用 迭代加深)。
但这些只是经验之谈,你可能还需要进行试验。
DFS 比 BFS 更节省空间,但可能会达到不必要的深度。
它们的名字很能说明问题:如果广度大(即分支系数大),但深度非常有限(如移动次数有限),那么 DFS 可能比 BFS 更可取。
值得一提的是,还有一种鲜为人知的变体,即迭代深化深度优先搜索,它兼具 DFS 的空间效率和 BFS 的层序访问(累积)。这种算法会重新访问一些节点,但只会带来一个恒定因子的渐近差值。