基本搜索算法之深度搜索.doc

基本搜索算法之深度搜索
从一个简单题目开始。
。(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