深度优先搜索(pascal).ppt

1、深度优先搜索,从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到“ 尽头 ”而没达到目的地的时候, 再倒回上一个出发点, 从另一个可能出发, 继续搜索. 这种不断“ 倒回 一步寻找解的方法, 称作 回溯法 . 回溯即是较简单、较常用的搜索策略,实质就是一种搜索策略.,从A到B的路线:A-4-6-B,如:找一条从A到B的路线,算法思想 深度优先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点

2、可到达的所有结点为止。,深度优先搜索的基本算法结构 （1）递归实现。 Procedure dfs_try(i); For i:=1 to maxr do begin if 子结点mr符合条件 then begin 产生的子结点mr入栈； if子结点mr是目标结点 then 输出； else dfs_try(i+1); 栈顶元素出栈； End; End;,1.、问题描述 学校放暑假时，信息学辅导教师有n本书要分给参加培训的n个学生。如：A，B，C，D，E共5本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书

3、本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。,输入格式：第一行一个数n（学生的个数，书的数量） 以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。 输出格式：依次输出每个学生分到的书号。 样例： 输入：book.in 5 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 输出：book.out 3 1 2 4 5,分析: a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; 方案:bi是第i个人借第bi

4、本书 book:array1.maxnof boolean; booki:能否可以借第i本书, 初始:true,一旦有人借了:就改为:false,算法设计: procedure try(i:integer);搜索第i个人可以借的书bi var j:integer; begin if i=n+1 then 若书都借出，则输出结果 else for j:=1 to n do if 第i个人可以借第j 本书 then begin 记录下bi; 标记第j本数已被借; try(i+1); 删除书的被借标志; end; end;,procedure try(i:integer); var j:intege

5、r; begin if i=n+1 then print else for j:=1 to n do if bookj and (ai,j=1) then begin bi:=j; bookj:=false; try(i+1); bookj:=true; bi:=0; end; end;,procedure print; var i:integer; begin for i:=1 to n-1 do write(bi, ); writeln(BN); end;,主程序: begin fillchar(b,sizeof(b),0); fillchar(book,sizeof(book),true

6、); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); try(1); End.,2.、骑士的游历 设有下图所示的一个棋盘，在棋盘上的A点有一个中国象棋马，并约定 马走的规则： 1、马只向右走； 2、马走“日“字。 找出所有从A到B的路径。,一种方法：(2 1)(4 0)(5 2)(6 0)(7 2)(8 4),1,1,1,分析： 1、马跳的方向： x:array1.4,1.2of integer= (1,-2),(2,-1),(2,1),(1,2); 4个方向横向和纵向的增量。 2、记录马经过的位置坐标 a:array0.8,1

7、.2of integer; 第i步所在的位置，1：横坐标 2：纵坐标,递归算法： procedure try(i:integer);搜索第i步: try(1); var j:integer; begin for j:=1 to 4 do if (ai-1,1+xj,1=0)and(ai-1,1+xj,1=0)and(ai-1,2+xj,2=4) then begin ai,1:=ai-1,1+xj,1; ai,2:=ai-1,2+xj,2; if (ai,1=8) and (ai,2=4) then print(i) else try(i+1); end; end;,procedure pri

8、nt(i:integer); var j:integer; begin inc(t); write(t,:); for j:=1 to i do write(,aj,1, ,aj,2,); writeln; end;,3.、迷宫问题 设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放有0和1，0表示可通，1表示不能，迷宫走的规则如下图所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可通过，要另找路径。 输入例子：（从文件中读取数据） 8 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0

9、 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 输出要求：找出一条 从入口（左上角）到出口（又上角）的路径(不能重复)。 (1,1)-(2,1)-(3,1)-(2,2)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1),分析: a:array1.maxn,1.maxnof 0.1; 记录迷宫坐标 c:array1.maxn,1.maxnof 0.1; 访问标志:0:没走;1:已走 b:array0.maxn*maxn of integer;记录路径方向 d

10、x,dy:array1.8of integer; 方向位移,8个方向的位移: dx1:=0; dy1:=-1; dx2:=1; dy2:=-1; dx3:=1; dy3:=0; dx4:=1; dy4:=1; dx5:=0; dy5:=1; dx6:=-1; dy6:=1; dx7:=-1; dy7:=0; dx8:=-1; dy8:=-1;,读入数据: 坐标 procedure readdata; begin assign(input,a.in); reset(input); readln(n); for i:=1 to n do for j:=1 to n do begin read(aj

11、,i);i:纵坐标;j:横坐标 cj,i:=0; end; close(input);,递归算法: procedure try(i:integer);搜索第i步应到达的位置 var k:integer; begin for k:=1 to 8 do begin if (x+dxk=1)and(x+dxk=1)and(y+dyk=n)and (ax+dxk,y+dyk=0)and(cx+dxk,y+dyk=0) then begin x:=x+dxk; y:=y+dyk; cx,y:=1; bi:=k; if (x=n)and(y=1) then begin print(i); halt; en

12、d else try(i+1); cx,y:=0; x:=x-dxk; y:=y-dyk; end; end; end;,输出一组解: procedure print(i:integer); var j:integer; begin x:=1; y:=1; write(,x,y,); 初始位置 for j:=1 to i do 输出路线 begin x:=x+dxbj; y:=y+dybj; write(-,(,x,y,); end; writeln; end;,主程序: begin readdata; x:=1; y:=1; try(1); end.,4、覆盖问题。(li1.txt) 边长为

13、N（偶数）的正方形，用N*N/2个长为2宽为1的长方形将它全部覆盖。编程打印所有覆盖方法。当N=4时几种覆盖方法的打印格式举例如下：,输出: 1224 1122 1334 3344 5668 5566 5778 7788,输入: 4,分析: 把边长为n的正方形划分为n*n个边长为1的格子, 用数组a描述覆盖情况：aI,j：格子还没被覆盖，否则被编号为aI,j的格子覆盖,算法描述： 、先行后列的原则找到一个aI,j，即未被覆盖的格子（i，j）。 、如果行号(in)and(ai+1,j=0),即正下方的格子未覆盖,那么格子(I,j)和(i+1,j)用同一个1*2的格子覆盖. 转向 3. 如果列号(

14、jn)and(ai,j=0),即右邻的格子未覆盖,那么格子(I,j)和(i,j)用同一个1*2的格子覆盖. 转向 3 、如果现在已用完了nn长方形，则转向，否则执行 、打印现有的覆盖方案，得到一种覆盖方法。,procedure try(i:integer);搜索用编号i的长方形覆盖的格子：给格子编号 var j,k:integer; begin j:=0;列初始化 repeat找aj，k的格子 j:=j+1;k:=1; while (k0) do inc(k); until (k=n); aj,k:=i;格子（j,k）用编号i覆盖 if (jn) and (aj+1,k=0) then正下方格

15、子未覆盖，用i覆盖 begin aj+1,k:=i; if i*2n*n then 最大编号为n*n/2 try(i+1) else print; aj+1,k:=0;回溯 end;,if (kn) and (aj,k+1=0) then 右方方格子未覆盖，用i覆盖 begin aj,k+1:=i; if i*2n*n then try(i+1) else print; aj,k+1:=0; 回溯 end; aj,k:=0; 回溯 end;,procedure print; var i,j:integer; begin writeln; inc(t); for i:=1 to n do beg

16、in for j:=1 to n do write(ai,j); writeln; end; end;,主程序： begin readln(n); if odd(n) or (n0) then writeln(Error!) else try(1); end.,5、黑白棋子 现有N个黑棋和N个白棋，将这2N各棋子放入一个N*N棋盘，使每行每列都有一个黑棋和一个白棋。求满足上述要求的布棋方案有多少种。 N=2时，有以下两种放置方法：,输出： ,const max=10; type bhxing=array1.maxof shortint; var b:array1.max,1.maxof boo

17、lean;棋盘能否可用 bai:array1.maxof boolean;能否放白棋子 hei:array1.maxof boolean; ;能否放黑棋子 bb:bhxing;白棋子列号 hh：bhxing; 黑棋子列号 n:integer;t:int64; 初始化： fillchar(bai,sizeof(bai),true); fillchar(hei,sizeof(hei),true); fillchar(b,sizeof(b),true);,procedure try(x:integer);放置第x行的白黑棋子 var i,j:integer; begin if x=n+1 then

18、begin print(bb);print(hh);writeln;inc(t);exit;end; for i:=1 to n do 搜索第x行白棋应放置的列i if bx,i and baii then begin bx,i:=false;baii:=false;bbx:=i; for j:=1 to n do 搜索第x行黑棋应放置的列j if bx,j and heij then begin bx,j:=false;heij:=false;hhx:=j; try(x+1); bx,j:=true;heij:=true;回溯：释放黑棋的位置 end; bx,i:=true;baii:=tr

19、ue; 回溯：释放白棋的位置 end; end;,procedure print(bh:bhxing); var i:integer; begin for i:=1 to n do write(bhi); write( ); end;,主程序： begin fillchar(bai,sizeof(bai),true); fillchar(hei,sizeof(hei),true); fillchar(b,sizeof(b),true); readln(n); try(1); writeln(t); end.,6、数字排列(li3.txt) 在一个N*N的棋盘上（1=n=100),填入1,2,.

20、,n*n共n*n个数，使得任意两个相临的数之合为素数 例如： n=2 时，有:1 2 4 3 n=41 2 11 1216 15 8 513 4 9 146 7 10 3,分析： 逐行搜索1到n*n之间的数放在（i，j）处，依次判断他与上方（i-1,j）的数和左边(I,j-1)的数的和是否为素数，是就放(I,j)处，再放（I,j+1);如果不是素数，则继续在1到n*n之间搜索合适的数能放在(I,j)处。,const maxn=100; type a=array1.2*maxn*maxnof boolean; var i,j,k,m,n,x,y,nn:integer; p:a;素数表：pi=tr

21、ue :i是素数， pi=false :i不是素数 b:array1.maxn,1.maxnof integer;坐标 used:array1.maxn*maxnof boolean;检查是否该数是否用过,筛选法创建素数表 procedure prime; var i,j,s:integer; begin fillchar(p,sizeof(p),true); p1:=false; for i:=2 to 3*n div 2 do 依次搜索素数i并筛掉是i倍数的数 if pi then begin j:=2*i; while j=2*n*n do begin pj:=false; j:=j+i

22、; end; end; end;,判断（x,y）位置能否放数值k的函数 function ok(x,y,k:integer):boolean; begin ok:=true; if x1 then if not (pbx-1,y+k) then ok:=false; if y1 then if not (pbx,y-1+k) then ok:=false; end;,procedure try(x,y,dep:integer);递归搜索（x,y）处放第 dep 个数 var i:integer; begin if dep=n*n+1 then print else 如果已放了n*n个数，得出一

23、种方法 for i:=1 to n*n do if not(usedi) and ok(x,y,i) then begin bx,y:=i; usedi:=true; if y=n then try(x+1,1,dep+1) 如果当前是最右边一列，则转到下一行首列 else try(x,y+1,dep+1); 继续放当前行的下一列 usedi:=false;释放标志 end; end;,procedure print; var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do write(bi,j:4); writeln; e

24、nd; halt; end;,主程序： begin readln(n); if n=1 then begin writeln(NO);halt;end; prime; b1,1:=1; for i:=2 to n*n do usedi:=false; used1:=true; try(1,2,2); writeln(NO); end.,上机练习题 1.添加自然数问题。（add.pas） 要求找出具有下列性质的数的个数(包含输入的自然数n)： 先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理: . 不作任何处理; . 在它的左边加上一个自然数,但该自然数不能超过原数的一半;

25、. 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 输入文件：add.in,一行，n的值。 输出文件：add.out，一行，按照规则可产生的自然数个数。,样例： 输入文件： 6 满足条件的数为 6 16 26 126 36 136 输出文件 6,var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) end end; begin readln(n); s:=0; qiu(n); write

26、ln(s) end.,2. 跳马问题。（jump.pas） 在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。 输出文件：jump.out，一行，路径条数。,program jump; var h:array-1.7,-1.7 of integer; a,b:array1.8 of integer; i,j,num:integer; procedure print; var i,j:integer; begin num:=num+1; if num=5 then begin for i:=1 to 5 do b

27、egin for j:=1 to 5 do write(hi,j:4); writeln; end; writeln; end; end;,procedure try(x,y,i:integer); var j,u,v:integer; begin for j:=1 to 8 do begin u:=x+aj; v:=y+bj; if hu,v=0 then begin hu,v:=i; if i25 then try(u,v,i+1) else print; hu,v:=0 end; end; end;,begin for i:=-1 to 7 do for j:=-1 to 7 do if

28、 (i=1)and(i=1)and(j=5) then hi,j:=0 else hi,j:=1; a1:=2;b1:=1; a2:=1;b2:=2; a3:=-1;b3:=2; a4:=-2;b4:=1; a5:=-2;b5:=-1; a6:=-1;b6:=-2; a7:=1;b7:=-2; a8:=2;b8:=-1; num:=0; h1,1:=1; try(1,1,2); writeln(num); end.,3.过河卒,棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称

29、之为“马拦过河卒”。,棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 【输入】 一行四个数据，分别表示B点坐标和马的坐标。 【输出】 一个数据，表示所有的路径条数。 【样例输入】 6 6 3 2 【样例输出】 17,题目分析： 本题是一道典型的深度优先搜索题目。 需要处理好的细节有： 1.读入“马”的坐标，控制好八个方向。 2.在（n,m）棋盘上控制好“马”所能跳出的边界。 3.按向下、向右两个方向搜索，只要当前没有走到（n,m）点且下

30、一节点未访问过，则搜索。,program zu; const dx:array1.8 of shortint=(2,1,-1,-2,-2,-1,1,2); dy:array1.8 of shortint=(1,2,2,1,-1,-2,-2,-1); var n,m,x,y:longint; g:array-2.22,-2.22 of boolean; i,ans:longint; procedure go(a,b:longint); begin if (a=n)and(b=m) then inc(ans) else begin if (a+1=n)and ga+1,b=true then go(a+1,b); if (b+1=m)and ga,b+1=true then go(a,b+1); end; end;,begin assign(input,zu.in); reset(input); assign(output,zu.ou