文档介绍：从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到“尽头”而没达到目的地的时候, 再倒回上一个出发点, 从另一个可能出发, 继续搜索. 这种不断“倒回一步"寻找解的方法, 称作" 回溯法".
回溯即是较简单、较常用的搜索策略,实质就是一种搜索策略.
A
B
1
2
3
4
5
6
7
8
9
10
从A到B的路线:A---4---6---B
如:找一条从A到B的路线
回溯算法:
假设问题的解的形式为(x1,x2,x3,……..xn),x1∈S1, x2∈S2, xn∈Sn 基本思路:
若已有满足约束条件的部分解,
不妨设为(x1,x2,x3,……xi),I<n,
则添加属于s(i+1)一个 x(i+1) ,
检查(x1,x2,……,xi,x(i+1))是否满足条件,满足了就继续添加一个x(i+2) ∈s(i+2),若所有的x(i+1) ∈ s(i+1)都不能得到部分解,即找不到一个x(i+1) ∈s(i+1)满足条件, 就去掉当前xi,回溯到(xi,x2,……x(i-1)),添加那些未考察过的xi ∈Si,看其是否满足约束条件,为此反复进行,直至得到解或证明无解。
递归算法框架:
procedure try(i);{搜索第i个分量Xi}
begin
if i=n +1 then print;
for Xi ∈Si且使得(X1,X2, 。。。Xi-1,Xi)满足约束条件 do
begin
记录满足条件的Xi;
添加相应的标志;
try(i+1)
{删除标志;恢复之前的状态,根据具体情况选择}
end;
end;
[问题描述]
在n×n的国际象棋盘上,放置n个皇后,使任何一个皇后都不能吃掉另一个,要使任何一个皇后都不能吃掉另一个,需满足的条件是:同一行、同一列、同一对角线上只能有一个皇后。求放置方法.
如:n=4时,有以下2种放置方法.
*
*
*
*
*
*
*
*
一 N皇后问题
输出:
1:2 4 1 3
2:3 1 4 2
方法一:分析:
1、问题解的形式:
x:array [1..n] of integer;
{x[i]:第i个皇后放在第i行,第x[i]列,保证所有皇后不同行}
问题的解变成求(x[1],x[2],。。。X[n]);x[i] ∈{1,2,3,4}
4皇后问题的解: (2,4,1,3), (3,1,4,2)
*
*
*
*
*
*
*
*
2、放置第k(1<=k<=n)个皇后的递归算法:
procedure try(k);
{搜索第k个皇后所在的列x[k]=?,前k -1个已放好,即已求得x[1]…x[k-1] }
var i:integer;
begin
if k=n+1 then print(输出放置方案:数组x);
for i:=1 to n do {搜索第k个皇后所在的列j}
if 第k个皇后能够放置在第 i列 then
begin
放置第k个皇后在第 i列(x[k]=i);
try(k+1);
end;
end;
3、怎样判断:第k个皇后能否放置在第i列:
function place(k,i:integer):boolean;
{第k个皇后能否放在第i列}
var j:integer;
begin
for j:=1 to k-1 do
if (x[j]=i) or (abs(x[j]-i)=abs(j-k)) then
exit(false);
exit(true);
end;
4、输出解:
procedure print;
var j:integer;
begin
count:=count+1;
write(count,':');
for j:=1 to n-1 do write(x[j],' ');
writeln(x[n]);
end;
主程序:try(1)
2、无重复元素的全排列
输入n(<=10)个不同的小些字母,输出n个字符的全部排列。
样例:
输入:
abc
输出:
1:abc
2:acb
3:bac
4:bca
5:cab
6:cba