《2022年搜索算法之深度优先搜索与广度优先搜索定义》由会员分享,可在线阅读,更多相关《2022年搜索算法之深度优先搜索与广度优先搜索定义(18页珍藏版)》请在金锄头文库上搜索。
1、搜索算法之深度优先搜索与广度优先搜索双击自动滚屏发布者:发布时间: 2009-5-16 阅读: 78 次搜索基础算法一、深度搜索(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;
2、 end. 下面是递归例程:const n=5; var x:array1.10 of integer; function try(v1,k:integer):boolean; 判重函数 ,v1 表示位置, k 表示所放的值 var i:integer; begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 18 页 - - - - - - - - - for i:=1 to v1-1 do if xi=k then begin try:=false;exit;en
3、d; 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 then 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)
4、;end; end; begin search(1); end. 说明: 使用非递归的好处是节约内存,当一些题目对内存消耗较大时,建议使用非递归方式; 但使用递归方式在程序运行时间上要好一些,因为在每个节点扩展时,递归方式少一个范围超界判断。例题一简单的背包问题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 18 页 - - - - - - - - - 设有一个背包,可以放入的重量为s。现有 n 件物品,重量分别为均为正整数,从n件物品中挑选若干件,使得放入背包的重量之
5、和正好为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 表示所放的值 var i:int
6、eger; 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 18 页 - - - - - - - - - write(wi, ); writeln(wk); end; if s1=s then begin try:=false;exit;end; el
7、se try:=true; end; procedure search(v:integer); v表示第 v 个位置 var i:integer; begin if vn then exit; 若 v 超界,一个排列完成, 本次选择物品方案不成功,退出 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有
8、一定的模式,如下:procedure search(v:integer;相关形参 ); v表示当前扩展节点层数(或者叫深度) 过程定义的变量表 begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 18 页 - - - - - - - - - if then begin out;exit;end; 若 v 超界, out 来作超界处理 形成某种节点扩展程序段(例如:for i:=1 to n do) if 判断所到节点的算法函数或条件 then 例如判重 begin
9、 当前节点处理;search(v+1); 处理下一个层数 end; end; 例题二给出一个自然数n( ), 把 n 分解为若干个大于1 的自然数之乘积。请编写程序找出所有的分解方案。分析:此题目的关键是怎样产生需要扩展的各个节点。不难看出乘积为n 的若干自然数,刚好都是n 的约数。因此其分解方案变成了求这些约数的不同组合(元素可重复),问题得到解决。例程:var y:array1.50 of longint; 用来存放 n 的所有约数 x:array0.50 of integer; 用来存放组合数的对应n 的约数所在位置值 n:longint; xlen:integer; procedure
10、 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 的所有约数 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 18 页 - - - - - - - - - if n mod i=0 then begin inc(xlen);yxlen:=i;inc(xlen);yxlen:=n div i
11、; if i=n div i then 对完全平方数的处理 dec(xlen); end; for i:=1 to xlen-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
12、 then 与 n 刚好相等,输出一种方案 begin for i:=1 to v1-1 do write(yxi, ); writeln(yk); end; if tm then begin for i:=1 to m do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 18 页 - - - - - - - - - write(xi); writeln;exit; end; for i:=xv-1+1 to n do begin xv:=i;search(v+1);e
13、nd; 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):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,
14、i); search:=s+1; end; begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 18 页 - - - - - - - - - readln(n); t:=search(n,2)-1; writeln(t); end. 例题三图论中的遍历问题,例如图论中单源点之间的最短通路问题。问题: 设有 n 个城市分布在若干地理位置,某两个城市存在一条通道,给出这两个相通城市之间的距离,求一个城市到另一个城市的最短距离。如下图:两个城市之间的如果不相通其距离我们
15、设定为零,否则它们的距离。数据提供方式我们用邻接矩阵。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.
16、10 of integer; 存放当前最短路径的顺序各点 n:integer; 点数目 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 18 页 - - - - - - - - - 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
17、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 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); 从第
18、 2 个位置开始搜索 writeln(slen); 输出结果 i:=1; while xbaki0 do begin write(xbaki, );inc(i);end; writeln; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 18 页 - - - - - - - - - end. 大家可以把这个题目改成从一个点,到某几个点的最短路径。这类问题也可以用E.W.Dijkstra方法来做,并且其时间效率要高一些。深度搜索有一定固定模式,但其变种还很多,就其实质来说
19、是 “怎样构造一棵用来搜索的树 (tree),然后对这棵树 (tree)进行高效率的剪支”,更重要的是对题目描述的问题建立科学合理的数学模型。二、广度搜索(BFS )入门例题:给出一个由1,2,3, 4,5,6 组成的 6 位数,相邻的两个数字可以交换位置,问最少经过多少次交换,可以到达另一个目标6 位数。例如:对于 123456,最少经过两次交换,可以变成231456。分析:这个题目与前面讲过的深度搜索相比有一个明显不同,会出现“又回去了”的情况(产生树的分支有连通的情况),例如:由123456 可以变成213456,而 213456 又可以变成123456,这样形成了循环。所以需要我们用广
20、度搜索来完成,需要的预备知识是数据结构中的队列。关键点在“最少次数及解决树的分支连通问题”。例程: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 位数 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
21、- - - 名师精心整理 - - - - - - - 第 13 页,共 18 页 - - - - - - - - - st2:string; 目标状态,一个6 位数 st:string; 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(op
22、enyp1+1); halt; end; begin readln(st1); readln(st2); p1:=1;p2:=1;openx1:=st1; 初始设置 fillchar(openy,sizeof(openy),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 中的数字 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
23、名师精心整理 - - - - - - - 第 14 页,共 18 页 - - - - - - - - - if st=st2 then 达到目标状态,转向结果输出 out; if find(st) then 判重 begin inc(p2);openxp2:=st; 队列入列操作 openyp2:=openyp1+1; 取得当前树的扩展层数, 即:移动次数 end; end; inc(p1); 队列出列操作 end; end. 有一些资料的描述是,把队列放在一个独立的线性表中,上面的程序是直接把队列放在数组 openx 中,这样节约一些空间。显然DFS的时间效率体现在“判重”的算法上,提高时间
24、效率方法很多,其中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)的前缀层数 , 即当前倒油次数 b:array1.3 of integer; 目标状态 c:array1.3 of integer; p1
25、:integer; p2:integer; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页,共 18 页 - - - - - - - - - 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(in
26、put); end; procedure out; begin writeln(yp1+1); halt; end; function 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 名师资料总结 - - -精品资料欢迎下载 -
27、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页,共 18 页 - - - - - - - - - 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:=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
28、 只能倒一部分 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页,共 18 页 - - - - - - - - - end; inc(p1); 队列出列操作 end; end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页,共 18 页 - - - - - - - - -