文档介绍：蒁常用算法——深度优先搜索(degreefirstserch)艿吴孝燕羇***深度优先搜索的基本思路袃把一个具体的问题抽象成了一个图论羂的模型——树(如图)。螇状态对应着结点,状态之间的关系羄(或者说决策方案)对应着边。这样羂的一棵树就叫搜索树。蒁(一)基本思路蒇n1、在每个阶段的决策时,采取能深则深的原则试探所有可行的方案,一旦深入一层则保存当前操作引起的状态。羆n2、一旦试探失败,为了摆脱当前失败状态,采取回到上一阶段尝试下一方案的策略(回溯策略);或者在求解所有解时,求得一个解后,回溯到上一阶段尝试下一方案,以求解下一个解。莄n3、在各个阶段尝试方案时,采取的是穷举的思想。袁(二)引题芈【例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、子程序结构。袆nproceduretry(I:integer);羃nvark:integer;腿nbegin羁nif到达了终点thenbegin保存较优解;返回上一点继续求解(回溯);end葿nelse蒃nbegin芄n穷举从I出发当前可以直接到达的点k;蚁nifI到k点有直接联边并且k点没有遍历过then芆nthenbegin袆n把A[I,K]累加入路径长度tot;k标记为已遍历;try(k);螃n现场恢复;莁nend;芈nend;羄子程序膃proceduretry(i:integer);袈vark:integer;荿begin莆ifi=nthenbeginiftot<minthenmin:=tot;exit;end薂else蚈begin膆fork:=1tondo蒅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);羆fori:=1tondo袀begin衿forj:=1tondoread(fi,a[i,j]);肆readln(fi);肄end;薄close(fi);薀主程序预处理和调用子程序肈tot:=0;min:=maxint;b[1]:=1;蒆try(1);羃writeln('tot=',min);莀袅(三)递归程序结构框架薅Proceduretry(i:integer);莂Vark:integer;肀Begin羇If所有阶段都已求解then蚃Begin袂比较最优解并保存;回溯;袁end肈else肅begin芁fork:=i深度可能决策范围;dobegin薁穷举当前阶段所有可能的决策(方案、结点)k袅ifk方案可行thenbegin膄记录状态变化;蚁try(i+1);莂状态恢复(回溯);end袇end;薆end;莄End;螈羈二、深度优先搜索的应用蚅例1:有A,B,C,D,E5本书,要分给张、王、刘、赵、钱5位同学,每人只选一本。每人将喜爱的书填写下表,输出每人都满意的分书方案。螃薈A螅B螃C芃D艿E螇张膅蚂聿1袈1芄肁王蝿1蚆1蚆薁蒀1蚇刘螄膄1芀1螈袃蚄赵羁薆芅肃1螁蚇钱莄蒂1蒁虿蚆1羂programallotbook;节typefive=1..5;蒆constlike:array[five,five]of0..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[five]ofstring[5]=('zhang','wang','liu','zhao','qian');蚈varbook:array[five]offive;薇flag:setoffive;羃c:integer;螀procedureprint;蒈vari:integer;蕿begin芅inc(c);蒄writeln('answer',c,':');腿fori:=1to5do莆writeln(name[i]:10,':',chr(64+book[i]));莃end;袃proceduretry(i:integer);罿varj:integer;蒇begin螆ifi>5thenprint莃elsebegin蚀forj:=1to5do葿ifnot(jinflag)and(like[i,j]>0