《信息学奥赛——深度优先搜索和广度优先搜索630.pdf》由会员分享，可在线阅读，更多相关《信息学奥赛——深度优先搜索和广度优先搜索630.pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国青少年信息学奥林匹克联赛 搜索基础算法 一、深度搜索（DFS）从一个简单题目开始。例1 输出n 个元素的无重复的全排列。（1=n0 do begin inc(xk);当前第 k 个位置中增加 1 if xkn then 判断当前第 k个位置中是否超界，超界指针后移一位 dec(k)else if try then 判重 begin inc(k);xk:=0;前进 1 位 if kn then 判断指针是否超界，决定一个排列是否完成,完成指针后移一位 begin out;dec(k);end;end;end;end.下面是递归例程：const n=5;var x:array1.10 of i
2、nteger;function try(v1,k:integer):boolean;判重函数,v1表示位置，k 表示所放的值 var i:integer;begin for i:=1 to v1-1 do if xi=k then begin try:=false;exit;end;try:=true;end;procedure out;输出过程 var i:integer;begin for i:=1 to n do write(xi);writeln;end;procedure search(v:integer);v表示第 v 个位置 var i:integer;begin if vn t
3、hen begin out;exit;end;若 v 超界，一个排列完成 for i:=1 to n do 在第 v 个位置上分别放 1 到 n if try(v,i)then 如果不重复，处理第 v+1个位置 begin xv:=i;search(v+1);end;end;begin search(1);end.说明：使用非递归的好处是节约内存，当一些题目对内存消耗较大时，建议使用非递归方式；但使用递归方式在程序运行时间上要好一些，因为在每个节点扩展时，递归方式少一个范围超界判断。例题一 简单的背包问题。设有一个背包，可以放入的重量为 s。现有 n 件物品，重量分别为 均为正整数，从n 件物
4、品中挑选若干件，使得放入背包的重量之和正好为 s。分析：可以设定 n 个位置，每个位置只能放 0 和 1，这样形成一个 0 和 1 可重复的排列，或者是产生一个 n 位的 2 进制数。例程：var w:array1.20 of integer;x:array1.20 of integer;n:integer;s:longint;procedure init;var i:integer;begin readln(n,s);for i:=1 to n do read(wi);end;function try(v1,k:integer):boolean;判断目标函数,v1表示位置，k 表示所放的值
5、var i:integer;s1:longint;begin s1:=wk;for i:=1 to v1-1 do s1:=s1+xi*wi;if s1=s then begin for i:=1 to v1-1 do if xi=0 then write(wi,);writeln(wk);end;if s1=s then begin try:=false;exit;end;else try:=true;end;procedure search(v:integer);v表示第 v 个位置 var i:integer;begin if vn then exit;若 v超界，一个排列完成,本次选择
6、物品方案不成功，退出 for i:=0 to 1 do 在第 v 个位置上分别放 0 到 1 if try(v,i)then 判断所选物品之和是否大于等于 s,否则处理第 v+1个位置 begin xv:=i;search(v+1);end;end;begin init;search(1);end.说明：本文用全排列进行引入 DFS搜索,目的是表明 DFS有一定的模式，如下：procedure search(v:integer；相关形参);v表示当前扩展节点层数（或者叫深度）过程定义的变量表 begin if then begin out;exit;end;若 v 超界，out来作超界处理 形
7、成某种节点扩展程序段（例如：for i:=1 to n do）if 判断所到节点的算法函数或条件 then 例如判重 begin 当前节点处理；search(v+1);处理下一个层数 end;end;例题二 给出一个自然数n(),把n 分解为若干个大于1 的自然数之乘积。请编写程序找出所有的分解方案。分析：此题目的关键是怎样产生需要扩展的各个节点。不难看出乘积为 n 的若干自然数，刚好都是 n 的约数。因此其分解方案变成了求这些约数的不同组合（元素可重复），问题得到解决。例程：var y:array1.50 of longint;用来存放 n 的所有约数 x:array0.50 of inte
8、ger;用来存放组合数的对应 n 的约数所在位置值 n:longint;xlen:integer;procedure init;var i,j,t:longint;k:integer;begin fillchar(x,sizeof(x),0);x0:=1;xlen:=0;for i:=2 to trunc(sqrt(n)do 找出 n 的所有约数 if n mod i=0 then begin inc(xlen);yxlen:=i;inc(xlen);yxlen:=n div i;if i=n div i then 对完全平方数的处理 dec(xlen);end;for i:=1 to xle
9、n-1 do 为保证输出方案由小到大的顺序，进行排序处理 begin k:=i;for j:=i+1 to xlen do if ykyj then k:=j;t:=yi;yi:=yk;yk:=t;end;end;function try(v1,k:integer):boolean;判定所选约数之乘积与 n 的关系 var i:integer;t:longint;begin t:=yk;for i:=1 to v1-1 do t:=t*yxi;if t=n then 与 n 刚好相等，输出一种方案 begin for i:=1 to v1-1 do write(yxi,);writeln(yk
10、);end;if tm then begin for i:=1 to m do write(xi);writeln;exit;end;for i:=xv-1+1 to n do begin xv:=i;search(v+1);end;end;begin readln(n,m);fillchar(x,sizeof(x),0);search(1);end.另外，如果该题目改成：给出一个自然数 n(),把 n 分解为若干个大于 1 的自然数之乘积。请编写程序求出所有的分解方案总数。可用如下方法，供大家参考：var n,t:longint;function search(a,min:longint):
11、longint;var i,s:longint;begin s:=0;for i:=min to trunc(sqrt(a)do if a mod i=0 then s:=s+search(a div i,i);search:=s+1;end;begin readln(n);t:=search(n,2)-1;writeln(t);end.例题三 图论中的遍历问题，例如图论中单源点之间的最短通路问题。问题：设有n 个城市分布在若干地理位置，某两个城市存在一条通道，给出这两个相通城市之间的距离，求一个城市到另一个城市的最短距离。如下图：两个城市之间的如果不相通其距离我们设定为零，否则它们的距离。数
12、据提供方式我们用邻接矩阵。6 0 4 8 0 0 0 4 0 3 4 6 0 8 3 0 2 2 0 0 4 2 0 4 9 0 6 2 4 0 4 0 0 0 9 4 0 分析：本题目我们就定义求 c1 到 c6 之间的最短距离，可以对每一个点进行编号，然后用一个二维数组来存放邻接矩阵，用本文所述的 DFS的固定模式就可以得出本题目的算法。例程如下。const infile=xx.txt;数据文件 var y:array1.10,1.10 of integer;存放邻接矩阵 x:array1.10 of integer;存放各点的编号 xbak:array1.10 of integer;存放
13、当前最短路径的顺序各点 n:integer;点数目 slen:longint;最短路径值 i:integer;procedure init;var i,j:integer;begin assign(input,infile);reset(input);readln(n);for i:=1 to n do for j:=1 to n do read(yi,j);close(input);end;procedure out(vv:integer);var i:integer;s:longint;begin s:=0;for i:=1 to vv-1 do inc(s,yxi,xi+1);if sn
14、 then exit;for i:=2 to n do if try(v,i)then begin xv:=i;search(v+1);end;end;begin init;读取数据 slen:=maxlongint;设最短路径值为最大 x1:=1;固定从编号为 1 的位置 search(2);从第 2 个位置开始搜索 writeln(slen);输出结果 i:=1;while xbaki0 do begin write(xbaki,);inc(i);end;writeln;end.大家可以把这个题目改成从一个点，到某几个点的最短路径。这类问题也可以用 E.W.Dijkstra方法来做，并且其
15、时间效率要高一些。深度搜索有一定固定模式，但其变种还很多，就其实质来说是“怎样构造一棵用来搜索的树(tree),然后对这棵树(tree)进行高效率的剪支”，更重要的是对题目描述的问题建立科学合理的数学模型。二、广度搜索（BFS）入门例题：给出一个由1，2，3，4，5，6 组成的6 位数，相邻的两个数字可以交换位置，问最少经过多少次交换，可以到达另一个目标 6 位数。例如：对于123456，最少经过两次交换，可以变成 231456。分析：这个题目与前面讲过的深度搜索相比有一个明显不同，会出现“又回去了”的情况（产生树的分支有连通的情况），例如：由 123456可以变成 213456，而21345
16、6又可以变成 123456，这样形成了循环。所以需要我们用广度搜索来完成，需要的预备知识是数据结构中的队列。关键点在“最少次数及解决树的分支连通问题”。例程：const n=6;var p1:integer;队列出列指针,指向 openx表 p2:integer;队列入列指针,指向 openx表 openx:array1.1000 of stringn;存放已经出现过的 6 位数 openy:array1.1000 of integer;存放树(tree)的前缀层数,即当前移动次数 st1:string;初始状态，一个 6 位数 st2:string;目标状态，一个 6 位数 st:strin
17、g;i:integer;tc:char;function find(stx:string):boolean;对生成新的状态进行判重 var i:integer;begin for i:=1 to p2 do if stx=openxi then begin find:=false;exit;end;find:=true;end;procedure out;结果输出 begin writeln(openyp1+1);halt;end;begin readln(st1);readln(st2);p1:=1;p2:=1;openx1:=st1;初始设置 fillchar(openy,sizeof(o
18、peny),0);while p1=p2 do begin for i:=1 to n-1 do 对当前 xp1状态，生成所有有效分支 begin st:=openxp1;tc:=sti;sti:=sti+1;sti+1:=tc;交换位置 I 和 i+1中的数字 if st=st2 then 达到目标状态，转向结果输出 out;if find(st)then 判重 begin inc(p2);openxp2:=st;队列入列操作 openyp2:=openyp1+1;取得当前树的扩展层数,即：移动次数 end;end;inc(p1);队列出列操作 end;end.有一些资料的描述是，把队列放在
19、一个独立的线性表中，上面的程序是直接把队列放在数组 openx中，这样节约一些空间。显然 DFS的时间效率体现在“判重”的算法上，提高时间效率方法很多，其中 hash表是重要的一种算法，请参看相关资料。例题二 有 10 升油在 10 升的容器中，另有两个 7 升和 3 升的空容器，要求用这三个容器倒油，使得最后在 10 升和 7 升的容器中各有 5 升油，问最少的倒油次数是多少？var a:array1.3 of integer;每个容器的容量 x:array1.1000,1.3 of shortint;存放已经出现过的状态 y:array1.1000 of integer;存放树(tree)
20、的前缀层数,即当前倒油次数 b:array1.3 of integer;目标状态 c:array1.3 of integer;p1:integer;p2:integer;i,j,t:integer;pt:boolean;procedure init;begin assign(input,xx1.txt);reset(input);readln(a1,a2,a3);readln(x1,1,x1,2,x1,3);读取初始状态 readln(b1,b2,b3);读取目标状态 close(input);end;procedure out;begin writeln(yp1+1);halt;end;fu
21、nction find:boolean;var i:integer;begin for i:=1 to p2 do if(c1=xi,1)and(c2=xi,2)and(c3=xi,3)then begin find:=false;exit;end;find:=true;end;begin init;fillchar(y,sizeof(y),0);p1:=1;p2:=1;while p1=p2 do begin for i:=1 to 3 do 对当前 xp1 状态，生成所有有效分支 for j:=1 to 3 do if ij then begin for t:=1 to 3 do ct:=
22、xp1,t;pt:=false;if ci+cj=aj then 从 i 到 j 全部倒完 begin cj:=cj+ci;ci:=0;pt:=true;end;if(cj=0)and(pt=false)then 只能倒一部分 begin ci:=ci-(aj-cj);cj:=aj;pt:=true;end;if pt then begin if(c1=b1)and(c2=b2)and(c3=b3)then out;到达目标输出 if find then 判重 begin inc(p2);队列入列操作 for t:=1 to 3 do xp2,t:=ct;取得当前树的扩展层数,即：倒油次数 yp2:=yp1+1;end;end;end;inc(p1);队列出列操作 end;end.