2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 深度优先搜索和广度优先搜索.doc

《2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 深度优先搜索和广度优先搜索.doc》由会员分享，可在线阅读，更多相关《2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 深度优先搜索和广度优先搜索.doc（16页珍藏版）》请在装配图网上搜索。

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 深度优先搜索和广度优先搜索 从一个简单题目开始。 例1．输出n个元素的无重复的全排列。（1<=n<=9） 在这里我们可以对每一个元素编号，形成1,2,…,8,9个数字的全排列。我们用一个一维数组来处理，相当于有9个位置，每个位置可以放1到9，再进行重复性判断，即在每个位置放一个数字时判断它前面是否已经使用该数字。通过数组中元素值的变化，产生全排列。 下面给出非递归例程，其中，变量k是表示位置指针，数组x用来装每个位置的值。 const n=5; var x:array[1..10] of integer; k:integer; {位置指针} function try:boolean; {判重函数} var i:integer; begin for i:=1 to k-1 do if x[i]=x[k] then begin try:=false;exit;end; try:=true; end; procedure out; {输出过程} var i:integer; begin for i:=1 to n do write(x[i]); writeln; end; begin k:=1; x[1]:=0; while k>0 do begin inc(x[k]); {当前第k个位置中增加1} if x[k]>n then {判断当前第k个位置中是否超界，超界指针后移一位} dec(k) else if try then {判重} begin inc(k);x[k]:=0; {前进1位} if k>n then{判断指针是否超界，决定一个排列是否完成,完成指针后移一位} begin out;dec(k);end; end; end; end. 下面是递归例程： const n=5; var x:array[1..10] of integer; function try(v1,k:integer):boolean; {判重函数,v1表示位置，k表示所放的值} var i:integer; begin for i:=1 to v1-1 do if x[i]=k then begin try:=false;exit;end; try:=true; end; procedure out; {输出过程} var i:integer; begin for i:=1 to n do write(x[i]); writeln; end; procedure search(v:integer); {v表示第v个位置} var i:integer; begin if v>n then begin out;exit;end; {若v超界，一个排列完成} for i:=1 to n do {在第v个位置上分别放1到n} if try(v,i) then {如果不重复，处理第v+1个位置} begin x[v]:=i;search(v+1);end; end; begin search(1); end. 说明：使用非递归的好处是节约内存，当一些题目对内存消耗较大时，建议使用非递归方式；但使用递归方式在程序运行时间上要好一些，因为在每个节点扩展时，递归方式少一个范围超界判断。 例题一 简单的背包问题。 设有一个背包，可以放入的重量为s。现有n件物品，重量分别为 均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。 分析：可以设定n个位置，每个位置只能放0和1，这样形成一个0和1可重复的排列，或者是产生一个n位的2进制数。 例程： var w:array[1..20] of integer; x:array[1..20] of integer; n:integer; s:longint; procedure init; var i:integer; begin readln(n,s); for i:=1 to n do read(w[i]); end; function try(v1,k:integer):boolean; {判断目标函数,v1表示位置，k表示所放的值} var i:integer; s1:longint; begin s1:=w[k]; for i:=1 to v1-1 do s1:=s1+x[i]*w[i]; if s1=s then begin for i:=1 to v1-1 do if x[i]=0 then write(w[i], ); writeln(w[k]); 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 v>n then exit;{若v超界，一个排列完成,本次选择物品方案不成功，退出} for i:=0 to 1 do{在第v个位置上分别放0到1} if try(v,i) then{判断所选物品之和是否大于等于s,否则处理第v+1个位置} begin x[v]:=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来作超界处理} 形成某种节点扩展程序段（例如：for i:=1 to n do） if 〈判断所到节点的算法函数或条件〉 then {例如判重} begin 当前节点处理； search(v+1); {处理下一个层数} end; end; 例题二 给出一个自然数n( ),把n分解为若干个大于1的自然数之乘积。请编写程序找出所有的分解方案。 分析：此题目的关键是怎样产生需要扩展的各个节点。不难看出乘积为n的若干自然数，刚好都是n的约数。因此其分解方案变成了求这些约数的不同组合（元素可重复），问题得到解决。 例程： var y:array[1..50] of longint; {用来存放n的所有约数} x:array[0..50] of integer; {用来存放组合数的对应n的约数所在位置值} n:longint; xlen:integer; procedure init; var i,j,t:longint; k:integer; begin fillchar(x,sizeof(x),0); x[0]:=1; xlen:=0; for i:=2 to trunc(sqrt(n)) do {找出n的所有约数} if n mod i=0 then begin inc(xlen);y[xlen]:=i;inc(xlen);y[xlen]:=n div i; 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 y[k]>y[j] then k:=j; t:=y[i];y[i]:=y[k];y[k]:=t; end; end; function try(v1,k:integer):boolean; {判定所选约数之乘积与n的关系} var i:integer; t:longint; begin t:=y[k]; for i:=1 to v1-1 do t:=t*y[x[i]]; if t=n then {与n刚好相等，输出一种方案} begin for i:=1 to v1-1 do write(y[x[i]], ); writeln(y[k]); end; if tm then begin for i:=1 to m do write(x[i]); writeln;exit; end; for i:=x[v-1]+1 to n do begin x[v]:=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):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个城市分布在若干地理位置，某两个城市存在一条通道，给出这两个相通城市之间的距离，求一个城市到另一个城市的最短距离。如下图： 两个城市之间的如果不相通其距离我们设定为零，否则它们的距离。数据提供方式我们用邻接矩阵。 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:array[1..10,1..10] of integer; {存放邻接矩阵} x:array[1..10] of integer; {存放各点的编号} xbak:array[1..10] of integer; {存放当前最短路径的顺序各点} 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(y[i,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,y[x[i],x[i+1]]); if sn then exit; for i:=2 to n do if try(v,i) then begin x[v]:=i;search(v+1);end; end; begin init; {读取数据} slen:=maxlongint; {设最短路径值为最大} x[1]:=1; {固定从编号为1的位置} search(2); {从第2个位置开始搜索} writeln(slen); {输出结果} i:=1; while xbak[i]>0 do begin write(xbak[i], );inc(i);end; writeln; end. 大家可以把这个题目改成从一个点，到某几个点的最短路径。 这类问题也可以用E.W.Dijkstra方法来做，并且其时间效率要高一些。 深度搜索有一定固定模式，但其变种还很多，就其实质来说是“怎样构造一棵用来搜索的树(tree),然后对这棵树(tree)进行高效率的剪支”，更重要的是对题目描述的问题建立科学合理的数学模型。 二、广度搜索（BFS） 入门例题： 给出一个由1，2，3，4，5，6组成的6位数，相邻的两个数字可以交换位置，问最少经过多少次交换，可以到达另一个目标6位数。例如： 对于123456，最少经过两次交换，可以变成231456。 分析：这个题目与前面讲过的深度搜索相比有一个明显不同，会出现“又回去了”的情况（产生树的分支有连通的情况），例如：由123456可以变成213456，而213456又可以变成123456，这样形成了循环。所以需要我们用广度搜索来完成，需要的预备知识是《数据结构》中的队列。关键点在“最少次数及解决树的分支连通问题”。 例程： const n=6; var p1:integer; {队列出列指针,指向openx表} p2:integer; {队列入列指针, 指向openx表} openx:array[1..1000] of string[n]; {存放已经出现过的6位数} openy:array[1..1000] of integer; {存放树(tree)的前缀层数,即当前移动次数} st1:string; {初始状态，一个6位数} 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=openx[i] then begin find:=false;exit;end; find:=true; end; procedure out; {结果输出} begin writeln(openy[p1+1]); halt; end; begin readln(st1); readln(st2); p1:=1;p2:=1;openx[1]:=st1; {初始设置} fillchar(openy,sizeof(openy),0); while p1<=p2 do begin for i:=1 to n-1 do {对当前x[p1]状态，生成所有有效分支} begin st:=openx[p1]; tc:=st[i];st[i]:=st[i+1];st[i+1]:=tc; {交换位置I和i+1中的数字} if st=st2 then {达到目标状态，转向结果输出} out; if find(st) then {判重} begin inc(p2);openx[p2]:=st; {队列入列操作} openy[p2]:=openy[p1]+1; {取得当前树的扩展层数,即：移动次数} end; end; inc(p1); {队列出列操作} end; end. 有一些资料的描述是，把队列放在一个独立的线性表中，上面的程序是直接把队列放在数组openx中，这样节约一些空间。显然DFS的时间效率体现在“判重”的算法上，提高时间效率方法很多，其中hash表是重要的一种算法，请参看相关资料。 例题二 有10升油在10升的容器中，另有两个7升和3升的空容器，要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油，问最少的倒油次数是多少？ var a:array[1..3] of integer; {每个容器的容量} x:array[1..1000,1..3] of shortint; {存放已经出现过的状态} y:array[1..1000] of integer; {存放树(tree)的前缀层数,即当前倒油次数} b:array[1..3] of integer; {目标状态} c:array[1..3] of integer; p1:integer; p2:integer; i,j,t:integer; pt:boolean; procedure init; begin assign(input,xx1.txt); reset(input); readln(a[1],a[2],a[3]); readln(x[1,1],x[1,2],x[1,3]); {读取初始状态} readln(b[1],b[2],b[3]); {读取目标状态} close(input); end; procedure out; begin writeln(y[p1]+1); halt; end; function find:boolean; var i:integer; begin for i:=1 to p2 do if (c[1]=x[i,1]) and (c[2]=x[i,2]) and (c[3]=x[i,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 {对当前x[p1…]状态，生成所有有效分支} for j:=1 to 3 do if i<>j then begin for t:=1 to 3 do c[t]:=x[p1,t]; pt:=false; if c[i]+c[j]<=a[j] then {从i到j全部倒完} begin c[j]:=c[j]+c[i];c[i]:=0;pt:=true;end; if (c[j]=0) and (pt=false) then {只能倒一部分} begin c[i]:=c[i]-(a[j]-c[j]);c[j]:=a[j];pt:=true; end; if pt then begin if (c[1]=b[1]) and (c[2]=b[2]) and (c[3]=b[3]) then out; {到达目标输出} if find then {判重} begin inc(p2); {队列入列操作} for t:=1 to 3 do x[p2,t]:=c[t]; {取得当前树的扩展层数,即：倒油次数} y[p2]:=y[p1]+1; end; end; end; inc(p1); {队列出列操作} end; end.