回溯控制問題最好用的方法來解決

Ⅰ 回溯法的用回溯法解題的一般步驟

（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，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。