| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2921 人关注过本帖, 1 人收藏
标题:递归的迷宫问题,请问代码错在什么地方
只看楼主 加入收藏
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 10楼 komorebi0110
楼主还是要立足于学习书本知识为好,论坛里接受的很多信息不准确(也包括我输出的信息),容易被误导。
1,关于深搜和广搜,可参考https://这篇文章,里面说的很清楚:深搜适合穷尽所有路线方案,广搜适合找最短路线。形象地理解就是广搜相当于以出发点为圆心,一圈圈往外搜索,直到找到目标,很显然最长路线就是圆心到目标为半径所包含的圆内所有点的一半。而深搜是从出发点先往一个方向搜,直到搜不动才换方向,最终会穷尽能搜到的所有点,这个面积肯定比最短距离为半径的圆的面积大。
2,只要使用深搜算法,即使不用递归,也必然会回溯。DFS最后都会回到出发点,因为该算法必须清除路线标记,否则得不到所有解,也就可能得不到最短路径。而广搜比较适合用循环解决,即使用递归也不需要清除标记就能得到最短路径。
3,关于剪枝,楼主和10楼代码类似,深搜时打标记,回溯时清除标记,根本没有剪枝。剪枝行为一般类似于动态规划的反过程,动态规划是记住并使用层层递进过程中的最优解,而剪枝是记住并丢弃达不到目标或最差解。我3楼的代码就用了两种方法剪枝,一是当深搜步数大于当前最少步数时,就不再深搜,第二种是当走别人走过的路且交叉点步数大于别人在这个位置的步数时不再深搜。通过比较,我三个起点坐标递归的次数分别是13、2161、2233,而楼主的递归次数分别是9、16674、49885,显然通过剪枝后递归的次数只有不剪枝的1/23,至于为什么第一个递归次数多于楼主,是算法上细微差别导致的,楼主是在递归前判断坐标合法性,不合法的没进递归,我的是在递归后判断,不管是否合法先递归再说,如果起点坐标在边缘,自然就多了些。
以上观点仅供参考。

能编个毛线衣吗?
2020-04-21 22:52
komorebi0110
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:145
专家分:17
注 册:2019-11-23
收藏
得分:0 
回复 11楼 wmf2014
谢谢!

我想要两颗西柚。
2020-04-25 17:23
快速回复:递归的迷宫问题,请问代码错在什么地方
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017756 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved