2022年搜索算法之深度优先搜索知识 .pdf

- 1 - 搜索算法之深度优先搜索 算法分析 编程学到现在才真正到了部分，从这里往下学，你才知道什么叫做博大精深。今天我们要啃的这块硬骨头叫做深度优先搜索法。首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出 口出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一个继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算结束了。 深度优先搜索法的基本原则就是这样：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。实现这一算法， 我们要用到编程的另一大利器- 递归。递归是一个很抽象的概念， 但是在日常生活中，我们还是能够看到的。拿两面镜子来，把他们面对着面，你会看到什么？你会看到镜子中有无数个镜子？怎么回事？A镜子中有 B镜子的象， B镜子中有 A镜子的象， A镜子的象就是 A镜子本身的真实写照，也就是说 A镜子的象包括了 A镜子， 还有 B镜子在 A镜子中的象 ,好累啊，又烦又绕口，还不好理解。换成计算机语言就是A调用 B，而 B又调用 A，这样间接的， A就调用了 A本身，这实现了一个重复的功能。再举一个例子；从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：,。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来， 或者使他不再往深一层次搜索，要不，我们的递归就会因计算机存储容量的限制而被迫溢出，切记，切记。我们把递归思想运用到上面的迷宫中，记老鼠现在所在的位置是 (x,y),那它现在有 前后左右 4 个方向可以走，分别是 (x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一个方向是它来时的路，我们先不考虑，我们就分别尝试其他三个方向，如果某个方向是路而不是墙的话，老鼠就向那个方向迈出一步。 在新的 位置上，我们又可以重复前面的步骤。 老鼠走到了死胡同又是怎么回事？就是除了来时的路，其他 3 个方向都是墙，这时这条路就走到了尽头，无法再向深一层发展，我们就应该沿来时的路回去，尝试另外的方向。例：八皇后问题：在标准国际象棋的棋盘上（8*8 格）准备放置 8 只皇后，我们知 道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她就可以吃掉对手。要求在棋盘上安放8只皇后，使她们彼此互相都不能吃到对方，求皇后的放法。这是一道很经典的题目了， 我们先要明确一下思路， 如何运用深度优先搜索法，完 成这道题目。我们先建立一个8*8 格的棋盘，在棋盘的第一行的任意位置安放一只皇后。紧接着，我们就来放第二行，第二行的安放就要受一些限制名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - - 2 - 了， 因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放皇后的，接下来是第三行， , ，或许我们会遇到这种情况，在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其他行的皇后吃掉，这说明什么呢？这说明，我们前面的摆放是失败的，也就是说，按照前面的皇后的摆放方法，我们不可能得到正确的解。 那这时怎么办？改啊， 我们回到上一行， 把原先我们摆好的皇后换另外一个位置， 接着再回过头摆这一行， 如果这样还不行或者上一行的皇后只有一个位置可放，那怎么办？我们回到上一行的上一行，这和老鼠碰了壁就回头是一个意思。就这样的不断的尝试，修正，尝试修正，我们最终会得到正确的结论的。 参考程序 program queen;8皇后问题参考程序 const n=8; var a,b:array 1.n of integer;数组 a 存放解： ai表示第 i 个皇后放在第 ai列； c:array 1-n,n-1 of integer; d:array 2.n+n of integer;数组 b，c，d 表示棋盘的当前情况： bk为 1 表示第 k 行已被占领为 0 表示为空； c、d 表示对角线 k:integer; procedure print;打印结果 var j:integer; begin for j:=1 to n do write(aj:4); writeln; end; procedrue try(i:integer); 递归搜索解 var j:integer;每个皇后的可放置位置。注意：一定要在过程中定义；否则当递归时会覆盖掉它的值，不能得到正确结果 begin for j:=1 to n do begin if (bj=0) and (ci-j=0) and (di+j=0) then检查位置是否合法 begin ai:=j;置第 i 个皇后的位置是第j 行 bj:=1;宣布占领行、对角线 ci-j:=1; di+j:=1; if in then try(i+1) else print;如果末达目标则放置下一皇后，否则打印结果 bj:=0;清空被占行、对角线，回溯 ci-j:=0; di+j:=0; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - - 3 - end; end; begin for k:=1 to n do bk:=0;初始化数据 for k:=1-n to n-1 do ck:=0; for k:=2 to n+n do dk:=0; try(1); end. 习题 1、完成上述老鼠走迷宫问题。2000年广东省重点中学邀请赛一试第一题求三角形最大面积题目描述圣诞节快到了。你接受了一件光荣的任务，就是制作圣诞树顶上的那颗大星星。不过当你拿到不过当你拿到制作用的三角形银纸的时候，你发现银纸上面有许多洞。原来你的妹妹已经再银纸上见剪下了一些小的三角形来制作小星星。你惟有寻找一个算法，能告诉你在每张银纸上还能切出来的最大的三角形面积。给定一个三角形， 里面有黑色和白色的区域， 你必须找到白色的区域中最大三角形的面积，如下图所示：输入输入文件包含若干个三角形描述。每个三角形描述的第一行是一个整数n(1=n=100)， 表示该三角形的高。 接下来的 n 行每行包含由空格、 “#”和“ -”组成的字符串表示三角形的状况。其中“#”代表黑色的区域， “- ”代表白色的区域。空格是用来填充输入的左边，从而使得整个输入构成一个三角形的形状。对每个三角形，每行字符“#”和“- ”的数目之和都是奇数，由2n-1 递减至 1。全部输入以 n=0 结束。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - - 4 - 输出对输入的每个三角形， 输出白色的区域中最大三角形的面积，注意最大三角形可以是顶角朝上的，如同第2 个样例输入所示样例输入5 # - # # - - - - # - - - - - # - - - - # - - # - - 4 # - # - # - - # - - - # # # - - 样例输出9 4 题目分析（聿怀中学吴优）这道题如果从每一个小三角形出发找出以它为顶点的最大三角形，会变成搜索，浪费大量的时间。 此外，从文件读入的三角形图形只用“-”和“#”来表示未破和已剪破的三角形， 没有直接告诉我们小三角形是朝上还是朝下的，这一点也是要判断的。数据结构一个二维数组（用来存放以每一个小三角形为顶点的大三角形的高）算法流程1、读入三角形图形，转化为而维数组。（未破赋值为1，以破 0）2、从第一行，算出每一行以每一个顶角朝下的小三角形为顶点的最大三角形的高。方法：x-1 x x+1 y-1 ? ? ? y ? 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - - 5 - 只要（ x,y-1) 处为 0，(x,y) 的值仍为 1 只要 （x,y-1) 处不为 0， (x,y) 的值就为 (x-1,y-1)及(x+1,y-1)两处的较小值加 1。（以上两种情况必须（ x,y) 处不为 0，否则 (x,y) 处的值为 0。3、从倒数第一行开始，算出每一行中以每一个顶角朝上的小三角形为顶点的最大三角形的高（方法与2 的方法相近）4、找出二维数组中最大的数，算出以它为高的等边三角形的面积，就是题目所求的解。优缺点优点：最环的情况也只是搜索5050 次。（ 1=n0 then if ai-1,j0 then if ai-1,j-10 then if ai+1,j0 then if ai+1,j-1ai+1,j+1 then ai,j:=ai+1,j-1+1 else ai,j:=ai+1,j+1+1; end; procedure find3; begin num:=0; for i:=1 to n do for j:=1 to n*2-i do if numai,j then num:=ai,j; end; procedure find; begin find1; find2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - - 8 - find3; end; procedure write_file; begin writeln(f2,num*num); end; procedure close_file; begin close(f1); close(f2); end; begin init; readln(f1,n); while n0 do begin read_file; find; write_file; readln(f1,n); end; close_file; end. 剪枝搜索名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - - 9 - 加括号题目描述输入两个数字 (i,j)，在第一个数字 i 中间添上若干个加号，使得这个代数式的值等于第二个数字j 。问题分析这道题采用的算法是剪枝搜索， 逐一在第一个数字i 各个数字之间添上加号， 并计算出当前代数式的值， 如果等于第二个数字j ， 则退出循环，打印结果“ YES ”；如果不是，则继续循环；当循环结束后，还未能得出第二个数j ，则打印结果“NO ”。算法流程1、首先将以字符串输入的第一个数字i 切成一个数字 e 段，放进一个数组ae里。2、接着进行循环，逐一在第一个数字i 各个数字之间添上加号，由于在各个数字之间添上加号后代数式的值只有两种情况：大于第二个数字 j 或小于第二个数字 j ，所以循环的内容可以如下：（1）以 h,i分别作为当前处理的数字的首位在数组里的位置和在当前数字的第i 位添加号。（2）分别以 x1,x2 存放添加号后加号前的数值以及加号后的数值，x3 将赋值为x1+x2，作为当前代数式的值。当 x3j 时，则进行将 h 赋值为 i ，将要处理的数字赋值为加号后的数值，并将x3 赋值为 x3-x2 ，作为加号前的数值；当x3j时，而且 ie 时， 则将 h 赋值为 h-1， i 赋值为 h+1，在当前处理的数字添加号的数位的前一位添上加号，并将 x3 赋值为 x3-x2-ai。3、 当 he、 ie 、 x3j 时， 则退出循环并打印结果“ no”； 当 0h=e、0i=e、x3=j 时，则退出循环并打印结果“yes”。参考程序下载program aa; var a,b:text; c:string; d,e,g,h,i,x1,x2,x3,xx:integer; f:array 1.100 of integer; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - - 10 - procedure bb; begin assign(a,tjh.dat); reset(a); readln(a,c,d); close(a); end; procedure cc; begin for e:=1 to length(c) do fe:=ord(ce)-48; x1:=0; x2:=0; x3:=0; xx:=1; h:=1; i:=1; while x3d do begin for g:=h to i do x1:=x1*10+fg; for g:=i+1 to e do x2:=x2*10+fg; x3:=x1+x2+x3; if x3=d then exit; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - - 11 - if (h0) or (i0) then begin xx:=0; exit; end; if x3d then begin h:=h+1; i:=h; x1:=0; x3:=x3-x2; x2:=0; end; end; end; procedure dd; begin assign(b,tjh.out); rewrite(b); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - - 12 - if xx=1 then writeln(b,yes) else writeln(b,no); close(b); end; begin bb; cc; dd; end. 练习1、 有一个由数字 1， 2， 3,9组成的数字串 ( 长度不超过 200), 问如何将 M(M=20)个加号 (+) 插入到这个数字串中 , 使所形成的算术表达式的值最小. 请编一程序解决这个问题 . 注意: 加号不能加在数字串的最前面或最末尾, 也不应有两个或两个以上的另号相邻.M 保证小于数字串的长度 . 例如: 数字串 79846,若需要加入两个加号 , 则最佳方案为 79+84+46,算术表达式的值为 133. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -