深度优先算法.doc

常用算法——深度优先有哪些信誉好的足球投注网站(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 totmin then min:=tot;exit;end else begin for k:=1 to n do if (b[k]=0) and (ik) 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; 二、深度优先有哪些信誉好的足球投注网站的应用 例1:有A，B，C，D，E 5本书，要分给张、王、刘、赵、钱5位同学，每人只选一本。每人将喜爱的书填写下表，输出每人都满意的分书方案。 　 A B C D E 张 　 　 1 1 　 王 1 1 　 　 1 刘 　 1 1 　 　 赵 　 　 　 1 　 钱 　 1 　 　 1 program allotbook; type five=1..5; const like:array[five,five] of 0..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] of string[5]=(zhang,wang,liu,zhao,qian); var book:array[five] of five; flag:set of five; c:integer; procedure print; var i:integer; begin inc(c); writeln(answer,c,:); for i