趣谈数据结构（十一）
    　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　 福州一中 陈颖

　　在前两讲中，我们介绍了两种图的遍历方法， 深度优先搜索遍历与广度优先搜索遍历，这两种遍历算法在实际编程中被广泛地采用。本讲对深度优先搜索算法的应用作进一步的讨论。
　　深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放每次生成的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，继续生成新的结点入栈，直到搜索到目标结点或栈空为止。

　　具体算法：
　　⒈把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。
　　⒉如果OPEN为一空表，则搜索失败退出。
　　⒊取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。
　　⒋如果结点ｎ的深度等于最大深度，则转向２。
　　⒌否则，扩展结点ｎ，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向ｎ的返回指针；如果没有后裔，则转向２。
　　⒍如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向２。

　　例如　八数码难题--已知８个数的起始状态如图1（ａ），要得到目标状态为图1(ｂ）。
　　　　　　　２　８　３　　　　　　　　　　　　　１　２　３
　　　　　　　１　６　４　　　　　　　　　　　　　８　■　４
　　　　　　　７　■　５　　 　　　　　　　　　　 ７　６　５
　　　　　　　　（ａ）　　　　　　　　　　　　　　　（ｂ）
　　　　　　　　　　　　　　　　　图　1
　　求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图2的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为５。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。

　　　
　　　　　　　　　　　　　　　　　　　　　 图 2
　　程序实现有两种方式--递归与非递归。

　　一、递归
　　递归过程为：
　　Procedure DEF-GO(step)
　　　for i:=1 to max do
　　　　if 子结点符合条件 then
　　　　　产生新的子结点入栈；
　　　　　　if 子结点是目标结点 then 输出
　　　　　　　else DEF-GO(step+1)；
　　　　　　栈顶结点出栈；
　　　　　endif；
　　　　enddo；
　　主程序为：
　　Program DFS；
　　　初始状态入栈；
　　　DEF-GO(1)；

　　二、非递归
　　Program DEF(step)；
　　step:=0；
　　repeat
　　step:=step+1；
　　j:=0；p:=false
　　　repeat
　　　　j:=j+1；
　　　　if 结点符合条件 then
　　　　　产生子结点入栈；
　　　　　　if 子结点是目标结点 then 输出
　　　　　　　else p:=true；
　　　　　else
　　　　　　if j>=max then 回溯 p:=false；
　　　　endif；
　　　until p=true；
　　until step=0；
　　回溯过程如下：
　　Procedure BACK；
　　　step:=step-1；
　　　if step>0 then 栈顶结点出栈
　　　　else p:=true；

　 例1 设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如下:

　　　　　　
　　　　　　　　　　　　　　图　3　
　　求最佳安排使效益最高。
　　分析:每人选择五项工作中的一项，在各种选择的组合中，找到效益最高的的一种组合输出。
　　算法步骤:
　　⒈数据库：用数组ｆ构成堆栈存放产生的结点；数组ｇ存放当前最高效益结点的组合；数组ｐ作为结点是否选择过的标志位。
　　⒉结点的产生：
　　(1)选择ｐ(i)=0的结点；
　　(2)判断效益是否高于ｇ记录结点的效益，是高于则更新ｇ数组及最高效益值。
　　⒊搜索策略: 深度优先搜索。
　　源程序如下:
　　program ex1;
　　const
　　　data: array [1..5,1..5] of integer
　　　　　=((13,11,10,4,7),(13,10,10,8,5),(5,9,7,7,4),
　　　　　　(15,12,10,11,5),(10,11,8,8,4));
　　var
　　　i,max: integer;
　　　f,g: array [1..5] of integer;
　　　p: array [1..5] of integer;
　　procedure go(step,t: integer);{选择最佳效益结点的组合}
　　var
　　　i: integer;
　　begin
　　　for i:=1 to 5 do
　　　　if p[i]=0 then begin
　　　　　f[step]:=i;
　　　　　p[i]:=1;
　　　　　t:=t+data[step,i];
　　　　　if step<5 then go(step+1,t)
　　　　　else
　　　　　if t>max then begin
　　　　　　max:=t;
　　　　　　g:=f;
　　　　　end;
　　　　　t:=t-data[step,i];
　　　　　p[i]:=0;
　　　　end;
　　end;
　　begin
　　　max:=0;
　　　for i:=1 to 5 do p[i]:=0;
　　　go(1,0);
　　　writeln;
　　　for i:=1 to 5 do write(chr(64+i),':J',g[i],'':3);
　　　writeln;
　　　writeln('supply: ',max);
　　end.

　 　　　　　　

   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有