文档文库

手机版

投诉建议

首页 > 深度优先搜索算法

深度优先搜索算法

发布时间：2012-04-12 21:01:33 来源：文档文库

小中大

字号：

手机查看

深度优先搜索算法教程

[例1] 有A、B、C、D、E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有可能方案，当然是让每个人都满意。（如下图所示）

[分析] 这个问题中喜爱的书是随机的，没有什么规律，所以用穷举法比较合适。

为编程方便，用1、2、3、4、5分别表示这五本书。这五本书的一种全排列就是五本书的一种分法。例如54321表示第5本书（即E）分给张，第4本书（即D分给王，）……第1本书（即A分给钱）。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。

[算法设计]：

1、产生5个数字的一个全排列；

2、检查是否符合“喜爱书表”的条件，如果符合就打印出来。

3、检查是否所有排列都产生了，如果没有产生完，则返回1。

4、结束。

[算法改进]：因为张只喜欢第3、4本书，这就是说，1* * * *一类的分法都不符合条件。所以改进后的算法应当是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立即换一个，符合条件后，再产生下一个数。因为从第i本书到第i+1本书的寻找过程是相同的，所以可以用递归算法。算法如下：

procedure try(i); {给第I个同学发书}

begin

for j:=1 to 5 do

begin

if 第i个同学分给第j本书符合条件 then

begin

记录第i个数; {即j值}

if i=5 then 打印一个解 else try(i+1);

删去第i个数字

end

end;

具体如下：

◆递归算法

program zhaoshu;

const

like:array[1..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:array[1..5] of string[5] =('zhang','wang','liu','zhao','qian');

var

book:array[1..5] of 0..5;

flag:set of 1..5;

c:integer;

procedure print;

var i:integer;

begin

inc(c);

writeln('answer',c,':');

for i:=1 to 5 do

writeln(name[i]:10,':',chr(64+book[i]));

end;

procedure try(i:integer);

var j:integer;

begin

for j:=1 to 5 do

if not(j in flag) and (like[i,j]>0) then

begin

flag:=flag+[j]; book[i]:=j;

if i=5 then print else try(i+1);

flag:=flag-[j]; book[i]:=0;

end;

{=====main====}

begin

flag:=[]; c:=0;

try(1);

readln;

end.

C语言代码：

#include

int like[5][5]={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 name[5][10]={"zhang","wang","liu","zhao","qian"};

int flag[5]={1,1,1,1,1};

int book[5],c=0;

void print()

{ int i;

c++;

printf("answer %d:",c);

for(i=0;i<=4;i++)

printf("%s:%c ",name[i],65+book[i]);

printf("\n");

}

void dsf(int i)

{

int j;

for(j=0;j<=4;j++)

if(flag[j]&&like[i][j])

{ flag[j]=0;book[i]=j;

if(i==4) print();

else dsf(i+1);

flag[j]=1;book[i]=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;

endif;

until p:=true;

until dep=0;

其中回溯过程如下：

procedure 回溯；

dep:=dep-1;

if dep=0 then p:=true else 取回栈顶元素（出栈）；

具体如下：

◆非递归算法

program zhaoshu2;

uses crt;

const

like:array[1..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:array[1..5] of string[5]

=('zhang','wang','liu','zhao','qian');

var book:array[0..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,name[i]:10,':',chr(64+book[i]));

end;

procedure back;

begin

dep:=dep-1;

if dep=0 then p:=true

else begin r:=book[dep]; 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 (like[dep,r]>0)and (r<=5)then

begin

flag:=flag+[r]; book[dep]:=r;

if dep=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）的深度大，所以先扩展。{同前边图的深度优先遍历联系起来}

这种在搜索过程中，深度大的节点先进行扩展的算法，称之为深度优先搜索法。简称DFS法。（Depth_First_Search）。

深度优先搜索的特点：

(1) 对已产生的节点按深度排序,深度大的先得到扩展，即先产生它的子节点。

(2) 深度大的节点是后产生的，但先得到扩展，即“后产生，先扩展”，因此，采用堆栈作为该算法的数据结构。

深度优先搜索的基本思想：

1、把初始状态赋到state(1)中，即初状态入栈，并初始化指针1––>object, 1––>top。

（注释：state(x)表示节点x的状态，state(1)表示初始状态，object表示作扩展的节点。Top表示由节点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是目标节点吗？是，则调用打印结果子程序print打印结果路径。若只要求一个方案则结束，否则，让节点top出栈再继续执行下一步。

（5）选择下一条路径，即waynum+1––>waynum，若waynum<=waymax，则转2––(2)。

3、选择用来扩展的新节点。

（1）若object，（即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);

const n=扩展节点估计数；waymax=扩展节点途径数；

var state, father：array[1..n] of integer;

top, object, waynum：integer;

procedure print(v：integer);

begin

while v>0 do

begin write(state[v], '<==');

v：=father[v]

end;

begin (第一步)

state[1]：=初状态；

object： =1；top:=1; father[1]:=0;

while top>0 do

begin

for waynum:=1 to waymax do （第二步）

begin

if way(maxnum) 可行 then

begin

top:=top+1; father[top]:=object;

state[top]:=新状态；

if top 是目标节点 then

begin

print(top); top:=top-1;

end;

if top>object then object:=top （第三步）

else repeat top:=top-1; object:=top until top<>father[top+1];

end;

end.

深度优先搜索的基本算法如下：

一、递归算法

递归过程为：

procedure 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：=TRUE；

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一本书，无其他选择余地。因此可以在搜索前就确定下来。为了编程方便，把赵钱二人位置互换，这样程序只需对张王刘钱四人进行搜索。

另外，发现表示“喜爱书表”的数组有多个0，为减少不必要的试探，我们改用链表来表示。例如第3位同学的链表是：LIKE（3，0）=2，表示他喜爱的第一本书编号是3，最后LIKE（3，3）=0，表示3是最后一本喜爱的书。

深度优先搜索算法小结

1．可以用深度优先搜索法处理的问题是各种各样的。有的搜索深度是已知和固定的，有的是未知的，有的搜索深度是有限制的，但达到目标的深度不定，但我们也看到，无论问题的内容、性质、求解要求如何不同，但它们的程序结构都是相同的，即都是第四节中描述的算法结构，不相同的仅仅是存储结点的数据库结构、产生规则和输出要求。

2．深度优先搜索法有递归和非递归两种设汁方法．一般地，当搜索深度较小、问题递归形式较明显时，用递归方法设计较好，它可以使程序结构更简捷易懂。但当搜索深度较大，由于系统堆栈容量的限制，递归易产生溢出，用非递归设计方法较合适。

3．探度优先搜索法有广义和狭义两种理解。广义的理解是只要最新产生的结点(即深度最大的结点)先进行扩展的搜索法，就称为深度优先搜索。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点两种情况，而狭义的理解是，仅仅指保留全部产生的结点的算法。本书取前一种广义的理解。不保留全部结点的算法，属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生—结点之间的搜索树，因此也属于图搜索算法的范畴。

4．不全部保留结点的深度优先搜索法，由于把扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少。所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。

5．从城市路径的输出结果可看出，深度优先搜索法找到的第一个解，不一定是最优解。例如城市路径的最优解应是COST=13，但第一个解却是COST＝17。

如果要求出最优解，一种办法是用第九章将要介绍的动态规划法，另一种办法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面巳记录的值加以比较，保留其中最优解。等全部搜索完成后，再把保留的最优解输出。

练习题：
1、八皇后问题：现要将八个皇后放置在8×8的棋盘上，要求任意两个皇后不能在同一行、同一列、同一条对角线上，打印出皇后的放置位置。

2、求出从1..N这N个数中取M个数的所有组合（M<=N）

3、求出从1..N这N(0个数中取M个数的所有排列(M<=N)

4、仅含有大写字母的的字符串“BFY”称为是“良序”的，因为它的字母是按ASCII码严格地从小到大排列的，而“BAY”就不是。请编一程序，从键盘输入自然数n(2<=n<=26)后，打印出所有长度为n的“良序”字符串。