常用算法——深度优先搜索(degree first serch) 吴孝燕 一、 深度优先搜索的基本思路 把一个具体的问题抽象成了一个图论 的模型——树（如图）。 状态对应着结点，状态之间的关系 （或者说决策方案）对应着边。这样 的一棵树就叫搜索树。 （一）基本思路 1、在每个阶段的决策时，采取能深则深的原则试探所有可行的方案，一旦深入一层则保存当前操作引起的状态。 2、一旦试探失败，为了摆脱当前失败状态，采取回到上一阶段尝试下一方案的策略（回溯策略）；或者在求解所有解时，求得一个解后，回溯到上一阶段尝试下一方案，以求解下一个解。 3、在各个阶段尝试方案时，采取的是穷举的思想。 （二）引题 【例 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; 子程序 procedure try(i:integer); var k:integer; begin if i=n then begin if totk) 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 所...
