2022年搜索算法之深度优先搜索与广度优先搜索 .pdf
《2022年搜索算法之深度优先搜索与广度优先搜索 .pdf》由会员分享,可在线阅读,更多相关《2022年搜索算法之深度优先搜索与广度优先搜索 .pdf(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 个城市分布在若干地理位置,某两个城市存在一条通道,给出这两个相通城市之间的距离,求一个城市到另一个城市的最短距离。如下图:两个城市之间的如果不相通其距离我们
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年搜索算法之深度优先搜索与广度优先搜索 2022 搜索 算法 深度 优先 广度
限制150内