搜索算法之深度优先搜索
深度优先搜索 |
[算法分析] 编程学到现在才真正到了戏肉部分,从这里往下学,你才知道什么叫做博大精深。今天我们要啃的这块硬骨头叫做 例:八皇后问题:在标准国际象棋的棋盘上(8*8格)准备放置8只皇后,我们知道,国际象棋中皇后的威力是 [参考程序] program queen;{8皇后问题参考程序}
const n=8;
var a,b:array [1..n] of integer;{数组a存放解:a[i]表示第i个皇后放在第a[i]列;}
c:array [1-n,n-1] of integer;
d:array [2..n+n] of
integer;{数组b,c,d表示棋盘的当前情况:b[k]为1表示第k行已被占领为0表示为空;c、d表示对角线}
k:integer;
procedure print;{打印结果}
var j:integer;
begin
for j:=1 to n do write(a[j]:4);
writeln;
end;
procedrue try(i:integer); {递归搜索解}
var
j:integer;{每个皇后的可放置位置。注意:一定要在过程中定义;否则当递归时会覆盖掉它的值,不能得到正确
结果}
begin
for j:=1 to n do
begin
if (b[j]=0) and (c[i-j]=0) and (d[i+j]=0) then{检查位置是否合法}
begin
a[i]:=j;{置第i个皇后的位置是第j行}
b[j]:=1;{宣布占领行、对角线}
c[i-j]:=1;
d[i+j]:=1;
if i<n then try(i+1) else print;{如果末达目标则放置下一皇后,否则打印结果}
b[j]:=0;{清空被占行、对角线,回溯}
c[i-j]:=0;
d[i+j]:=0;
end;
end;
end;
begin
for k:=1 to n do b[k]:=0;{初始化数据}
for k:=1-n to n-1 do c[k]:=0;
for k:=2 to n+n do d[k]:=0;
try(1);
end.
N皇后问题 {
Problem : N Queens Problem
Algorithm : Depth First Search
Author : tenshi
Date : 2002-07-14 @ SJTU ZZL 111
}
Program N_Queens;
const n=8;
var
a:array[1..n] of integer; { 皇后放在 ( i, a[i] ) }
mk:array[1..n] of boolean; { 如果mk[i]为true,表示第i列可以放 }
total:integer;
procedure output; {输出}
var i:integer;
begin
inc(total);
write('No.':4,'[',total:2,']');
for i:=1 to n do write(a[i]:3);
writeln;
end;
function can(d:integer):boolean; {判断第d行的Queen可否放在第a[d]列}
var i:Integer;
begin
can:=false;
if mk[a[d]] then exit; {如果第d列已经被占,则返回false}
for i:=1 to d-1 do
if abs(a[i]-a[d])=abs(i-d) then exit; { 如果第i行和第d行的Queen在同一对角线上,则返回false }
can:=true;
end;
procedure dfs(d:integer);
var i,j:integer;
begin
if (d>n) then { 找到一个解并输出 }
begin
output;
exit;
end;
for i:=1 to N do { 每一行均有N种放法 }
begin
a[d]:=i; { 第d行的Queen放在第a[d]列 }
if can(d) then
begin
mk[i]:=true; { 标记第i列已经被占 }
dfs(d+1); { 如果第d行的方法可行,就放下一行 }
mk[i]:=false; { 恢复第i列被占标记 }
end;
end;
end;
begin
fillchar(mk,sizeof(mk),0);
dfs(1);
writeln('Total = ',total);
end.
把N拆分为若干个数的和
问题描述:
给定一个正整数N,假设 0<A1<=A2<=A3...<=As 满足 A1+A2+A3+...+As=N,那么我们称序列A1 A2……As
为N的一个拆封。现在要求N的拆分数目。例如:当N= 6 时
6 = 1 + 1 + 1 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 2
= 1 + 1 + 2 + 2
= 2 + 2 + 2
= 1 + 1 + 1 + 3
= 1 + 2 + 3
= 3 + 3
= 1 + 1 + 4
= 2 + 4
= 1 + 5
= 6
所以 6 的整数拆分个数为 11
{
Problem : N = A1 + A2 ... + As
Algorithm : Depth First Search
Author : tenshi
Date : 2002-07-15 @ SJTU ZZL 111
}
Program N_Sum;
const n=6;
var
a:array[1..n] of integer; { 保存单个拆分。n最多拆封为n个1,所以s<=n }
total:integer; { 方案总数 }
procedure output(s:integer); { 输出。 s为一个拆分的长度 }
var i:integer;
begin
write(n,' =',a[1]:3);
for i:=2 to s do write(' +',a[i]:3);
writeln;
end;
procedure dfs(d,low,rest:integer); { low为当前a[d]的下界,rest为还剩下多少要拆分 }
var i:integer;
begin
if(rest=0) then {找到一组解}
begin
inc(total);
output(d-1);
end;
if( low>rest ) then exit;
{rest已经不能满足low的要求了,所以退出}
for i:=low to rest do
begin
a[d]:=i;
dfs(d+1,i,rest-i);
end;
end;
begin
dfs(1,1,n);
writeln('Total = ',total);
end.
[习题]
http://blog.sina.com.cn/s/blog_493d9ebc0100091a.html
|