问题描述
据我了解DFS(深度优先搜索)和BFS(广度优先搜索)之间的差异,但我想知道当它是更实际的使用一个比其他?
I understand the differences between DFS (Depth First Search) and BFS (Breadth First Search), but I'm interested to know when it's more practical to use one over the other?
谁能给出任何示例如何DFS会胜过BFS反之亦然?
Could anyone give any examples of how DFS would trump BFS and vice versa?
推荐答案
这很大程度上依赖于搜索树的结构和解决方案的数量和位置(即搜索的项目)。如果你知道一个解决方案是不远处的树的根,广度优先搜索(BFS)可能会更好。如果树是非常深刻和解决方案是罕见的,深度优先搜索(DFS),可能需要很长的时间,但BFS可能会更快。如果树很宽,一个BFS可能需要太多的内存,所以它可能是完全不切实际的。如果解决方案频繁,但位于深树,BFS可能是不切实际的。如果搜索树是非常深的,你将需要限制搜索深度深度优先搜索(DFS),反正(例如使用迭代加深)。
That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items). If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).
但这些经验只是规则;你可能需要进行试验。
But these are just rules of thumb; you'll probably need to experiment.
这篇关于什么时候才使用DFS VS BFS?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!