关注
10、BFS+DFS
深搜,顾名思义,是深入其中、直取结果的一种搜索方法
如果深搜是一个人,那么他的性格一定倔得像头牛!他从一点出发去旅游,只朝着一个方向走,除非路断了,他绝不改变方向!除非四个方向全都不通或遇到终点,他绝不后退一步!因此,他的姐姐广搜总是嘲笑他,说他是个一根筋、不撞南墙不回头的家伙。
深搜很讨厌他姐姐的嘲笑,但又不想跟自己的亲姐姐闹矛盾,于是他决定给姐姐讲述自己旅途中的经历,来改善姐姐对他的看法。他成功了,而且只讲了一次。从那以后他姐姐不仅再没有嘲笑过他,而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了姐姐,但他不知道,其实另有原因……
深搜是这样跟姐姐讲的:关于旅行呢,我并不把目的地的风光放在第一位,而是更注重于沿路的风景,所以我不会去追求最短路,而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地,于是我只能每到一个地方,就向当地的人请教各个方向的道路情况。
深搜优缺点
①优点
能找出所有解决方案
优先搜索一棵子树,然后是另一棵,所以和广搜对比,有着内存需要相对较少的优点
② 缺点
要多次遍历,搜索所有可能路径,标识做了之后还要取消(在图中需要做标识)。
在深度很大的情况下效率不高
使用场景:性格测试的游戏
参考文章:https://segmentfault.com/a/1190000010563179
广搜,顾名思义,是多管齐下、广撒网的一种搜索方法
广搜属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。类似树的按层遍历,其过程为:首先访问初始点Vi,并将其标记为已访问过,接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2 … Vit,并均标记为已访问过,然后再按照Vi1、Vi2…Vit 的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依此类推,直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。
广搜优缺点
①优点
对于解决最短或最少问题特别有效,而且寻找深度小
每个结点只访问一遍,结点总是以最短路径被访问,所以第二次路径确定不会比第一次短
②缺点
内存耗费量大(需要开大量的数组单元用来存储状态,需要使用队列来保存遍历元素)
使用场景:计算网络数据链路层的最短跳数,走迷宫的最短路径
查看原帖
1 评论
相关推荐
07-22 15:24
广西师范大学 大数据开发工程师 上周偶然刷到了lls的26秋招提前批开了,主包前段时间从字节实习完,秉持着投着试试的心态,认真填写了秋招的网申,提交成功的下一秒再刷新应聘页面,已经变成流程结束好夸张!是不是被机筛了,终究是双非不配了

点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 哪些公司开提前批了? #
25479次浏览 258人参与
# 华子oc时间线 #
1244021次浏览 6483人参与
# 风评不好的公司,你会去吗? #
59728次浏览 432人参与
# 实习如何「偷」产出? #
49692次浏览 1307人参与
# 除了主业以外,你还有哪些其他收入? #
11808次浏览 199人参与
# 不卡学历的大厂有哪些? #
28162次浏览 223人参与
# 校招阶段,学历VS技术哪个更重要? #
17174次浏览 184人参与
# 职场新人体验 #
24861次浏览 233人参与
# 腾讯音乐求职进展汇总 #
98034次浏览 570人参与
# 社恐入职新公司如何融入团队 #
11798次浏览 63人参与
# 校园里的破防时刻 #
11029次浏览 123人参与
# 哪些公司校招卡第一学历 #
67149次浏览 263人参与
# Offer比较,你最看重什么? #
191545次浏览 1301人参与
# 你投递的公司有几家约面了? #
108871次浏览 779人参与
# 你觉得技术面多长时间合理? #
100206次浏览 720人参与
# 你今年的平均薪资是多少? #
133988次浏览 686人参与
# 实习打杂,要跑路吗 #
17964次浏览 202人参与
# 正在实习的碎碎念 #
1454609次浏览 13469人参与
# 你最满意的offer薪资是哪家公司? #
33068次浏览 176人参与
# 你的秋招第一场笔试是哪家 #
147455次浏览 1484人参与