全国青少年信息学奥林匹克联赛
搜索基础算法
一、深度搜索（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;
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;
2
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
3
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个位置}
4
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;
5
高中信息技术 全国青少年奥林匹克联赛教案 深度优先搜索和广度优先搜索
