DFS(一)

举报
野猪佩奇996 发表于 2022/01/23 01:03:56 2022/01/23
【摘要】 使用场景 输入数据:如果是递归数据结构,如单链表,二叉树,集合,则一定可以用DFS;如果是非递归数据结构,如一维数组,二维数组,字符串,图,则概率小一点。 状态转换图:树或图 求解目标:必须要走到最深(如树,必须走到叶结点)才能得到一个解,这种情况适合用DFS 思考的步骤 1.是求路径条数,还是路径本身(或动作序列)? DF...

使用场景

输入数据:如果是递归数据结构,如单链表,二叉树,集合,则一定可以用DFS;如果是非递归数据结构,如一维数组,二维数组,字符串,图,则概率小一点。

状态转换图:树或图

求解目标:必须要走到最深(如树,必须走到叶结点)才能得到一个解,这种情况适合用DFS

思考的步骤

1.是求路径条数,还是路径本身(或动作序列)?

DFS最常见的三个问题,求可行解的总数,求一个可行解,求所有可行解。

(a)如果是路径条数,则不需要存储路径

(b)如果是求路径本身,则要用一个数组path[]存储路径。和BFS不同,BFS虽然最终求的也是一条路径,但需要存储扩展过程的中所有路径,在没有找到答案之前所有路径都不能放弃;而DFS,在搜索过程中始终只有一条路径,因此用一个数组就足够了。

2.只要求一个解,还是要求所有解?

如果只要求一个解,那就找到一个解就可以返回

如果要求所有解,找到一个后,还要继续扩展,知道遍历完

BFS一般只要求一个解,因此不需要考虑这个额问题(BFS当然也可以求所有解,这时需要扩展到所有叶子结点,相当于在内存中存储整个状态转换图,非常占内存,因此BFS不适合解这类问题)

3.如何表示状态?

即一个状态需要存储那些必要的数据,才能完整提供如何扩展到下一步状态的所有信息。和BFS不同,DFS的惯用写法,不是把数据记录在状态struct里,而是添加函数参数(有时为了节省递归堆栈,用全局变量),struct里的字段与函数参数一一对应。

4.如何扩展状态?

这一步和上一步相关。状态里记录得数据不同,扩展方法也就不同。对于固定不变的数据结构(一般题目直接给出,作为输入数据),如二叉树,图等,扩展方法很简单,直接往下一层走,对于隐式图,要先在第一步里想清楚状态所带的数据。

5.关于判重

(a)是否需要判重?如果状态转换图是一棵树,则不需要判重,因为在遍历过程中不可能重复;如果状态转换图是一个DAG,则需要判重。这一点和BFS不同,BFS的状态转换图总是DAG,必须要判重。

(b)怎样判重?和BFS相同!!同时DAG说明存在重叠子问题,此时可以用缓存加速。

6.终止条件是什么?

终止条件是指到了不能扩展的末端节点。对于树,是叶子结点,对于图或者隐式图,是出度为0的节点

7.收敛条件是什么?

收敛条件是指找到了一个合法解的时刻。如果是正向DFS(父状态处理完才进行递归,即父状态不依赖子状态,递归语句一定是在最后,尾递归),则是指是否达到目标状态;如果是逆向DFS(处理父状态时需要先知道子状态的结果,此时递归语句不在最后),则是指是否达到初始状态。

由于很多时候终止条件和收敛条件是合二为一的,因此很多人不区分这两种条件。仔细区分这这两种条件是很有必要的。

为了判断是否到了收敛条件,要在函数接口里面用一个参数记录当前的位置(或距离目标还有多远)。如果是求一个解,直接返回这个解;如果是求所有解,要在这里收集解,即把第一步中表示路径的数组path[]复制到解集合里面。

8.如何加速?

(a)剪枝。 无通用方法,具体分析,在中间节点提前返回。

(b)缓存。

i。提前条件:状态转换图是一个DAG.DAG--》存在重叠子问题--》子问题的解会被重复利用,用缓存能加速。如果依赖关系是树状的(如树,单链表等),没有必要加缓存,因为子问题只会一层层往下,用一次就再也不会用到,加了缓存也没有啥加速效果。

ii。具体实现:可以用数组/HashMap。维度复杂的,用HashMap,C++有map,C++11以后用unordered_map,比map快。

 

拿到一个题目,回忆上面8个问题,对于树,不需要回答第5和第8个问题。

------------------------------------------------------------------------------------------

dfs模板 
 *input 输入数据指针
 *path  当前路径,也是中间结果
 *result存放最终结果
 *cur/gap标记当前位置/距离目标的距离
 *return 路径长度,如果是求路径本身,则不需要返回长度


  
  1. /**
  2. *dfs模板
  3. *input 输入数据指针
  4. *path 当前路径,也是中间结果
  5. *result存放最终结果
  6. *cur/gap标记当前位置/距离目标的距离
  7. *return 路径长度,如果是求路径本身,则不需要返回长度
  8. */
  9. void dfs(type &input,type &path,type &result ,int cur or gap){
  10. if(数据非法) return 0;//终止条件
  11. if(cur==input.size()){//收敛条件
  12. //if(gap==0){
  13. 将path放入result
  14. }
  15. if(可以剪枝) return;
  16. for(...){//执行所有可能的扩展动作
  17. 执行动作,修改path
  18. dfs(input,step+1 or gap--,result);
  19. 恢复path
  20. }
  21. }

DFS和回溯法的区别

回溯法=DFS+剪枝

DFS和递归的区别

递归和迭代是对应的。

DFS可以用递归实现,也可用栈实现

递归一般总是用来实现DFS

递归有两种加速策略:(1)剪枝:对中间结果进行判断,提前返回(2)缓存:缓存中间结果,防止重复计算,用空间换时间

 

文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。

原文链接:andyguo.blog.csdn.net/article/details/103866516

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200