回溯

回溯

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

  • 中文名稱
    回溯
  • 外文名稱
    back
  • 拼音
    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.

在編譯原理中的運用

回溯

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

相關詞條

相關搜尋

其它詞條