DFS&BFS第二次小考总结
2025-03-23 17:15:20
发布于：上海
食用说明:虽然只是主播的一次考试总结,但如果有DFS和BFS题目难以理解,也可以看看主播的错因,或许也可以帮到你
前情提要:(跟正文基本上没有联系,想直接看题的小可爱可以不看哦)
大家还记得我有一个"小测验分析"吗?来解释一下为什么那个暂时不更了:
本来主播以为自己只需要进行一次考试就可以了...结果3.22主播去上常规课时,被通知还要考两次,然后主播炸了.
主要是因为可怜的主播不知道还有第二次和第三次考试,所以近期已经在预习新课了(详解最短路自学笔记),然后没有复习再加上3.21基本上莫有睡觉(通宵)就成了这样:
就成了这样:
(本人在常规课的班级里几乎一直都是第一,这次直接掉到第四挺难过的...)
所以打算放弃问题不太大的第一次考试,直接来细究有问题的第二次考试
正文开始:
游荡的奶牛:
错因分析:对回溯算法理解模糊(本来做DFS笔记的那一篇时,以为自己对回溯已经完全掌握了,但现在好像突然发现,主播掌握的知识也只是冰山一角)和对DFS和BFS运用的混淆:
1.对回溯理解模糊:
回溯:多用于01DFS和排列DFS:就是用于有选择的DFS,选择一个后,就把这个选择设置为不可选择的类型.
简单来说就是运用vis数组进行一个标记,它的存在有两个原因:
原因一:有一些题目可能会专门说"选过的不能再选",比如说一些走迷宫的题目,题目中可能会要求:"走过的路不能再走"之类的,这时你就可以用一个bool vis来去标记你走过的路径.
如果在上述的条件之下,题目的要求是求出它的路径有多少种,你就可以运用回溯.
如何运用呢?就是把标记过的vis数组在返回后,重新撤掉标记.
比如:
vis[x][y]=1;
dfs(x,y);
vis[x][y]=0;
原因2:回溯存在的另一部分的原因,其实是为了节省时间的:走过的路,不再走一遍,也是一种节约时间的体现.
好了,解释完了回溯,就证实开始分析错题:
这道题看似与普通的迷宫DFS无异,但其实还是有差别的,主要看这句话:
这句话的出现,也表明了,贝西可能曾经到过R2,C2.也就是说,这是允许重复经过的一次DFS,如果要硬加回溯上去的话,可能会导致结果出错,因为这道题它不仅要求"到达"还要求了"时间".如果不是完全卡在正确的时间,那也是不能算一种方案的.
所以,这道题不用回溯,也不用标记曾经到过的点.
但这很明显会出问题:
如果不进行标记,也就代表,它的行动是永无止境的.
这时,需要想一个方法,能使递归结束:
只要限制时间记好了,时间超过t,就直接return,完美!
......
不过这个问题,主播已经找(xue)到了解决方案:就是将剪枝(就是超过t就返回)进一步完善:
if(abs(x-r2)+abs(y-c2)+h>t)return;//x,y是现在所处位置
计算未来最少还有几步到达终点再加上现在已花费的时间,如果超过目标时间,就直接返回
(这个优化看似很小,也没有存在感,但其实,如果说不及时返回,会使一些不符合要求的路径走很长时间,使得程序无法运行到目标路径)(但如果是这样的话,应该是TLE的,主播也不知道为什么是WA,但却是改了优化,就变成满分了)
腐烂的橘子:
错因分析:识别错误,本来是多源BFS的,结果硬生生给主播识别成DFS了...一定要记住:最短路是BFS!
其他倒也没什么好提的...
要点就两个:
1.BFS 2.多源
(不是主播偷懒,真的知识因为这道题只是板子题,没有什么好分析来,分析去的.甚至有很多所谓的特殊情况,都是不用去判断的)
这里空空如也
有帮助，赞一个