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

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

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

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

回溯法C语言举例

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

八皇后问题是一个古老而著名的问题。该问销差题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上禅斗衫的状态 ：

a[] a[i]=0表示第i行上还没有皇后；

b[] b[i]=0表示第i列反斜线/上没有皇后；

c[] c[i]=0表示第i列正斜线\上没有皇后。

棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线\上的方格的行号与列号之差均相同，这就是判断斜线的依据。

初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #include<stdio.h>

#include<stdlib.h>

#define Queens 8

int a[Queens+1]//八皇后问题的皇后所在每一行位置，从1开始算

int main()

{

int i,k,flag,not_finish=1,count=0

i=1//初始

a[1]=1

printf(the possible configuration of 8 queesns are:\n)

while(not_finish) //not_finsh=1:处理未结束

{

while(not_finish &&i<Queens+1) //处理未结束

{

for(flag=1,k=1flag &&k<ik++)//判断是否有多个皇后在同一行

if(a[k]==a[i])

flag=0

for(k=1flag &&k<ik++) //判断是否有多个皇后在对角线

if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))

flag=0

if(!flag) //若存在矛盾 重设第i个元素

{

if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值

{

i--//退回一步 重新试探处理前一个元素

if(i>1 &&a[i]==Queens)

a[i]=1// 当a[i]为 Queens时 将a[i]的值重置

else

if(i==1 &&a[i]==Queens)//当第一未位的值达到Queens时结束

not_finish=0

else

a[i]++

}

else

if(a[i]==Queens)

a[i]=1

else

a[i]++

}

else

if(++i<=Queens) //若前一个元素的值为Queens

if(a[i-1]==Queens)

a[i]=1

else //否则元素为前一个元素的下一个值

a[i]=a[i-1]+1

}

if (not_finish)

{

++count

printf((count-1)%3?[%2d]::\n[%2d]:,count)

for(k=1k<=Queensk++) //输出结果

printf(%d,a[k])

if(a[Queens-1]<Queens)

a[Queens-1]++

else

a[Queens-1]=1

i=Queens-1

}

}

system(pause)

} 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

#include

#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=0i<mi++) p=></mi++)>

{

for(j=0j<nj++) p=></nj++)>

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

printf(\n)

}

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]:=xb[i,2]:=ysearch(x-1,y,i+1)end

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

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

if a[x,y+1]=0 then begin b[i,1]:=xb[i,2]:=ysearch(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:=1y:=1

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

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

end.

约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruning function）。

使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法(backtracking)

使用剪枝函数的广度优先生成状态空间树中结点的求解方法称为分支/枝限界法(branch-and-bound)

回溯法/分支限界法 = 穷举 + 剪枝。

回溯法是一个既带有系统性又带有跳跃性的搜索算法；

这种以深度优先的方式系统地搜索问题的解得算法称为回溯法。其实回溯法就是对 隐式图 的深度优先搜索算法

回溯是穷举方法的一个改进，它在所有可行的选择中，系统地搜索问题的解。它假定解可以由向量形式 (x1,x2,...,xn) 来 表示，其中xi的值表示在第i次选择所作的决策值，并以深度优先的方式遍历向量空间,逐步确定xi 的值，直到解被找到。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束，来确保解的正确性。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。( 找出解空间树中满足约束条件的所有解 )

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。 这种方法适用于解一些组慎链合数较大的问题 。

（1）问题框架

（2） 递归的算法框架

回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：

（3）非宽指孙递归回溯框架（递归转非递归，这里可以参考树的遍历，或者看上篇博客——递归算法介绍）

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为 ，则回溯法所需的计算空间通常为 。而显式地存储整个解空间则需要 或 内存空间。

回溯法解题的时候常遇到两种类型的解空间树：

用回溯法搜索子集树的算法框架可描述为：逗宏

用回溯法搜索排列树的算法框架可描述为：

---