2024年5月11日发(作者：华为手机强行恢复出厂)
常用算法——深度优先搜索(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 tot else begin 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
发布者：admin，转转请注明出处：http://www.yc00.com/xitong/1715384218a2609929.html
评论列表（0条）