[精品]深度优先算法
常用算法——深度优先搜索(degree first serch)
吴孝燕
一、 深度优先搜索的基本思路
把一个具体的问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
抽象成了一个图论
的模型——树(如图)。
状态对应着结点，状态之间的关系
(或者说决策
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
)对应着边。这样
的一棵树就叫搜索树。
(一)基本思路
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
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;
二、深度优先搜索的应用
例1:有A，B，C，D，E 5本
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
，要分给张、王、刘、赵、钱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:=1 to 5 do
writeln(name[i]:10,':',chr(64+book[i]));
end;
procedure try(i:integer);
var j:integer;
begin
if i>5 then print
else begin
for j:=1 to 5 do
if not(j in flag) and (like[i,j]>0) then
begin flag:=flag+[j];
book[i]:=j;
try(i+1);
flag:=flag-[j];
end
end;
end;
begin
flag:=[];
c:=0;
try(1);
readln;
end.
例2: 中国象棋棋盘如下图马自左下角往右上角跳.规定只许往左跳,不许往右跳(如图跳法)
编程找出所有跳法。
program tiaoma;
const
di:array[1..4] of integer=(1,2,2,1); dj:array[1..4] of integer=(2,1,-1,-2); var x,y:array[0..20] of integer;
c:integer;
procedure print(dep:integer);
var j:integer;
begin
c:=c+1;write(c,':');
for j:=0 to dep-1 do write('(',x[j],',',y[j],')->');
writeln('(',x[dep],',',y[dep],')');
end;
procedure try(dep,i,j:integer);
var r,ni,nj:byte;
begin
if (i=8) and (j=4) then print(dep-1)
else begin
for r:=1 to 4 do
begin
ni:=i+di[r];
nj:=j+dj[r];
if (ni>0)and(ni<=8)and(nj>=0)and(nj<=4) then
begin
x[dep]:=ni;y[dep]:=nj ;
try(dep+1,ni,nj)
end;
end;
end;
end;
begin
x[0]:=0;y[0]:=0;
c:=0;
try(1,0,0);
readln;
end.
三、深度优先搜索在奥赛中的应用 1、NOIP1999 邮票面值
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
给定一个信封，最多只允许粘贴N张邮票，计算在给定K(N+k<=40) 种邮票的情况下(假
定所有的邮票数量都足够)，如何设计邮票的面值，能得到最大max ，使得1,max之间的每
一个邮资值都能得到。
program noip4;
var
n,k:integer;
procedure get(p:integer,var maxn:integer);
var
begin
t:=can;
for i:=1 to p do
for j:=0 to maxn do if can[j] then t[j+now[i]]:=true; can:=t;
maxn:=maxn+now[p];
end;
procedure solve(p,last,max:integer); begin
if p=k then begin
if max>best then begin best:=max;answer:=now; end;
exit;
end;
for i:=last+1 to max+1 do begin now[p+1]:=i;
h:=0;
fillchar(can,sizeof(can),false); can[0]:=true;
for j:=1 to n do get(p+1,h); for j:=1 to h+1 do
if not can[j] then begin ma:=j-1;break;end;
solve(p+1,i,ma);
end;
end;
{main}
begin
readln(n,k);
best:=0;
solve(0,0,0);
i:=0
2、NOIP2001 数的划分 将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
例如:n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入:n，k (6=pre then inc(r); exit;
end;
for j:=pre to s div 2 do work(dep+1,j,s-j); end;
也可利用回溯思想
procedure try(dep:integer);
var i:integer;
begin
if dep=k then begin
if tot>=a[dep-1] then inc(sum);
exit; end;
for i:=a[dep-1] to tot div 2 do begin a[dep]:=i; dec(tot,i);
try(dep+1);
inc(tot,i);
end;
end;{try}
深度优先搜索算法是算法设计中最为基本的算法。大多数的题可以用它来解决，但是深度优先搜索算法的运算速度慢，而竞赛试题对程序出解的时限有严格的要求，因此必须对搜索加以优化。优化一般有以下三种方法:(1)缩小搜索范围;(2)改变搜索次序;(3)剪枝。当然，解决问题有多种方法，能用效率更高的算法那更佳。
![[精品]深度优先算法](https://swf.iask.com/ynX4Af5PxGa.svg?ssig=2%2FQZnq6qxp&Expires=1721179801&KID=sina,ishare&range=0-18586)
浙公网安备 33021202002483