回溯(計算機算法)

回溯(計算機算法)

本詞條是多義詞,共4個義項
更多義項 ▼ 收起列表 ▲

基本介紹

  • 中文名:回溯
  • 外文名:recall;look back upon;trace
  • 拼音:huí sù
  • 解釋:上溯,向上推導,向內推導
概念,步驟,遞歸回溯,回溯設計,程式,運用,

概念

回溯法也稱試探法,它的基本思想是:從問題的某一種狀態(初始狀態)出發,搜尋從這種狀態出發所能達到的所有“狀態”,當一條路走到“盡頭”的時候(不能再前進),再後退一步或若干步,從另一種可能“狀態”出發,繼續搜尋,直到所有的“路徑”(狀態)都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法,就稱作“回溯法”。

步驟

用回溯算法解決問題的一般步驟為:
一、定義一個解空間,它包含問題的解。
二、利用適於搜尋的方法組織解空間。
三、利用深度優先法搜尋解空間。
四、利用限界函式避免移動到不可能產生解的子空間。問題的解空間通常是在搜尋問題的解的過程中動態產生的,這是回溯算法的一個重要特性。
回溯
回溯法是一個既帶有系統性又帶有跳躍性的的搜尋算法。它在包含問題的所有解的解空間樹中,按照深度優先的策略,從根結點出發搜尋解空間樹。算法搜尋至解空間樹的任一結點時,總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結點為根的子樹的系統搜尋,逐層向其祖先結點回溯。否則,進入該子樹,繼續按深度優先的策略進行搜尋。回溯法在用來求問題的所有解時,要回溯到根,且根結點的所有子樹都已被搜尋遍才結束。而回溯法在用來求問題的任一解時,只要搜尋到問題的一個解就可以結束。這種以深度優先的方式系統地搜尋問題的解的算法稱為回溯法,它適用於解一些組合數較大的問題.

遞歸回溯

遞歸回溯:由於回溯法是對解空間的深度優先搜尋,因此在一般情況下可用遞歸函式來實現回溯法如下:
procedure try(i:integer);
var
begin
if i>n then 輸出結果
else for j:=下界 to 上界do
begin
x:=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,回溯到(x1,x2,……x(i-1)),添加那些未考察過的xi屬於s1,看其是否滿足約束條件,為此反覆進行,直至得到解或證明無解。

回溯設計

1.用棧保存好前進中的某些狀態.
2.制定好約束條件
【例1】從1到X這X個數字中選出N個,排成一列,相鄰兩數不能相同,求所有可能的排法。每個數可以選用零次、一次或多次。例如,當N=3、X=3時,排法有12種:121、123、131、132、212、213、231、232、312、313、321、323。
【分析】以N=3,X=3為例,這個問題的每個解可分為三個部分:第一位,第二位,第三位。先寫第一位,第一位可選1、2或3,根據從小到大的順序,我們選1;那么,為了保證相鄰兩數不同,第二位就只能選2或3了,我們選2;最後,第三位可以選1或3,我們選1;這樣就得到了第一個解"121"。然後,將第三位變為3,就得到了第二個解"123"。此時,第三位已經不能再取其他值了,於是返回第二位,看第二位還能變為什麼值。第二位可以變為3,於是可以在"13"的基礎上再給第三位賦予不同的值1和2,得到第三個解"131"和"132"。此時第二位也已經不能再取其他值了,於是返回第一位,將它變為下一個可取的值2,然後按順序變換第二位和第三位,得到"212"、"213"、"231""232"。這樣,直到第一位已經取過了所有可能的值,並且將每種情況下的第二位和第三位都按上述思路取過一遍,此時就已經得到了該問題的全部解。
由以上過程可以看出,回溯法的思路是:問題的每個解都包含N部分,先給出第一部分,再給出第二部分,……直到給出第N部分,這樣就得到了一個解。若嘗試到某一步時發現已經無法繼續,就返回到前一步,修改已經求出的上一部分,然後再繼續向後求解。這樣,直到回溯到第一步,並且已經將第一步的所有可能情況都嘗試過之後,即可得出問題的全部解。

程式

program p11_14;
const n=3;x=3;
var a:array [1..n] of 0..x;
p,c,I:integer;
begin
writeln;
p:=1; {從第一位開始}
c:=1; {從1開始選數字}
repeat
repeat
if (p=1) or (c<>a[p-1]) then {第一位可填任意數}
begin
a[p]:=c; {將數字C填到第P位上}
if p=n then {若已填到最後一位,則表明已求出了一個解}
begin
for I:=1 to n do write(a); {顯示這個解}
writeln;
end;
P:=P+1; {繼續下一位}
C:=1; {下一位從1開始}
End
Else
C:=c+1; {下一位仍然從1開始選數字}
Until (p>n) or (c>X); {直到已填完最末位,或本位再無數字可選}
Repeat
P:=p-1; {向前回溯}
Until (p=0) or (a[p]<x) ; {回溯到尚有選擇餘地的一位,或到首位}
If p>0 then {若非首位,則將該位變為下一個可取的數字}
C:=a[P]+1;
Until p=0; {將第一位回溯完畢後,程式結束}
End.
由鍵盤上輸入任意n個符號,輸出它的全排列。(一個符號只能出現一次)
program hh;
const n=3;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure 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=x[k] then begin place:=false; break end;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x]);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 ;
readln
end.

運用

在編譯原理中
回溯(計算機算法)
如左圖,在發生虛假匹配時需要進行回溯,就是退回到開始的位置

相關詞條

熱門詞條

聯絡我們