標籤: 暫無標籤

回溯法(探索與回溯法)是一種選優搜索法,按選優條件向前搜索,以達到目標。但當探索到某一步時,發現原先選擇並不優或達不到目標,就退回一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀態的點稱為「回溯點」。

1回溯法的一般描述

一般表達
可用回溯法求解的問題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的一個解。但顯然,其計算量是相當大的。
空間樹
回溯法首先將問題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的一個解

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

(1)針對所給問題,定義問題的解空間;
(2)確定易於搜索的解空間結構;
(3)以深度優先方式搜索解空間,並在搜索過程中用剪枝函數避免無效搜索。
回溯法C語言舉例
八皇后問題是能用回溯法解決的一個經典問題。
八皇后問題是一個古老而著名的問題。該問題是十九世紀著名的數學家高斯1850年提出:在8X8格的國際象棋上擺放八個皇后,使其不能互相攻擊,即任意兩個皇后都不能處於同一行、同一列或同一對角線上,問有多少種擺法。
用回溯法解決八皇后問題的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("\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]:=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.

相關評論

同義詞:暫無同義詞