搜索算法之深度优先搜索

《搜索算法之深度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索算法之深度优先搜索值得拥有的资料是来自平时学习积累总结的有问题的地方肯定有的还请大家批评指正！搜索算法之深度优先搜索[算法分析]编程学到现在才真正到了部分从这里往下学你才知道什么叫做博大精深今天我们要啃的这块硬骨头叫做深度优先搜索法首先我们来想象一只老鼠在一座不见天日的迷宫内老鼠在入口处进去要从出口出来那老鼠会怎么走？当然是这样的：老鼠如果遇到直路就一直往前走如果遇到分叉路口就任意选择其中的一个继续往下走如果遇到死胡同就退回到最近的一个分叉路口选择另一条道路再走下去如果遇到了出口老鼠的旅途就算结束了深度

2、优先搜索法的基本原则就是这样：按照某种条件往前试探搜索如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索直到找到条件的目标为止实现这一算法我们要用到编程的另一大利器--递归递归是一个很抽象的概念但是在日常生活中我们还是能够看到的拿两面镜子来把他们面对着面你会看到什么？你会看到镜子中有无数个镜子？怎么回事？A镜子中有B镜子的象B镜子中有A镜子的象A镜子的象就是A镜子本身的真实写照也就是说A镜子的象包括了A镜子还有B镜子在A镜子中的象..................好累啊又烦又绕口还不好理解换

3、成计算机语言就是A调用B而B又调用A这样间接的A就调用了A本身这实现了一个重复的功能再举一个例子；从前有座山山里有座庙庙里有个老和尚老和尚在讲故事讲什么呢？讲：从前有座山山里有座庙庙里有个老和尚老和尚在讲故事讲什么呢？讲：从前有座山山里有座庙庙里有个老和尚老和尚在讲故事讲什么呢？讲：............好家伙这样讲到世界末日还讲不玩老和尚讲的故事实际上就是前面的故事情节这样不断地调用程序本身就形成了递归万一这个故事中的某一个老和尚看这个故事不顺眼就把他要讲的故事换成："你有完没完啊！"这样整个故事也就嘎

4、然而止了我们编程就要注意这一点在适当的时候就必须要有一个这样的和尚挺身而出把整个故事给停下来或者使他不再往深一层次搜索要不我们的递归就会因计算机存储容量的限制而被迫溢出切记切记我们把递归思想运用到上面的迷宫中记老鼠现在所在的位置是(x,y),那它现在有前后左右4个方向可以走分别是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一个方向是它来时的路我们先不考虑我们就分别尝试其他三个方向如果某个方向是路而不是墙的话老鼠就向那个方向迈出一步在新的位置上我们又可以重复前面的步骤老鼠走到了死胡同又

5、是怎么回事？就是除了来时的路其他3个方向都是墙这时这条路就走到了尽头无法再向深一层发展我们就应该沿来时的路回去尝试另外的方向例：八皇后问题：在标准国际象棋的棋盘上（8*8格）准备放置8只皇后我们知道国际象棋中皇后的威力是最大的她既可以横走竖走还可以斜着走遇到挡在她前进路线上的敌人她就可以吃掉对手要求在棋盘上安放8只皇后使她们彼此互相都不能吃到对方求皇后的放法这是一道很经典的题目了我们先要明确一下思路如何运用深度优先搜索法完成这道题目我们先建立一个8*8格的棋盘在棋盘的第一行的任意位置安放一只皇后紧接着我们就

6、来放第二行第二行的安放就要受一些限制了因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放皇后的接下来是第三行......或许我们会遇到这种情况在摆到某一行的时候无论皇后摆放在什么位置她都会被其他行的皇后吃掉这说明什么呢？这说明我们前面的摆放是失败的也就是说按照前面的皇后的摆放方法我们不可能得到正确的解那这时怎么办？改啊我们回到上一行把原先我们摆好的皇后换另外一个位置接着再回过头摆这一行如果这样还不行或者上一行的皇后只有一个位置可放那怎么办？我们回到上一行的上一行这和老鼠碰了壁就回头是一个意思就这样的

7、不断的尝试修正尝试修正我们最终会得到正确的结论的[参考程序]programqueen;{8皇后问题参考程序}constn=8;vara,b:array[1..n]ofinteger;{数组a存放解：a[i]表示第i个皇后放在第a[i]列；}c:array[1-n,n-1]ofinteger;d:array[2..n+n]ofinteger;{数组bcd表示棋盘的当前情况：b[k]为1表示第k行已被占领为0表示为空；c、d表示对角线}k:integer;procedureprint;{打印结果}varj:in

8、teger;beginforj:=1tondowrite(a[j]:4);writeln;end;procedruetry(i:integer);{递归搜索解}varj:integer;{每个皇后的可放置位置注意：一定要在过程中定义；否则当递归时会覆盖掉它的值不能得到正确结果}beginforj:=1tondobeginif(b[j]=0)and(c[i-j]=0)and(d[i+j]=0)then{检查位置是否