深度优先搜索算法_Pascal.ppt

深度优先搜索算法,深度优先搜索法有两大基本特点:1对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点；2深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点，先把产生的数入栈，产生栈顶（即深度最大的元素）子结点，子结点产生以后，出栈，再产生栈顶子结点。,一递归算法：递归过程为：proceduretry(i);forr:=1tomaxrdo(maxr是产生式规则数)beginif子结点mr符合条件thenbegin产生的子结点mr压入栈；if子结点mr是目标结点then输出elsetry（i+1）;栈顶元素出栈（删去mr）；end;end;*main*programdfs;初始栈；try（1）；,n,子结点mr是目标结点,n,y,try(i),二非递归算法programdfs(dep);dep:=0;repeatdep:=dep+1;j:=0;p:=false;repeatj:=j+1;if子结点mr符合条件then产生子结点mr并将其记录if子结点是目标then输出并出栈(更新j)elsep:=true;elseifjmaxjthen回溯elsep:=false;untilp=true;untildep=0;,其中回溯过程如下：procedurebacktracking;dep:=dep-1;ifdep0then取回栈顶元素elsep:=true;,y,n,mr符合条件,子节点是目标,y,n,y,n,j=maxj,如图：a点有一个过河卒，需要走到目标b点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图的c点），该马所在的点和所有串跳跃一步可达的点称为对方马的控制点。例如图中c点上的马可以控制9个点（图中的p1，p2，p8和c）。卒不能通过对方马的控制点。棋盘用坐标表示，a点（0，0）、b点（n,m）（n,m为不超过20的整数，并由键盘输入），同样马的位置坐标是需要给出的（约定：ca,同时cb）。现在要求你计算出卒从a点能够到达b点的路径的条数。,数据结构：卒移动方向mov1.2,1.212马控制范围move0.8,1.2012345678,现有n个数字(n0,y,n,exit,输出结果到outputhave:=false,pass检验第2组第k组数是否合格，如合格则输出其中bb是b的拷贝,将z1zm中数字计算出值赋给e,i,2tok,j,mdownto1,gmod10,g,gdiv10,bbh:=bbh-1,ifg0thenexit,骑士游历问题：在6*6的国际象棋上的某一位置上放置一“马”，然后采用象棋中“马走日字”的规则，要求该“马”能不重复地走完36个格子，试编写程序解决这个问题。,数组a,设置8个方向变化,board1,1,1,try(1,1,2,q),y,n,q,输出无解信息,初始化board,输出结果,try(x,y,i,q)表示对（x,y）位置作为第i步向前试探的过程。若试探成功，逻辑变量q的值为true，否则为false,k,kk+1q1false,not(q1),0,q1or(k=8),ux+a1,kvy+a2,k,y,n,boardu,vi,合格,in*n,try(u,v,i+1,q1),y,n,boardu,v:=0,q1:=true,board=0,y,n,y,n,q:=q1,试编程将1至n（n10）的自然数序列1，2，n重新排列，使任意相邻两数之和为素数。例如n3时有两种排列方案123、321满足要求。输入要求：n从键盘输入。输出要求：每行输出一种排列方案（相邻数字之间用空格分隔）。最后一行输出排列方案总数。例如输入3输出1233212,数据初始化,have,true,made(1),y,n,have,输出无解信息,i,1ton,pass1(i,t)andyn(at-1+bt),at:=i,y,n,t0,dec(numc),ans(lev):=c,search,inc(numc),dec(lev),迷宫问题,-回溯法,入口,出口,输入：1.迷宫