基本搜索算法之深度搜索.doc

基本搜索算法之深度搜索从一个简单题目开始。例1输出n个元素的无重复的全排列。（1=n0 dobegininc(xk); 当前第k个位置中增加1if xkn then 判断当前第k个位置中是否超界，超界指针后移一位dec(k)elseif try then 判重begininc(k);xk:=0; 前进1位if kn then 判断指针是否超界，决定一个排列是否完成,完成指针后移一位 begin out;dec(k);end;end;end;end.下面是递归例程：const n=5;varx:array1.10 of integer;function try(v1,k:integer):boolean; 判重函数,v1表示位置，k表示所放的值var i:integer;beginfor i:=1 to v1-1 doif xi=k thenbegin try:=false;exit;end;try:=true;end;procedure out; 输出过程 var i:integer;beginfor i:=1 to n dowrite(xi);writeln;end;procedure search(v:integer); v表示第v个位置var i:integer;beginif vn then begin out;exit;end; 若v超界，一个排列完成for i:=1 to n do 在第v个位置上分别放1到nif try(v,i) then 如果不重复，处理第v+1个位置begin xv:=i;search(v+1);end;end;beginsearch(1);end.说明：使用非递归的好处是节约内存，当一些题目对内存消耗较大时，建议使用非递归方式；但使用递归方式在程序运行时间上要好一些，因为在每个节点扩展时，递归方式少一个范围超界判断。例题一简单的背包问题。设有一个背包，可以放入的重量为s。现有n件物品，重量分别为 均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。分析：可以设定n个位置，每个位置只能放0和1，这样形成一个0和1可重复的排列，或者是产生一个n位的2进制数。例程：varw:array1.20 of integer;x:array1.20 of integer;n:integer;s:longint;procedure init;var i:integer;beginreadln(n,s);for i:=1 to n doread(wi);end;function try(v1,k:integer):boolean; 判断目标函数,v1表示位置，k表示所放的值var i:integer;s1:longint;begins1:=wk;for i:=1 to v1-1 dos1:=s1+xi*wi;if s1=s thenbeginfor i:=1 to v1-1 doif xi=0 thenwrite(wi, );writeln(wk);end;if s1=s thenbegin try:=false;exit;end;elsetry:=true;end;procedure search(v:integer); v表示第v个位置var i:integer;beginif vn then exit;若v超界，一个排列完成,本次选择物品方案不成功，退出for i:=0 to 1 do 在第v个位置上分别放0到1if try(v,i) then 判断所选物品之和是否大于等于s,否则处理第v+1个位置begin xv:=i;search(v+1);end;end;begininit;search(1);end.说明：本文用全排列进行引入DFS搜索,目的是表明DFS有一定的模式，如下：procedure search(v:integer；相关形参); v表示当前扩展节点层数（或者叫深度）过程定义的变量表beginif then begin out;exit;end; 若v超界，out来作超界处理形成某种节点扩展程序段（例如：for i:=1 to n do）if 判断所到节点的算法函数或条件 then 例如判重begin 当前节点处理；search(v+1); 处理下一个层数end;end;例题二给出一个自然数n( ),把n分解为若干个大于1的自然数之乘积。请编写程序找出所有的分解方案。分析：此题目的关键是怎样产生需要扩展的各个节点。不难看出乘积为n的若干自然数，刚好都是n的约数。因此其分解方案变成了求这些约数的不同组合（元素可重复），问题得到解决。例程：vary:array1.50 of longint; 用来存放n的所有约数x:array0.50 of integer; 用来存放组合数的对应n的约数所在位置值n:longint;xlen:integer;procedure init;var i,j,t:longint;k:integer;beginfillchar(x,sizeof(x),0);x0:=1;xlen:=0;for i:=2 to trunc(sqrt(n) do 找出n的所有约数if n mod i=0 thenbegininc(xlen);yxlen:=i;inc(xlen);yxlen:=n div i;if i=n div i then 对完全平方数的处理dec(xlen);end;for i:=1 to xlen-1 do 为保证输出方案由小到大的顺序，进行排序处理begink:=i;for j:=i+1 to xlen doif ykyj thenk:=j;t:=yi;yi:=yk;yk:=t;end;end;function try(v1,k:integer):boolean; 判定所选约数之乘积与n的关系var i:integer;t:longint;begint:=yk; for i:=1 to v1-1 dot:=t*yxi;if t=n then 与n刚好相等，输出一种方案begin for i:=1 to v1-1 dowrite(yxi, );writeln(yk);end;if tm thenbeginfor i:=1 to m dowrite(xi);writeln;exit;end;for i:=xv-1+1 to n dobegin xv:=i;search(v+1);end;end;beginreadln(n,m);fillchar(x,sizeof(x),0);search(1);end.另外，如果该题目改成：给出一个自然数n( ),把n分解为若干个大于1的自然数之乘积。请编写程序求出所有的分解方案总数。可用如下方法，供大家参考：varn,t:longint;function search(a,min:longint):longint;vari,s:longint;begins:=0;for i:=min to trunc(sqrt(a) doif a mod i=0 thens:=s+search(a div i,i);search:=s+1;end;beginreadln(n);t:=search(n,2)-1;writeln(t);end.例题三图论中的遍历问题，例如图论中单源点之间的最短通路问题。问题：设有n个城市分布在若干地理位置，某两个城市存在一条通道，给出这两个相通城市之间的距离，求一个城市到另一个城市的最短距离。如下图：两个城市之间的如果不相通其距离我们设定为零，否则它们的距离。数据提供方式我们用邻接矩阵。60 4 8 0 0 04 0 3 4 6 08 3 0 2 2 00 4 2 0 4 90 6 2 4 0 40 0 0 9 4 0分析：本题目我们就定义求c1到c6之间的最短距离，可以对每一个点进行编号，然后用一个二维数组来存放邻接矩阵，用本文所述的DFS的固定模式就可以得出本题目的算法。例程如下。constinfile=xx.txt; 数据文件vary:array1.10,1.10 of integer; 存放邻接矩阵x:array1.10 of integer; 存放各点的编号xbak:array1.10 of integer; 存放当前最短路径的顺序各点n:integer; 点数目slen:longint; 最短路径值i:integer;procedure init;var i,j:integer;beginassign(input,infile);reset(input);readln(n);for i:=1 to n dofor j:=1 to n doread(yi,j);close(input);end;procedure out(vv:integer);var i:integer;s:longint;begins:=0;for i:=1 to vv-1 doinc(s,yxi,xi+1);if sn then exit;for i:=2 to n doif try(v,i) thenbegin xv:=i;search(v+1);end;end;begininit; 读取数据slen:=maxlongint; 设最短路径值为最大x1:=1; 固定从编号为1的位置search(2); 从第2个位置开始搜索writeln(slen); 输出结果i:=1;while xbaki