回溯控制问题最好用的方法来解决

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

（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: );
while(not_finish) //not_finsh=1:处理未结束
{
while(not_finish && i<Queens+1) //处理未结束
{
for(flag=1,k=1;flag && k<i;k++)//判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判断是否有多个皇后在对角线
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]:: [%2d]:,count);
for(k=1;k<=Queens;k++) //输出结果
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;
procere 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=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></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;
procere 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.

Ⅱ Pascal算法之回溯及递推详细介绍、

在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。

在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。

递推算法的关键是认真分析题意，发现递推关系，正确写出递推公式，求得边界条件，然后用循环实现即可。总结

1.递推算法的基本形式，是指编程者让计算机循环求得一序列数值，而后一项的计算结果是由上一项或多项推导出来的。有时，我们为求得一个数列的某一项，我们不得不从第一项开始，逐个计算前面每一项的值。虽然这样做的效率不很高，但它能帮助我们解决许多实际问题。

2.无论是顺着还是逆着递推，其关键是递推公式是否正确，边界条件是否正确。二者有一个出错。则所有递推结果将都是错误的。

【】

例1：已知数列1，2，5，10，17，26，37...求数列的第n项。

通过分析，我们可以发现，数列后面的数在前一项的基础上以1，3，5，7，9，11的规律增长，则可以得出增长规律的表达式为2*n-3,也就是a(1)=1,a(n)=a(n-1)+2*n-3;

还有一个规律，我们可以发现每一项依次为从0开始的自然数的平方再加1，即

(n-1)2+1,第一项（1-1）2+1，第二项（2-1）2+1，第三项（3-1）2+1... 例2:阶梯问题：题目的意思是：有N级阶梯，可以一步走上一级，也可以一步走两级，求从阶梯底走到顶端可以有多少种不同的走法。

这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级,也就是说增加的第三级有两种处理方法，第一种就是直接作为一级走一步，那么就和两级的走法一致，另一种就是与第二级合并作一步走，那么就和一级的走法一致，加起来就是一级的方法和二级的走法之和），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。很明显，这是一个菲波拉契数列。到这里，读者应能很熟练地写出这个程序。在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。

例3：猴子吃桃问题：山中住有五只猴。一天，老大看见一堆桃子，想把桃子据为已有，却担心让老二老三知道了说自己太贪心。于是将桃分成相等的两份，却发现剩余一个，于是，老大吃掉这一个以后，再带走这堆桃的二分之一。第二天，老二也看到了这堆桃，其想法和做法与老大一样，老三老四老五也和他们的兄长想到一块去了。结果等老五吃完一个，带走一半以后，这堆桃还剩余11个。请编程计算当初这堆桃共有多少个。

这个下题目明眼人一看便知，我们如果按兄弟吃桃把桃的相反顺序倒推过去，就能知道当初桃子的总数。其递推的公式是a[n-1]=a[n]*2+1。递推的初始值是a[5]=11（又称边界条件），待求a[0]的值。相信现在大家能很容易就能写出正确的程序。在这里不过是想说明一下，递推算法不仅可以顺着推、也可逆着推的道理。

【】

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

用回溯算法解决问题的一般步骤为：

一、定义一个解空间，它包含问题的解。

二、利用适于搜索的方法组织解空间。

三、利用深度优先法搜索解空间。

四、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.

[递推是学习材料，回溯是网络]

江静
游客 回答于：2010-8-29 15:05:18
递归

递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写

程序能是程序变得简洁和清晰.

2.1 递归的概念


1.概念

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

如:

procere a;

begin

.

.

.

a;

.

.

.

end;

这种方式是直接调用.

又如:

procere b; procere c;

begin begin

. .

. .

. .

c; b;

. .

. .

. .

end; end;

这种方式是间接调用.

例1计算n!可用递归公式如下:

1 当 n=0 时

fac(n)={n*fac(n-1) 当n>0时

可编写程序如下:

program fac2;

var

n:integer;

function fac(n:integer):real;

begin

if n=0 then fac:=1 else fac:=n*fac(n-1)

end;

begin

write('n=');readln(n);

writeln('fac(',n,')=',fac(n):6:0);

end.例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.

设n阶台阶的走法数为f(n)

显然有

1 n=1

f(n)={2 n=2

f(n-1)+f(n-2) n>2

可编程序如下：

program louti;

var n:integer;

function f(x:integer):integer;

begin

if x=1 then f:=1 else

if x=2 then f:=2 else f:=f(x-1)+f(x-2);

end;

begin

write('n=');read(n);

writeln('f(',n,')=',f(n))

end.

2.2 如何设计递归算法
1.确定递归公式

2.确定边界(终了)条件

练习:

用递归的方法完成下列问题

1.求数组中的最大数

2.1+2+3+...+n

3.求n个整数的积

4.求n个整数的平均值

5.求n个自然数的最大公约数与最小公倍数

6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题

例3 梵塔问题

如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子

从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上

不能出现大盘压小盘.找出移动次数最小的方案.

程序如下:

program fanta;

var

n:integer;

procere move(n,a,b,c:integer);

begin

if n=1 then writeln(a,'--->',c)

else begin

move(n-1,a,c,b);

writeln(a,'--->',c);

move(n-1,b,a,c);

end;

end;

begin

write('Enter n=');

read(n);

move(n,1,2,3);

end.

例4 快速排序

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

程序如下:

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

练习:

1.计算ackerman函数值:

n+1 m=0

ack(m,n)={ ack(m-1,1) m<>0 ,n=0

ack(m-1,ack(m,n-1)) m<>0,n<>0

求ack(5,4)回溯

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

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];
procere 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;
procere 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;
procere 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];
procere 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;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere 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;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere 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;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere 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项工作每人只能从事一项,它们的

效益表如下:求最佳安排,使效益最高.

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.

Ⅲ 回溯法在问题的解空间树中,按什么策略

回溯法在问题的解空间树中，按深度优先策略。

相关介绍：

回溯法（英语：backtracking），又称为试探法，是一种选优搜索法，按选优条件向前搜索，以达到目标。回溯法采用试错的思想，它尝试分步的去解决一个问题。

在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

Ⅳ 哪里有基本的回溯法教程

没有专门的回溯法教程，可以看下一般的信息学竞赛的书哈，下面找了一个，先看下哈：

一、回溯法：
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：
procere try(i:integer);
var
begin
if i>n then 输出结果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;
end;
end;

说明：
i是递归深度；
n是深度控制，即解空间树的的高度；
可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；

搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。
回溯即是较简单、较常用的搜索策略。
基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。

例子:

例1、八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。
（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）

program tt;var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer;procere print;begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' '); writeln;end;procere try(i:integer);var j:integer;begin for j:=1 to 8 do {每个皇后都有8种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突} begin a[i]:=j; {摆放皇后} b[j]:=1; {宣布占领第J行} c[i+j]:=1; {占领两个对角线} d[i-j]:=1; if i<8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后} else print; {完成任务，打印结果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end;end;begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; end; try(1);{从第1个皇后开始放置}end.
例2、跳马问题。在5*5格的棋盘上，有一个国家象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘后再条回出发点。

program jump;
var
h:array[-1..7,-1..7] of integer;
a,b:array[1..8] of integer;
i,j,num:integer;
procere print;
var i,j:integer;
begin
num:=num+1;
if num<=5 then
begin
for i:=1 to 5 do
begin
for j:=1 to 5 do write(h[i,j]:4);
writeln;
end;
writeln;
end;
end;
procere try(x,y,i:integer);
var j,u,v:integer;
begin
for j:=1 to 8 do
begin
u:=x+a[j];
v:=y+b[j];
if h[u,v]=0 then
begin h[u,v]:=i;
if i<25 then try(u,v,i+1)
else print;
h[u,v]:=0
end;
end;
end;
begin
for i:=-1 to 7 do
for j:=-1 to 7 do
if (i>=1)and(i<=5)and(j>=1)and(j<=5)
then h[i,j]:=0
else h[i,j]:=1;
a[1]:=2;b[1]:=1;
a[2]:=1;b[2]:=2;
a[3]:=-1;b[3]:=2;
a[4]:=-2;b[4]:=1;
a[5]:=-2;b[5]:=-1;
a[6]:=-1;b[6]:=-2;
a[7]:=1;b[7]:=-2;
a[8]:=2;b[8]:=-1;
num:=0;
h[1,1]:=1;
try(1,1,2);
writeln('num=',num);
end.

例3：素数环： 把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
〖问题分析〗 非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法：
与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

〖算法流程〗
1、数据初始化；
2、递归填数：
判断第J种可能是否合法；
A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；
B、如果不合法：选择下一种可能；

参考程序：

program tt;var a:array [1..20] of integer; k:integer;function pd1(j,i:integer):boolean;begin pd1:=true; for k:=1 to i-1 do if a[k]=j then begin pd1:=false;exit;end;end;function pd2(x:integer):boolean;begin pd2:=true; for k:=2 to trunc(sqrt(x)) do if x mod k=0 then begin pd2:=false; exit;end;end;function pd3(j,i:integer):boolean;begin if i<20 then pd3:=pd2(j+a[i-1]) else pd3:=pd2(j+a[i-1]) and pd2(j+1);end;procere print;begin for k:=1 to 20 do write(a[k]:4); writeln;end;procere try(i:integer);var j:integer;begin for j:=2 to 20 do begin if pd1(j,i) and pd3(j,i) then begin a[i]:=j; if i=20 then begin print; halt;end else try(i+1); a[i]:=0; end; end;end;begin for k:=1 to 20 do a[k]:=0; a[1]:=1; try(2);end.

Ⅳ 用递归回溯法设计旅行售货员问题的算法

一、回溯法：
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：
procere try(i:integer);
var
begin
if i>n then 输出结果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;
end;
end;

说明：
i是递归深度；
n是深度控制，即解空间树的的高度；
可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；

搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。
回溯即是较简单、较常用的搜索策略。
基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。

Ⅵ pascal回溯问题

回溯法也称为试探法，该方法放弃关于问题规模大小的限制，并将问题的方案按某种顺序逐一枚举和试验。发现当前方案不可能有解时，就选择下一个方案，倘若当前方案不满足问题的要求时，继续扩大当前方案的规模，并继续试探。如果当前方案满足所有要求时，该方案就是问题的一个解。在回溯中，放弃当前方案，寻找下一介方案的过程称为回溯，
在一般情况下需要用计算机解决的问题有两种类型：
1、 以用精确的数学公式或明确的算法语言来描述的问题。如圆周率的计算、多位数的阶乘等。
2、 完成一件事情的过程中，要经过若干个步骤，而每一个步骤都有若干种可能的分支，为了圆满地完成任务，必须遵守一些规则，但这些规则又无法精确地用数学公式或语言来描述的。
对于第二类问题，一般采用穷举或回溯的方法来解决。穷举法是将问题的所有可能性都一一例举出来，而回溯是穷举算法的一种控制策略，是把有可能圆满地完成任务的解法进行例举，是一种组织得井井有条的，能避免不必要的穷举搜索算法。它的基本思想是：在搜索过程中，由于方案在当前状态下求解不到，需返回搜索进程中的上一环节，并重新寻求解答。
如何学会用回溯的方法解题，先来看下题用穷举法是如何解题的：我们为了便于对问题进一步分析，以下题为例（皇后问题）：
问题描述：在一个4×4的棋盘上放置4个皇后，并使她们不能互相攻击，既在同一个行，同一个列上，同一个对角线不能有多于一个以上的皇后,问有多少种放置的方法。
穷举法：
列出4个皇后在棋盘上的所有可能性，然后一一判断是否互相攻击，程序如下
回溯法：
在寻找解答时需要一个环节一个环节地考虑，当某一个环节的各个方案都已试验过但仍未找到合适的解，得退到上一个环节，对未有试探过的方案继续试探，程序如下：
program qi16;
var
i,t,an:word;
co,bo:boolean;
a:array[1..4] of byte;
const
n=4;ct=4;
begin
t:=0;an:=0;
repeat
inc(t); a[t]:=0;
repeat
inc(a[t]);
bo:=false;
co:=false;
if a[t]>ct then bo:=true
else begin
co:=true;
for i:=t-1 downto 1 do {与已放了皇后的行逐行比较}
if (t-i=abs(a[t]-a[i])) or (a[t]=a[i]) then
co:=false;
end;
if bo then begin dec(t); {如果各个方案都已试验过但仍未找到合适的解则回溯}
if t=0 then co:=true;
end;
until co;
if t>=n then
begin {输出结果}
inc(an);
write('#',an,' ':10);
for i:=1 to n do write(chr(64+i),':',a[i],' ');
writeln
end
until t=0;
if an=0 then writeln('No Answer');
end.

Ⅶ 简述回溯法的2种算法框架,并分别举出适合用这两种框架解决的一个问题实例

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束

一般表达
可用回溯法求解的问题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的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

Ⅷ Free Pascal 中的回溯算法，具体讲一下

1 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 一、定义一个解空间，它包含问题的解。 二、利用适于搜索的方法组织解空间。 三、利用深度优先法搜索解空间。 四、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：procere try(i:integer);varbeginif i>n then 输出结果else for j:=下界 to 上界 dobeginx:=h[j];if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;end;end; 说明：i是递归深度； n是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。回溯即是较简单、较常用的搜索策略。基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。