第三章 回溯

3.1 回溯的设计

3.2 回溯算法的递归实现
 

回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索.

3.1 回溯的设计 

1.用栈保存好前进中的某些状态.

2.制定好约束条件

例1由键盘上输入任意n个符号;输出它的全排列.

program hh;
const n=4;
var i,k:integer;
    x:array[1..n] of integer;
    st:string[n];
    t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
 var i:integer;
 begin
 place:=true;
 for i:=1 to k-1 do
   if x[i]=x[k]  then
     begin place:=false; break end ;
 end;
procedure print;
var i:integer;
 begin
 for i:=1 to n do write(t[x[i]]);
 writeln;
 end;
begin
 input;
 k:=1;x[k]:=0;
 while k>0 do
  begin
  x[k]:=x[k]+1;
  while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
  if x[k]>n then k:=k-1
            else if k=n then print
                       else begin k:=k+1;x[k]:=0 end
  end ;
end.

例2.n个皇后问题:

program hh;
const n=8;
var i,j,k:integer;
    x:array[1..n] of integer;
function place(k:integer):boolean;
 var i:integer;
 begin
 place:=true;
 for i:=1 to k-1 do
   if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
     place:=false  ;
 end;
procedure print;
var i:integer;
 begin
 for i:=1 to n do write(x[i]:4);
 writeln;
 end;
begin
 k:=1;x[k]:=0;
 while k>0 do
  begin
  x[k]:=x[k]+1;
  while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
  if x[k]>n then k:=k-1
            else if k=n then print
                       else begin k:=k+1;x[k]:=0 end
  end ;

end.

回溯算法的公式如下:



3.2 回溯算法的递归实现

由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。

上述例1的递归方法实现如下：

program hh;
const n=4;
var i,k:integer;
    x:array[1..n] of integer;
    st:string[n];
    t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
 var i:integer;
 begin
 place:=true;
 for i:=1 to k-1 do
   if x[i]=x[k]  then
     begin place:=false; break end ;
 end;
procedure print;
var i:integer;
 begin
 for i:=1 to n do write(t[x[i]]);
 writeln;readln;
 end;
procedure try(k:integer);
var i :integer;
begin
 if k=n+1 then begin print;exit end;
 for i:=1 to n do
  begin
   x[k]:=i;
   if place(k) then try(k+1)
  end
end;
begin
 input;
 try(1);
end.

例2：n皇后问题的递归算法如下：

程序1：

program hh;
const n=8;
var i,j,k:integer;
    x:array[1..n] of integer;
function place(k:integer):boolean;
 var i:integer;
 begin
 place:=true;
 for i:=1 to k-1 do
   if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
     place:=false  ;
 end;
procedure print;
var i:integer;
 begin
 for i:=1 to n do write(x[i]:4);
 writeln;
 end;
procedure try(k:integer);
var i:integer;
begin
 if k=n+1 then begin print; exit end;
 for i:= 1 to n do
  begin
  x[k]:=i;
  if place(k) then try(k+1);
  end;
end ;
begin
try(1);
end.

程序2：

说明:当n=8 时有30条对角线分别用了l和r数组控制，

用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:

program nhh;
const n=8;
var s,i:integer;
 a:array[1..n] of byte;
 c:array[1..n] of boolean;
 l:array[1-n..n-1] of boolean;
 r:array[2..2*n] of boolean;
procedure output;
var i:integer;
begin
 for i:=1 to n do write(a[i]:4);   
 inc(s);writeln('  total=',s);
end;
procedure try(i:integer);
 var j:integer;
begin
 for j:=1 to n do
  begin
   if c[j] and l[i-j] and r[i+j] then
    begin
     a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
     if i<n then try(i+1) else output;
     c[j]:=true;l[i-j]:=true;r[i+j]:=true;
    end;
  end;
 end;
begin
 for i:=1 to n do c[i]:=true;
 for i:=1-n to n-1 do l[i]:=true;
 for i:=2 to 2*n do r[i]:=true;
 s:=0;try(1);
 writeln;
end.

　

练习：

1.找出所有从m个元素中选取n(n<=m)元素的组合。

2.设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的

效益表如下:

　 j1 j2 j3 j4 j5 
A 13 11 10 4 7 
B 13 10 10 8 5 
C 5 9 7 7 4 
D 15 12 10 11 5 
E 10 11 8 8 4 

求最佳安排,使效益最高.

3.N个数中找出M个数(从键盘上输入正整数N,M后再输入N个正数),要求从N个数中

找出若干个数,使它们的和为M,把满足条件的数组找出来,并统计组数.

4.地图着色。如下图12个区域用4种颜色着色要求相邻的区域着不同的颜色


5.将任意一正整数(1<n<100)分解成若干正整数的和.

 如:4=1+1+1+1

     =2+1+1

     =2+2

     =3+1.