程序设计：深度优先搜索算法

1、深度优先搜索算法教程例1 有A、B、C、D、E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有可能方案，当然是让每个人都满意。（如下图所示）分析 这个问题中喜爱的书是随机的，没有什么规律，所以用穷举法比较合适。为编程方便，用1、2、3、4、5分别表示这五本书。这五本书的一种全排列就是五本书的一种分法。例如54321表示第5本书（即E）分给张，第4本书（即D分给王，）第1本书（即A分给钱）。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。算法设计：1、 产生5个数字的一个全排列；2、 检查是否符合“喜

2、爱书表”的条件，如果符合就打印出来。3、 检查是否所有排列都产生了，如果没有产生完，则返回1。4、 结束。算法改进：因为张只喜欢第3、4本书，这就是说，1* * * *一类的分法都不符合条件。所以改进后的算法应当是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立即换一个，符合条件后，再产生下一个数。因为从第i本书到第i+1本书的寻找过程是相同的，所以可以用递归算法。算法如下：procedure try(i); 给第I个同学发书begin for j:=1 to 5 dobeginif 第i个同学分给第j本书符合条件 then begin记录第i个数; 即j值if i=5 th

3、en 打印一个解 else try(i+1);删去第i个数字endendend;具体如下：递归算法program zhaoshu;const like:array1.5,1.5 of 0.1 =(0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1); name:array1.5 of string5 =('zhang','wang','liu','zhao','qian');var book:array1.5 of 0.5; flag:set of 1

4、.5; c:integer;procedure print; var i:integer; begin inc(c); writeln('answer',c,':'); for i:=1 to 5 do writeln(namei:10,':',chr(64+booki); end;procedure try(i:integer);var j:integer;begin for j:=1 to 5 do if not(j in flag) and (likei,j>0) then begin flag:=flag+j; booki:=j;

5、if i=5 then print else try(i+1); flag:=flag-j; booki:=0; end;end;=main=begin flag:=; c:=0; try(1); readln;end.C语言代码：#include<stdio.h>#include<stdlib.h>int like55=0,0,1,1,0,1,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,1;char name510="zhang","wang","liu","zhao&q

6、uot;,"qian"int flag5=1,1,1,1,1;int book5,c=0;void print() int i; c+; printf("answer %d:",c); for(i=0;i<=4;i+) printf("%s:%c ",namei,65+booki); printf("n");void dsf(int i) int j; for(j=0;j<=4;j+) if(flagj&&likeij) flagj=0;booki=j; if(i=4) print();

7、 else dsf(i+1); flagj=1;booki=0; int main() dsf(0); system("pause"); return 0; 非递归算法program path;dep:=0; dep为栈指针，也代表层次repeat dep:=dep+1; r:=0; p:=false; repeat r:=r+1;if 子节点mr符合条件 then 产生新节点并存于dep指向的栈顶； if 子节点是目标 then 输出并退出（或退栈） else p:=true;else if r>=maxr then 回溯 else p:=flase; e

8、ndif;until p:=true;until dep=0;其中回溯过程如下：procedure 回溯； dep:=dep-1; if dep=0 then p:=true else 取回栈顶元素（出栈）；具体如下：非递归算法program zhaoshu2;uses crt;const like:array1.5,1.5 of 0.1 =(0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1); name:array1.5 of string5 =('zhang','wang','liu&

9、#39;,'zhao','qian');var book:array0.5 of 0.5; flag:set of 1.5; c,dep,r:longint; p:boolean;f:text;procedure print; var i:integer; begin inc(c); writeln(f,'answer',c,':'); for i:=1 to 5 do writeln(f,namei:10,':',chr(64+booki); end;procedure back;begin dep:=dep-1

10、; if dep=0 then p:=true else begin r:=bookdep; flag:=flag-r; end;end;=main=begin assign(f,'d:wuren.pas'); rewrite(f); clrscr; flag:=; c:=0; dep:=0; repeat dep:=dep+1; r:=0; p:=false; repeat r:=r+1; if not(r in flag) and (likedep,r>0)and (r<=5)then begin flag:=flag+r; bookdep:=r; if dep

11、=5 then begin print;inc(dep);back; end else p:=true; end else if r>=5 then back else p:=false until p=true; until dep=0; close(f);end.上述程序运行产生结点的过程如下图所示： 结点旁的编号是结点产生的先后顺序。从产生的顺序可以看出，深度越大的结点越先进行扩展，即先产生它的子结点。例如，有了结点（3）和（31）后，并不是继续产生（3）的子结点，而是先产生（31）的子结点（312）。这是由于（31）的深度是2，（3）的深度是1，（31）的深度大，所以先

12、扩展。同前边图的深度优先遍历联系起来这种在搜索过程中，深度大的节点先进行扩展的算法，称之为深度优先搜索法。简称DFS法。（Depth_First_Search）。深度优先搜索的特点：(1) 对已产生的节点按深度排序,深度大的先得到扩展，即先产生它的子节点。(2) 深度大的节点是后产生的，但先得到扩展，即“后产生，先扩展”，因此，采用堆栈作为该算法的数据结构。深度优先搜索的基本思想：1、把初始状态赋到state(1)中，即初状态入栈，并初始化指针1>object, 1>top。（注释：state(x)表示节点x的状态，state(1)表示初始状态，object表示作扩展的节点。Top

13、表示由节点object扩展的子节点。）2、分别用waymax种途径扩展object的子节点。 (1)从途径1开始扩展新节点 1>waynum。（注释：waymax表示所有可能扩展子节点的途径的总数目，waynum表示所选途径编号） （2）判断waynum途径可行吗？（即可否扩展新节点）若不行，转2（5）。 （3）对新节点设父指针，新状态入栈。top+1>top，object>father(top)，state(object)经途径waynum改变后的新状态>state(top)中。(注释：father(x)节点x 的父节点的标号。) （4）top是目标节点吗？是，则调用

14、打印结果子程序print打印结果路径。若只要求一个方案则结束，否则，让节点top出栈再继续执行下一步。 （5）选择下一条路径，即waynum+1>waynum，若waynum<=waymax，则转2(2)。3、选择用来扩展的新节点。 （1）若object<top，（即object有子节点）则转3(3)。 （2）top出栈，top-1>top，若top=0（栈空则结束），若top已扩展，再转3(2)。 （3）top>object，若object已规定深度，则转3(2)。否则转2(1)。深度优先搜索Pascal语言程序：program dfs(input,output

15、);const n=扩展节点估计数；waymax=扩展节点途径数；var state, father：array1.n of integer;top, object, waynum：integer;procedure print(v：integer);beginwhile v>0 dobegin write(statev, '<='); v：=fathervend;end;begin(第一步)state1：=初状态；object： =1；top:=1; father1:=0;while top>0 dobeginfor waynum:=1 to waymax

16、do （第二步） begin if way(maxnum) 可行 then begin top:=top+1; fathertop:=object; statetop:=新状态； if top 是目标节点 then begin print(top); top:=top-1; end; end; end; if top>object then object:=top（第三步）else repeat top:=top-1; object:=top until top<>fathertop+1;end;end.深度优先搜索的基本算法如下：一、递归算法递归过程为：procedure

17、DFS_TRY(i);for r:=1 to maxr do if 子结点mr符号条件 then 产生的子结点mr压入栈； if 子结点mr是目标结点 THEN 输出 ELSE DFS_TRY（I+1）；栈顶元素出栈（删去mr）;ENDIF；ENDDO；主程序为：PROGRAM DFS；初始状态入栈；DFS_TRY（1）；二、非递归算法：PROGRAM DFS（DEP）；DEP：=0；REPEAT DEP：=DEP+1；J：=0；P：=FALSE；REPEAT J：=J+1；IF MR 符合条件 THEN产生子结点MR并将其记录；IF 子结点是目标 THEN 输出并出栈 ELSE P：=TRU

18、E；ELSE IF J>=MAXJ THEN回溯 ELSE P：=FALSE；ENDIF；UNTIL P=TRUE；UNTIL DEP=0；其中回溯过程如下：PROCEDURE BACKTRACKING；DEP：=DEP-1；IF DEP>0 THEN 取回栈顶元素 ELSE P：=TRUE；不同问题的深度优先搜索基本算法是一样的，但在具体处理方法上，编程的技巧上，不尽相同，甚至会有很大差别。比如例1的解法还可以这样来设计：从表中看出，赵同学只喜爱D一本书，无其他选择余地。因此可以在搜索前就确定下来。为了编程方便，把赵钱二人位置互换，这样程序只需对张王刘钱四人进行搜索。另外，发现表

19、示“喜爱书表”的数组有多个0，为减少不必要的试探，我们改用链表来表示。例如第3位同学的链表是：LIKE（3，0）=2，表示他喜爱的第一本书编号是3，最后LIKE（3，3）=0，表示3是最后一本喜爱的书。深度优先搜索算法小结 1可以用深度优先搜索法处理的问题是各种各样的。有的搜索深度是已知和固定的，有的是未知的，有的搜索深度是有限制的，但达到目标的深度不定，但我们也看到，无论问题的内容、性质、求解要求如何不同，但它们的程序结构都是相同的，即都是第四节中描述的算法结构，不相同的仅仅是存储结点的数据库结构、产生规则和输出要求。2深度优先搜索法有递归和非递归两种设汁方法一般地，当搜索深度较小、问题递归形式较明显时，用递归方法设计较好，它可以使程序结构更简捷易懂。但当搜索深度较大，由于系统堆栈容量的限制，递归易产生溢出，用非递归设计方法较合适。3探度优先搜索法有广义和狭义两种理解。广义的理解是只要最新产生的结点(即深度最大的结点)先进行扩展的搜索法，就称为深度优先搜索。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点两种情况，而狭义的理解是，仅仅指保留全部产生的结点的算法。本书取前一种广义的理解。不保留全部结点的算法，属于一般的回溯算法范畴。保留全部结点的算法，实