《深优先搜索算法.pptx》由会员分享，可在线阅读，更多相关《深优先搜索算法.pptx（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、深度优先搜索法有两大基本特点:1 对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点；2 深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点，先把产生的数入栈，产生站顶（即深度最大的元素）子结点，子结点产生以后，出栈，再产生栈顶子结点。第1页/共32页一 递归算法：递归过程为：procedure TRY(i);For r:=1 to maxr do(maxr是产生式规则数)begin If 子结点MR 符合条件 THEN begin 产生的子结点MR压入栈；IF 子结点 MR是目标结点 THEN 输出 ELSE TRY（I
2、+1）;栈顶元素出栈（删去MR）；end;end;*main*program DFS;初始栈；TRY（1）；第2页/共32页For r:=1 to maxr do 子结点mr符合条件 Y 产生的子结点mr入栈输出Try(I+1)栈顶元素出栈（删去mr）N子结点mr是目标结点NYTry(I)第3页/共32页二 非递归算法program DFS(dep);dep:=0;repeat dep:=dep+1;j:=0;p:=false;repeat j:=j+1;if 子结点mr符合条件 then 产生子结点mr并将其记录 if 子结点是目标 then 输出并出栈(更新j)else p:=true;e
3、lse if jmaxj then 回溯 else p:=false;until p=true;until dep=0;第4页/共32页其中回溯过程如下：procedure backtracking;dep:=dep-1;if dep0 then 取回栈顶元素else p:=true;第5页/共32页Dep:=0Dep:=dep+1j:=0;p:=false;j:=j+1;产生子节点MR并记录回溯P:=false输出并出栈P:=trueUntil p=falseUntil dep=0YNMr符合条件子节点是目标YNYNJ=maxj第6页/共32页如图：A点有一个过河卒，需要走到目标B点。卒行走
4、的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图的C点），该马所在的点和所有串跳跃一步可达的点称为对方马的控制点。例如图中C点上的马可以控制9个点（图中的P1，P2，P8和C）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n,m）（n,m为不超过20的整数，并由键盘输入），同样马的位置坐标是需要给出的（约定：CA,同时CB）。现在要求你计算出卒从A点能够到达B点的路径的条数。第7页/共32页A12345678Y1P5P42P6P33马4P7P2XP8P1B(4,8)第8页/共32页现有n个数字(n0BI:=BI-1YNS0YNexit输出结果到OUTPU
5、THave:=falsePass检验第2组 第K组数是否合格，如合格则输出其中bb是b的拷贝将Z1Zm中数字计算出值赋给Ei2 to kjM downto 1g mod 10gg div 10bbh:=bbh-1If g0 then exit第14页/共32页骑士游历问题：在6*6的国际象棋上的某一位置上放置一“马”，然后采用象棋中“马走日字”的规则，要求该“马”能不重复地走完36个格子，试编写程序解决这个问题。第15页/共32页3241 X,Y5867-1-2-2-1122121-1-2-2-112数组A第16页/共32页设置8个方向变化Board1,11try(1,1,2,q)YNq输出无
6、解信息初始化board输出结果第17页/共32页Try(x,y,i,q)表示对（x,y）位置作为第i步向前试探的过程。若试探成功，逻辑变量q的值为true，否则为falseK kk+1 q1falseNot(q1)0Q1 OR (K=8)ux+a1,k vy+a2,kYNBoardu,v i合格in*nTry(u,v,i+1,q1)YNBoardu,v:=0Q1:=trueBoard=0YNYNQ:=Q1第18页/共32页试编程将1至N（N10）的自然数序列1，2，N重新排列，使任意相邻两数之和为素数。例如N3时有两种排列方案123、321满足要求。输入要求：N从键盘输入。输出要求：每行输出一
7、种排列方案（相邻数字之间用空格分隔）。最后一行输出排列方案总数。例如输入 3输出 1 2 3 3 2 1 2第19页/共32页数据初始化havetrueMade(1)YNhave输出无解信息第20页/共32页i1 to nPass1(I,t)and YN(at-1+bt)at:=iYNt0dec(numc)ans(lev):=csearchinc(numc)dec(lev)第27页/共32页迷宫问题-回溯法第28页/共32页入口出口第29页/共32页*输入：1.迷宫；2.入口；3.出口。第30页/共32页*.输出：1.搜索完的迷宫；2.行走路线；3.如没有可行路线，需给出提示。第31页/共32页感谢您的观看！第32页/共32页