什么时候用深搜(dfs)什么时候用广搜(bfs)(转)

1.BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适宜使用DFS,因为DFS搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根的最近的解。(当然这个DFS的不足,可以使用迭代加深搜索ID-DFS去弥补)
2.空间优劣上,DFS是有优势的,DFS不需要保存搜索过程中的状态,而BFS在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。
3.DFS适合搜索全部的解,因为要搜索全部的解,那么BFS搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,DFS搜索也会搜索全部,但是相比DFS不用记录过多信息,所以搜素全部解的问题,DFS显然更加合适。

作者:知乎用户
链接:https://www.zhihu.com/question/23780297/answer/167225829
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 
就我个人理解,最短路用广搜,全部解用深搜
上一篇:2、kvm基础常用命令操作


下一篇:玩转Docker之常用命令篇(三)