回溯[漢語詞語]

回溯是一個漢語詞語，讀音huí sù，英文recall;look back upon;trace，解釋是上溯,向上推導,向內推導。

基本信息

• 名稱：回溯

漢語詞語

【詞目】回溯

【拼音】huí sù

【基本解釋】回憶：～過去，瞻望未來。

回:還，走向原來的地方：如回家。 掉轉：回首（回頭看）。回顧。回眸。回曖。妙手回春。

溯: 溯 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.

運用

在編譯原理中

回溯[漢語詞語]

如左圖，在發生虛假匹配時需要進行回溯，就是退回到開始的位置