信息学奥赛——深度优先搜索和广度优先搜索

《信息学奥赛——深度优先搜索和广度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、全国青少年信息学奥林匹克联赛搜索基础算法-、深度搜索(DFS)从一个简单题日开始。例1・输出n个元素的无重复的全排列。(l<=n<=9)在这里我们可以对每一个元素编号,形成1,2,…,&9个数字的全排列。我们用一个-•维数组來处理,相当于有9个位置,每个位置可以放1到9,再进行重复性判断,即在每个位置放一个数字时判断它前面是否已经使用该数字。通过数组小元素值的变化,产半全排列。下而给出非递归例程，其中，变量k是表示位置指针，数组x用来装每个位置的值。constn二5;varx:array[1..10]ofinteger;k:integer;｛位置指针｝functiontry:boolean;｛

2、判重函数｝vari:integer;beginfori:=1tokTdoifx[i]=x[k]thenbegintry:=false;exit;end;try:=true;end;procedureout;｛输出过程｝vari:integer;beginfori:=1tondowrite(x[i]);writeIn;end;begink:=l;x[l]:=O;wh订ek>0dobegininc(x[k]);｛当前笫k个位置中增加1｝ifx[k]>nthendec(k)｛判断当前第k个位置中是否超界，超界指针后移一位｝elseiftrythenbegin｛判重｝inc(k);x[k]:二0;｛前

3、进1位｝ifk>nthen｛判断指针是否超界，决定一个排列是否完成，完成指针后移一位｝beginout;dec(k);end;end;end;end.下面是递归例程：constn二5;varx:array[1..10]ofinteger;｛判重函数jl表示位置，k表示所｛输出过程｝functiontry(vl,k:integer):boolean;放的值｝vari:integer;beginfori:=1tovl-1doifx[i]=kthenbegintry:=false;exit;end;try:二true;end;procedureout;vari:integer;beginfori:=

4、ltondowrite(x[i]);writein;end;proceduresearch(v:integer);(v表示第v个位置｝vari:integer;beginifv>nthenbeginout;exit;end;｛若v超界，一个排列完成｝fori:=ltondo｛在第v个位置上分别放1到n｝iftry(v,i)then｛如果不重复，处理第v+1个位置｝beginx[v]:=i;search(v+1);end;end;beginsearch(1);end.说明：使用非递归的好处是节约内存，当一些题日对内存消耗较大时，建议使用非递归方式；但使用递归方式在程序运行时间上要好一些，因为在每

5、个节点扩展时，递归方式少一个范围超界判断。例题一简单的背包问题。设有一个背包，町以放入的重量为s。现有n件物品，重量分别为均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为so分析：可以设定n个位置，每个位置只能放0和1,这样形成一个0和1可重复的排列，或者是产生一个n位的2进制数。例程：varw:array[1..20]ofinteger;x:array[1..20]ofinteger;｛判断目标函数11表示位置，k表示所｛v表示第v个位置｝n:integcr;s:longint;procedureinit;vari:integer;beginreadln(n,s);fori:

6、=1tondoread(w[i]);end;functiontry(vl,k:integer):boolean;放的值｝vari:integer;si:longint;beginsi:=w[k];fori:=1tovlTdosi:二sl+x[i]*w[i];ifsi二sthenbeginfori:=1tovl-1doifx[i]=0thenwrite(w[i],'');writeln(w[k]);end;ifsl>=sthenbegintry:=false;exit;end;elsetry:=true;end;proceduresearch(v:integer);beginifv>nthene

7、xit;｛若v超界，一个排列完成，本次选择物品方案不成功，退出｝fori:=0to1do｛在第v个位置上分别放0到1｝iftry(v,i)then｛判断所选物品之和是否大于等于s,否则处理第v+1个位置｝beginx[v]:=i;search(v+1);end;end;begininit;search(1);end.说明：本文用全排列进行引入DFS捜索，目的是表明DFS有一定的模式，如下:proc