信息学奥赛-深度优先搜索和广度优先搜索.doc
文本预览下载声明
全国青少年信息学奥林匹克联赛
一、深度搜索（DFS）
从一个简单题目开始。
例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 k0 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 kn 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 vn 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:in
显示全部