基本介紹
- 中文名：回溯
- 外文名：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.
運用
在編譯原理中
如左圖，在發生虛假匹配時需要進行回溯，就是退回到開始的位置
