回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法的一般描述(一般表达 规律 空间树)

用回溯法解题的一般步骤：(用回溯法解决八皇后问题的C语言程序 用回溯法解决八皇后问题的PASCAL语言程序 回溯法解决迷宫问题)

回溯法的一般描述

一般表达

可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

规律

我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<=i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i≥j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

空间树

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：

设Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，xn，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。

因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，xi），…，直到i=n为止。

在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解

用回溯法解题的一般步骤：

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法C语言举例

八皇后问题是能用回溯法解决的一个经典问题。

八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

用回溯法解决八皇后问题的C语言程序

#include<stdio.h>

#include<stdlib.h>

int col[9]={0},a[9];

int b[17],c[17];

main()

{

int m,good;

int i,j,k;

char q;

for(i=0;i<17;i++)

{

if(i<9) a[i]=1;

b[i]=1;c[i]=1;

}

good=1;

col[1]=1;

m=1;

while(col[0]!=1)

{

if(good)

if(m==8)

{

for(i=1;i<9;i++)

printf("col[%d] %d\",i,col[i]);

printf("input 'q' to quit\");

scanf("%c",&q);

getchar();

if(q=='q'||q=='Q') exit(0);

while(col[m]==8)

{

m--;

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1;

}

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1;

col[m]++;

}

else

{

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=0;

m++;

col[m]=1;

}

else

{

while(col[m]==8)

{

m--;

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1;

}

col[m]++;

}

good=a[col[m]]&&b[m+col[m]]&&c[8+m-col[m]];

}

}

用回溯法解决八皇后问题的PASCAL语言程序

var

n,k,t,i:longint;

x:array[1..100] of integer;

function pa(k:integer):boolean;

begin

pa:=true;

for i:=1 to k-1 do

if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;

end;

procedure try(k:integer);

var

i:integer;

begin

if k>n then

begin

t:=t+1;

exit;

end;

for i:=1 to n do

begin

x[k]:=i;

if pa(k) then try(k+1);

end;

end;

begin

read(n);

t:=0;

try(1);

write(t);

end.

回溯法解决迷宫问题

#include<stdio.h>

#include<stdlib.h>

#define m 5

#define n 6

int sf=0;

int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};

void search(int x,int y)

{

if((x==m-1)&&(y==n-1))

sf=1;

else

{

mase[x][y]=1;

if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)

search(x,y+1);

if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)

search(x+1,y);

if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)

search(x,y-1);

if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)

search(x-1,y);

}

mase[x][y]=0;

if(sf==1)

mase[x][y]=5;//通过路径用数字的表示

}

int main()

{

int i=0,j=0;

//clrscr();

search(0,0);

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

printf("%d",mase[i][j]);

printf("\");

}

system("pause");

return 0;

}

回溯法解决迷宫问题PASCAL语言

program migong;

var

n,k,j,x,y:integer;

a:array[0..10000,0..10000] of integer;

b:array[0..1000000,0..2] of integer;

procedure search(x,y,i:integer);

begin

a[x,y]:=1;

if (x=n) and (y=n) then

begin

for j:=1 to i-1 do

writeln(j,':(',b[j,1],',',b[j,2],')');

writeln(i,':(',x,',',y,')');

halt;

end;

if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;

if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;

if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;

if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;

a[x,y]:=0;

end;

begin

read(n);

for k:=1 to n do

for j:=1 to n do

read(a[k,j]);

for k:=0 to n+1 do

begin

a[k,0]:=-1;

a[k,n+1]:=-1;

a[n+1,k]:=-1;

a[0,k]:=-1;

end;

x:=1;y:=1;

if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;

if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;

end.