t:=tae+(m-ee)/a;
tge:=(ee-tae*a)/(a+b);
t2:=tae+tge+(m-(tae+tge)*a)/b; if t if t writln(l:8:4,m:8:4,ee:8:4,t1:8:4,t3:8:4); if t1 writeln(l:8:4,m:=8:4,ee:8:4,t:8:4,t1:8:4); end. 深度优先搜索(degree first serch) 一、 深度优先搜索的基本思路 把一个具体的问题抽象成了一个图论 的模型——树（如图）。 状态对应着结点，状态之间的关系 （或者说决策方案）对应着边。这样 的一棵树就叫搜索树。 （一）基本思路 ?1、在每个阶段的决策时，采取能深则深的原则试探所有可行的方案，一旦深入一层则保存当前操作引起的状态。 ?2、一旦试探失败，为了摆脱当前失败状态，采取回到上一阶段尝试下一方案的策略（回溯策略）；或者在求解所有解时，求得一个解后，回溯到上一阶段尝试下一方案，以求解下一个解。 ?3、在各个阶段尝试方案时，采取的是穷举的思想。 （三）搜索过程 深度优先搜索的搜索过程类似树的先序遍历，也叫回溯法。搜索过程如下： 从源节点开始发现有一节点v，如果v还有未探测到的边，就沿此边继续探测下去，当节点v的所有边都被探测过，搜索过程将回溯到最初发现v点的源节点。这一过程一直进行到已发现从源节点可达的所有节点为止。这显然是一个递归过程。 为了在遍历过程中区分顶点是否被访问，往往可以引入一个数组，如以mark[1..n]作为标记。数组的元素取0和1，初值为0。当节点被访问时，与节点相应得数组元素为1，每次访问节点时，都得先检查它的标记值，找0值得节点访问，并深度继续。深度大的先得到扩展，具有“后产生先扩展”的特点，因此在数据结构上采用堆栈来存储（新节点入栈，节点不能扩展时，栈定出栈）。 （四）搜索特点 1、由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。 2、 深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。 3、 由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。 4、 深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。 - 21 - 5、 适用范围：适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。 （五）算法描述 1、算法数据结构描述： 深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN表，直到搜索到目标结点或OPEN栈空为止。具体算法如下： ① 把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。 ② 如果OPEN为一空表，则搜索失败退出。 ③ 取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。 ④ 如果结点ｎ的深度等于最大深度，则转向２。 ⑤ 否则，扩展结点ｎ，产生其全部子结点，把它们放入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 产生子结点入栈； - 22 - 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（ａ），要得到目标状态为图1(ｂ）。 ２ ８ ３ １ ２ ３ １ ６ ４ ８ ■ ４ ７ ■ ５ ７ ６ ５ （ａ） （ｂ） 图1 求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图2的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为５。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。 - 23 - 图 2 二、关于深度优先搜索的下界 对于许多问题，深度优先搜索查找的解答树可能含有无穷分支（深度优先搜索误入无穷分支就不可能找到目标节点），或者其深度可能至少要比某个可以接受的解答系列的已知上限还要深，或者能估计出目标节点不会超过多少层。为了避免可能太长的路径，给出一个节点扩展的最大深度，即深度界限D，任何节点达到了D，那么都将它们作为没有后继节点处理。如图2我们设置深度界限为５，如果我们不对它的深度进行限定，那么第5层以下可以产生大量的搜索节点，而目标节点可以在第5层找到。深度优先搜索是最常用的算法之一，而确定“深度D”是解题的关键，因为我们需要它消除不必要的搜索，提高搜索效率。 估算“深度D”的方法：无章可循，凭经验和大致的计算，在时间和空间允许的范围内，宁大勿小。 三、引题 【例1】选择最短路径。有如下所示的交通路线图，边上数值表示该道路的长度，编程求从1号地点到达7号地点的最短的路径长度是多少，并输出这个长度。 ? 数据结构 1、邻接矩阵表示图的连接和权值。A[I,j]=x,或者a[I,j]=maxint。B[i]表示结点i是否已经遍历过。 2、用变量min来保存最优解，而用tot变量保存求解过程中临时解（当前路径总长度）。 3、状态。Tot的值和结点的遍历标志值。 ? 程序结构 1、递归结构。 2、主程序中用try(1)调用递归子程序 。 3、子程序结构。 ?procedure try(I:integer); ?var k:integer; ?begin ? if 到达了终点 then begin 保存较优解；返回上一点继续求解（回溯）；end ? else ? begin ? 穷举从I出发当前可以直接到达的点k； ? if I到k点有直接联边 并且 k点没有遍历过 then ? then begin ? 把A[I,K]累加入路径长度tot;k标记为已遍历；try(k); ? 现场恢复； ? end; ? end; ? 子程序 - 24 - procedure try(i:integer); var k:integer; begin if i=n then begin if tot for k:=1 to n do if (b[k]=0) and (i<>k) and (a[i,k]<32700) then begin b[k]:=1;tot:=tot+a[i,k];try(k);b[k]:=0;tot:=tot-a[i,k]; end; end; end; ? 主程序数据输入 readln(fi,n); for i:=1 to n do begin for j:=1 to n do read(fi,a[i,j]); readln(fi); end; close(fi); ? 主程序预处理和调用子程序 tot:=0;min:=maxint;b[1]:=1; try(1); writeln('tot=',min); 四、递归程序结构框架 Procedure try(i:integer); Var k:integer; Begin If 所有阶段都已求解 then Begin 比较最优解并保存；回溯； end else begin for k:=i 深度可能决策范围；do begin 穷举当前阶段所有可能的决策（方案、结点）k if k方案可行 then begin 记录状态变化； try(i+1); 状态恢复（回溯）； end end; end; End; 五、 深度优先搜索的应用 【例2】分工问题：设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如下， 求最佳安排使效益最高。 - 25 -