深度优先搜索搜索.ppt

《深度优先搜索搜索.ppt》由会员分享，可在线阅读，更多相关《深度优先搜索搜索.ppt（51页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、搜索算法搜索算法从问题的某一种可能出发从问题的某一种可能出发,搜索从这种情况出发所能达搜索从这种情况出发所能达到的所有可能到的所有可能,当这一条路走到当这一条路走到“尽头尽头 ”而没达到目的地而没达到目的地的时候的时候,再倒回再倒回上一个上一个出发点出发点,从另一个可能出发从另一个可能出发,继续搜继续搜索索.这种不断这种不断“倒回倒回 一步一步 寻找解的方法寻找解的方法,称作称作 回溯法回溯法 .回溯即是较简单、较常用的搜索策略回溯即是较简单、较常用的搜索策略,实质就是一种实质就是一种搜索策略搜索策略.AB12345678910从从A到到B的路线的路线:A-4-6-B如如:找一条从找一条从A到

2、到B的路线的路线深度优先搜索1.算法思想深度优先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止。2.深度优先搜索的基本算法结构（1）递归实现。Proceduredfs_try(i);Fori:=1tomaxrdobeginif子结点mr符合条件thenbegin产生的子结点mr入栈；if子结点mr是目标结点then输出；elsedfs_try(i+1);栈顶元素出栈；End;End;1.、问题描述

3、问题描述 学校放暑假时，信息学辅导教师有学校放暑假时，信息学辅导教师有n本书要分给参加培训的本书要分给参加培训的n个学生。如：个学生。如：A，B，C，D，E共共5本书要分给参加培训的张、刘、王、李、孙本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。ABCDE张YY王YY刘YY孙

4、Y李YY输入格式：第一行一个数输入格式：第一行一个数n（学生的个数，书的数量）（学生的个数，书的数量）以下共以下共n行，每行行，每行n个个0或或1（由空格隔开），第（由空格隔开），第I行数据表示第行数据表示第i个同学对个同学对所有书的喜爱情况。所有书的喜爱情况。0表示不喜欢该书，表示不喜欢该书，1表示喜欢该书。表示喜欢该书。输出格式：依次输出每个学生分到的书号。输出格式：依次输出每个学生分到的书号。样例：样例：输入：book.in50011011000011000001001001输出：book.out31245分析分析:a:array1.maxn,1.maxnof 0.1;b:array1.

5、maxnof integer;方案方案:bi是第是第i个人借第个人借第bi本书本书 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;标记第标

6、记第j本数已被借本数已被借;try(i+1);删除书的被借标志删除书的被借标志;end;end;proceduretry(i:integer);varj:integer;beginifi=n+1thenprintelseforj:=1tondoifbookjand(ai,j=1)thenbeginbi:=j;bookj:=false;try(i+1);bookj:=true;bi:=0;end;end;procedureprint;vari:integer;beginfori:=1ton-1dowrite(bi,);writeln(BN);end;主程序主程序:beginfillchar(b,

7、sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(ai,j);try(1);End.2.、问题描述问题描述 house11.txt 骑士的游历骑士的游历1设有下图所示的一个棋盘，在棋盘上的设有下图所示的一个棋盘，在棋盘上的A点有一个中国象棋马，并约定点有一个中国象棋马，并约定马走的规则：马走的规则：1、马只向右走；、马只向右走；2、马走、马走“日日“字。字。找出所有从找出所有从A到到B的路径。的路径。一种方法：一种方法：(2 1)(4 0)(5 2)(6 0)(7 2)(8

8、4)1112345671231分析：分析：1、马跳的方向：马跳的方向：x:array1.4,1.2of integer=(1,-2),(2,-1),(2,1),(1,2);4个方向横向和纵向的增量。个方向横向和纵向的增量。2、记录马经过的位置坐标、记录马经过的位置坐标 a:array0.8,1.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=

9、0)and(ai-1,1+xj,1=0)and(ai-1,2+xj,2(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;记录路径方向记录路径方向 dx,dy:array1.8of integer;方向位移方向位移 8个方向的位移个方向的位移:dx1:=0;dy1:=-1;dx2:=

10、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;读入数据读入数据:坐标坐标procedurereaddata;beginassign(input,a.in);reset(input);readln(n);fori:=1tondoforj:=1tondobeginread(aj,i);i:纵坐标;j:横坐标cj,i:=0;end;close(input);递归算法递归算法:procedure try(i:integer);搜索第搜索第i步应到达的位置

11、步应到达的位置 var k:integer;begin for k:=1 to 8 do begin if(x+dxk=1)and(x+dxk=1)and(y+dyk,(,x,y,);end;writeln;end;主程序主程序:begin readdata;x:=1;y:=1;try(1);end.4、覆盖问题。、覆盖问题。(li1.txt)边长为N（偶数）的正方形，用N*N/2个长为2宽为1的长方形将它全部覆盖。编程打印所有覆盖方法。当N=4时几种覆盖方法的打印格式举例如下：12241334566857781122334455667788输出:12241122133433445668556

12、657787788输入: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.如果列号如果

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

14、,k:=i;格子（j,k）用编号i覆盖if(jn)and(aj+1,k=0)then正下方格子未覆盖，用i覆盖beginaj+1,k:=i;ifi*2n*nthen最大编号为n*n/2try(i+1)elseprint;aj+1,k:=0;回溯end;if(kn)and(aj,k+1=0)then右方方格子未覆盖，用i覆盖beginaj,k+1:=i;ifi*2n*nthentry(i+1)elseprint;aj,k+1:=0;回溯end;aj,k:=0;回溯end;procedureprint;vari,j:integer;beginwriteln;inc(t);fori:=1tondob

15、eginforj:=1tondowrite(ai,j);writeln;end;end;主程序主程序：beginreadln(n);ifodd(n)or(n0)thenwriteln(Error!)elsetry(1);end.5、黑白棋子、黑白棋子 现有现有N个黑棋和个黑棋和N个白棋，将这个白棋，将这2N各棋子放入一个各棋子放入一个N*N棋盘，使每行每列都有一个黑棋和一个白棋。求满足棋盘，使每行每列都有一个黑棋和一个白棋。求满足上述要求的布棋方案有多少种。上述要求的布棋方案有多少种。(li2.txt)N=2时，有以下两种放置方法：时，有以下两种放置方法：bwwbwbbw输出：const ma

16、x=10;type bhxing=array1.maxof shortint;var b:array1.max,1.maxof boolean;棋盘能否可用棋盘能否可用 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(

17、b,sizeof(b),true);procedure try(x:integer);放置第放置第x行的白黑棋子行的白黑棋子 var i,j:integer;begin if x=n+1 then 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

18、and heij then begin bx,j:=false;heij:=false;hhx:=j;try(x+1);bx,j:=true;heij:=true;回溯：释放黑棋的位置回溯：释放黑棋的位置 end;bx,i:=true;baii:=true;回溯：释放白棋的位置回溯：释放白棋的位置 end;end;procedure print(bh:bhxing);var i:integer;begin for i:=1 to n do write(bhi);write();end;主程序：beginfillchar(bai,sizeof(bai),true);fillchar(hei,si

19、zeof(hei),true);fillchar(b,sizeof(b),true);readln(n);try(1);writeln(t);end.6、数字排列、数字排列(li3.txt)在一个在一个N*N的棋盘上（的棋盘上（1=n=100),填入填入1,2,.,n*n共共n*n个个数，使得任意两个相临的数之合为素数数，使得任意两个相临的数之合为素数例如：例如：n=2 时，有时，有:1 2 4 3n=41 2 11 1216 15 8 513 4 9 146 7 10 3分析：分析：逐行搜索逐行搜索1到到n*n之间的数放在（之间的数放在（i，j）处，依次判断他与）处，依次判断他与上方（上方（

20、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=true:i是素数，是素数，pi=false:i不是素数不是素数 b:array1.maxn,1.maxnof integer;坐标坐标 used:

21、array1.maxn*maxnof boolean;检查是否该数是否用过检查是否该数是否用过筛选法创建素数表筛选法创建素数表procedureprime;vari,j,s:integer;beginfillchar(p,sizeof(p),true);p1:=false;fori:=2to3*n div 2 do依次搜索素数i并筛掉是i倍数的数ifpithenbeginj:=2*i;whilej1 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(

22、x,y,dep:integer);递归搜索（递归搜索（x,y）处放）处放第第 dep 个个数数var i:integer;begin if dep=n*n+1 then print else 如果已放了如果已放了n*n个数，得出一种方法个数，得出一种方法 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);继续放当前行的

23、下一列继续放当前行的下一列 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;end;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)

24、;end.上机练习题1.添加自然数问题。（add.pas）要求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理:.不作任何处理;.在它的左边加上一个自然数,但该自然数不能超过原数的一半;.加上数后,继续按此规则进行处理,直到不能再加自然数为止.输入文件：add.in,一行，n的值。输出文件：add.out，一行，按照规则可产生的自然数个数。样例：输入文件：6满足条件的数为6162612636136输出文件6varn,i:integer;s:real;procedureqiu(x:integer);vark:integer;b

25、eginifx0thenbegins:=s+1;fork:=1toxdiv2doqiu(k)endend;beginreadln(n);s:=0;qiu(n);writeln(s)end.2.跳马问题。（jump.pas）在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。输出文件：jump.out，一行，路径条数。programjump;varh:array-1.7,-1.7ofinteger;a,b:array1.8ofinteger;i,j,num:integer;procedureprint;vari,j

26、:integer;beginnum:=num+1;ifnum=5thenbeginfori:=1to5dobeginforj:=1to5dowrite(hi,j:4);writeln;end;writeln;end;end;proceduretry(x,y,i:integer);varj,u,v:integer;beginforj:=1to8dobeginu:=x+aj;v:=y+bj;ifhu,v=0thenbeginhu,v:=i;ifi=1)and(i=1)and(j=5)thenhi,j:=0elsehi,j:=1;a1:=2;b1:=1;a2:=1;b2:=2;a3:=-1;b3:=

27、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点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动

28、的，并不是卒走一步马走一步。【输入输入】一行四个数据，分别表示B点坐标和马的坐标。【输出输出】一个数据，表示所有的路径条数。【样例输入样例输入】6 6 3 2【样例输出样例输出】17题目分析：本题是一道典型的深度优先搜索题目。需要处理好的细节有：1.读入“马”的坐标，控制好八个方向。2.在（n,m）棋盘上控制好“马”所能跳出的边界。3.按向下、向右两个方向搜索，只要当前没有走到（n,m）点且下一节点未访问过，则搜索。programzu;constdx:array1.8ofshortint=(2,1,-1,-2,-2,-1,1,2);dy:array1.8ofshortint=(1,2,2,1,

29、-1,-2,-2,-1);varn,m,x,y:longint;g:array-2.22,-2.22ofboolean;i,ans:longint;procedurego(a,b:longint);beginif(a=n)and(b=m)theninc(ans)elsebeginif(a+1=n)andga+1,b=truethengo(a+1,b);if(b+1=m)andga,b+1=truethengo(a,b+1);end;end;beginassign(input,zu.in);reset(input);assign(output,zu.out);rewrite(output);re

30、adln(n,m,x,y);fillchar(g,sizeof(g),true);gx,y:=false;fori:=1to8dogx+dxi,y+dyi:=false;ans:=0;go(0,0);writeln(ans);close(input);close(output);end.4.素数环问题。（sushu.pas）把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。请输出一种摆放方法。输出文件：sushu.out,一行，以1开始的20个整数，中间用一个空格隔开，最后一个数后面没有空格。programtt;vara:array1.20ofinteger;k:integer

31、;functionpd1(j,i:integer):boolean;beginpd1:=true;fork:=1toi-1doifak=jthenbeginpd1:=false;exit;end;end;functionpd2(x:integer):boolean;beginpd2:=true;fork:=2totrunc(sqrt(x)doifxmodk=0thenbeginpd2:=false;exit;end;end;functionpd3(j,i:integer):boolean;beginifi20thenpd3:=pd2(j+ai-1)elsepd3:=pd2(j+ai-1)andpd2(j+1);end;procedureprint;beginfork:=1to20dowrite(ak:4);writeln;end;proceduretry(i:integer);varj:integer;beginforj:=2to20dobeginifpd1(j,i)andpd3(j,i)thenbeginai:=j;ifi=20thenbeginprint;halt;endelsetry(i+1);ai:=0;end;end;end;beginfork:=1to20doak:=0;a1:=1;try(2);end.