深度优先搜索(pascal).ppt

深度优先搜索,从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,当这一条路走到“尽头”而没达到目的地的时候,再倒回上一个出发点,从另一个可能出发,继续搜索.这种不断“倒回一步寻找解的方法,称作回溯法.回溯即是较简单、较常用的搜索策略,实质就是一种搜索策略.,从A到B的路线:A-4-6-B,如:找一条从A到B的路线,算法思想深度优先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止。,深度优先搜索的基本算法结构（1）递归实现。Proceduredfs_try(i);Fori:=1tomaxrdobeginif子结点mr符合条件thenbegin产生的子结点mr入栈；if子结点mr是目标结点then输出；elsedfs_try(i+1);栈顶元素出栈；End;End;,1.、问题描述学校放暑假时，信息学辅导教师有n本书要分给参加培训的n个学生。如：A，B，C，D，E共5本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。,输入格式：第一行一个数n（学生的个数，书的数量）以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号。样例：输入：book.in50011011000011000001001001输出：book.out31245,分析:a:array1.maxn,1.maxnof0.1;b:array1.maxnofinteger;方案:bi是第i个人借第bi本书book:array1.maxnofboolean;booki:能否可以借第i本书,初始:true,一旦有人借了:就改为:false,算法设计:proceduretry(i:integer);搜索第i个人可以借的书bivarj:integer;beginifi=n+1then若书都借出，则输出结果elseforj:=1tondoif第i个人可以借第j本书thenbegin记录下bi;标记第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,sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(ai,j);try(1);End.,2.、骑士的游历设有下图所示的一个棋盘，在棋盘上的A点有一个中国象棋马，并约定马走的规则：1、马只向右走；2、马走“日“字。找出所有从A到B的路径。,一种方法：(21)(40)(52)(60)(72)(84),1,1,1,分析：1、马跳的方向：x:array1.4,1.2ofinteger=(1,-2),(2,-1),(2,1),(1,2);4个方向横向和纵向的增量。2、记录马经过的位置坐标a:array0.8,1.2ofinteger;第i步所在的位置，1：横坐标2：纵坐标,递归算法：proceduretry(i:integer);搜索第i步:try(1);varj:integer;beginforj:=1to4doif(ai-1,1+xj,1=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.maxnof0.1;记录迷宫坐标c:array1.maxn,1.maxnof0.1;访问标志:0:没走;1:已走b:array0.maxn*maxnofinteger;记录路径方向dx,dy:array1.8ofinteger;方向位移,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;,读入数据:坐标procedurereaddata;beginassign(input,a.in);reset(input);readln(n);fori:=1tondoforj:=1tondobeginread(aj,i);i:纵坐标;j:横坐标cj,i:=0;end;close(input);,递归算法:proceduretry(i:integer);搜索第i步应到达的位置vark:integer;beginfork:=1to8dobeginif(x+dxk=1)and(x+dxk=1)and(y+dyk,(,x,y,);end;writeln;end;,主程序:beginreaddata;x:=1;y:=1;try(1);end.,4、覆盖问题。(li1.txt)边长为N（偶数）的正方形，用N*N/2个长为2宽为1的长方形将它全部覆盖。编程打印所有覆盖方法。当N=4时几种覆盖方法的打印格式举例如下：,输出:12241122133433445668556657787788,输入: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.如果列号(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,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:=1tondobeginforj:=1tondowrite(ai,j);writeln;end;end;,主程序：beginreadln(n);ifodd(n)or(n0)thenwriteln(Error!)elsetry(1);end.,5、黑白棋子现有N个黑棋和N个白棋，将这2N各棋子放入一个N*N棋盘，使每行每列都有一个黑棋和一个白棋。求满足上述要求的布棋方案有多少种。N=2时，有以下两种放置方法：,输出：,constmax=10;typebhxing=array1.maxofshortint;varb:array1.max,1.maxofboolean;棋盘能否可用bai:array1.maxofboolean;能否放白棋子hei:array1.maxofboolean;能否放黑棋子bb:bhxing;白棋子列号hh：bhxing;黑棋子列号n:integer;t:int64;初始化：fillchar(bai,sizeof(bai),true);fillchar(hei,sizeof(hei),true);fillchar(b,sizeof(b),true);,proceduretry(x:integer);放置第x行的白黑棋子vari,j:integer;beginifx=n+1thenbeginprint(bb);print(hh);writeln;inc(t);exit;end;fori:=1tondo搜索第x行白棋应放置的列iifbx,iandbaiithenbeginbx,i:=false;baii:=false;bbx:=i;forj:=1tondo搜索第x行黑棋应放置的列jifbx,jandheijthenbeginbx,j:=false;heij:=false;hhx:=j;try(x+1);bx,j:=true;heij:=true;回溯：释放黑棋的位置end;bx,i:=true;baii:=true;回溯：释放白棋的位置end;end;,procedureprint(bh:bhxing);vari:integer;beginfori:=1tondowrite(bhi);write();end;,主程序：beginfillchar(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=n1thenifnot(pbx,y-1+k)thenok:=false;end;,proceduretry(x,y,dep:integer);递归搜索（x,y）处放第dep个数vari:integer;beginifdep=n*n+1thenprintelse如果已放了n*n个数，得出一种方法fori:=1ton*ndoifnot(usedi)andok(x,y,i)thenbeginbx,y:=i;usedi:=true;ify=nthentry(x+1,1,dep+1)如果当前是最右边一列，则转到下一行首列elsetry(x,y+1,dep+1);继续放当前行的下一列usedi:=false;释放标志end;end;,procedureprint;vari,j:integer;beginfori:=1tondobeginforj:=1tondowrite(bi,j:4);writeln;end;halt;end;,主程序：beginreadln(n);ifn=1thenbeginwriteln(NO);halt;end;prime;b1,1:=1;fori:=2ton*ndousedi:=false;used1:=true;try(1,2,2);writeln(NO);end.,上机练习题1.添加自然数问题。（add.pas）要求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理:.不作任何处理;.在它的左边加上一个自然数,但该自然数不能超过原数的一半;.加上数后,继续按此规则进行处理,直到不能再加自然数为止.输入文件：add.in,一行，n的值。输出文件：add.out，一行，按照规则可产生的自然数个数。,样例：输入文件：6满足条件的数为6162612636136输出文件6,varn,i:integer;s:real;procedureqiu(x:integer);vark:integer;beginifx0thenbegins:=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: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:=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点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【输入】一行四个数据，分别表示B点坐标和马的坐标。【输出】一个数据，表示所有的路径条数。【样例输入】6632【样例输出】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,-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);readln(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