问答

当前位置
  • 首页
  • 问答
  • 能不能系统讲讲什么时候用BFS和DFS

能不能系统讲讲什么时候用BFS和DFS

哪些时候一个可以beat另一个?哪些时候两个都ok?

4 个回复

2016-03-14 马同学

首先感觉这个问题问的好大。
我就稍微说几句,BFSDFS 都是搜索算法,我就比较一下他们的优缺点。
1.BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适宜使用DFS,因为DFS搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根的最近的解。(当然这个DFS的不足,可以使用迭代加深搜索ID-DFS去弥补)

2.空间优劣上,DFS是有优势的,DFS不需要保存搜索过程中的状态,而BFS在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。

3.DFS适合搜索全部的解,因为要搜索全部的解,那么BFS搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,DFS搜索也会搜索全部,但是相比DFS不用记录过多信息,所以搜素全部解的问题,DFS显然更加合适。

上面提到的迭代加深搜索(ID-dfs)我觉得充分吸收了BFSDFS各自的长处


2016-03-27 九章管理员

基本原则:能用BFS的时候就用BFS,不能用的时候再用DFS。


2016-11-29 好同学

有个问题,当搜索所有解的时候DFS会出现栈溢出的情况,这个怎么解决


2016-12-08 余同学

1.增加栈内存。这个可以通过在程序开始的时候加一些代码完成,具体的自行百度。
2.定义全局变量数组(或者其他的什么全局变量结构),来存储搜索过程中的数据。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1