回溯演算法思想

『壹』 五大基本演算法——回溯法

回溯法是一種選優搜索法（試探法）。

基本思想：將問題P的狀態空間E表示成一棵高為n的帶全有序樹T，把求解問題簡化為搜索樹T。搜索過程採用 深度優先搜索 。搜索到某一結點時判斷該結點是否包含原問題的解，如果包含則繼續往下搜索，如果不包含則向祖先回溯。

通俗來說，就是利用一個樹結構來表示解空間,然後從樹的根開始深度優先遍歷該樹，到不滿足要求的葉子結點時向上回溯繼續遍歷。

幾個結點：
擴展結點：一個正在產生子結點的結點稱為擴展結點
活結點：一個自身已生成但未全部生成子結點的結點
死結點：一個所有子結點已全部生成的結點

1、分析問題，定義問題解空間。

2、根據解空間，確定解空間結構，得 搜索樹 。

3、從根節點開始深度優先搜索解空間（利用 剪枝 避免無效搜索）。

4、遞歸搜索，直到找到所要求的的解。

1、子集樹
當問題是：從n個元素的集合S中找出滿足某種性質的子集時，用子集樹。
子集樹必然是一個二叉樹。常見問題：0/1背包問題、裝載問題。

遍歷子集樹時間復雜度：O（2^n）

2、排列樹
當問題是：確定n個元素滿足某種排列時，用排列數。常見問題：TSP旅行商問題，N皇後問題。

遍歷排列樹時間復雜度：O（n!）

通俗地講，結合Java集合的概念，選擇哪種樹其實就是看最後所得結果是放入一個List（有序）里，還是放入一個Set（無序）里。

剪枝函數能極大提高搜索效率，遍歷解空間樹時，對於不滿足條件的分支進行剪枝，因為這些分支一定不會在最後所求解中。

常見剪枝函數：

約束函數（對解加入約束條件）、限界函數（對解進行上界或下界的限定）

滿足約束函數的解才是可行解。

1、0/1背包問題

2、TSP旅行商問題

3、最優裝載問題

4、N-皇後問題

具體問題可網路詳細內容。

『貳』 常見演算法思想6：回溯法

回溯法也叫試探法，試探的處事方式比較委婉，它先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一進行枚舉和檢驗。當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探演算法中，放棄當前候選解，並繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

（1）針對所給問題，定義問題的解空間。
（2）確定易於搜索的解空間結構。
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。

回溯法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，馬上會自覺地退回一步重新選擇，然後繼續向前試探，如此這般反復進行，直至得到解或證明無解時才死心。

下面是回溯的3個要素。
（1）解空間：表示要解決問題的范圍，不知道範圍的搜索是不可能找到結果的。
（2）約束條件：包括隱性的和顯性的，題目中的要求以及題目描述隱含的約束條件，是搜索有解的保證。
（3）狀態樹：是構造深搜過程的依據，整個搜索以此樹展開。

下面是影響演算法效率的因素：

回溯法搜索解空間時，通常採用兩種策略避免無效搜索，提高回溯的搜索效率:

為縮小規模，我們用顯示的國際象棋8*8的八皇後來分析。按照國際象棋的規則，皇後的攻擊方式是橫，豎和斜向。
皇後可以攻擊到同一列所有其它棋子，因此可推導出每1列只能存在1個皇後，即每個皇後分別占據一列。棋盤一共8列，剛好放置8個皇後。

為了擺放出滿足條件的8個皇後的布局，可以按如下方式逐步操作：

把規模放大到N行N列也一樣，下面用回溯法解決N皇後問題：

執行：

『叄』 回溯法的基本思想是什麼

回溯法又稱試探法。回溯法的基本做法是深度優先搜索，是一種組織得井井有條的、能避免不必要重復搜索的窮舉式搜索演算法。
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
當我們遇到某一類問題時，它的問題可以分解，但是又不能得出明確的動態規劃或是遞歸解法，此時可以考慮用回溯法解決此類問題。回溯法的優點在於其程序結構明確，可讀性強，易於理解，而且通過對問題的分析可以大大提高運行效率。但是，對於可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花宏歷滑費的時間比較長。
對於用回溯法求解的問題，首先要將問題進行適當的轉化，得出狀態空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優先搜索這棵樹，枚舉每種可能的解的情況；從而得出結果。但是，回溯法中通過構造約束函數，可以大大提升程序效率，因為在深度優先搜索的過程中，不斷的將每個解（並不一定是完整的，事實上這也就是構造約束函數的意義所在）與約束函數進行對照從而刪除一些不可能的解，這樣就不必繼續把解的剩餘部分列出從而節省部分時間。
回溯法中，首先需要明確下面三個概念：
（一）約束函數：約束函數是根據題意定出的。通過描述合法解的一般特徵用於去除不合法的解，從而避免繼續搜索出這個不合法解的剩餘部分。因此，約束函數是對於任何狀態空間樹上的節點都有效、等價的。
（二）狀態空間樹：剛剛已經提到，狀態空間樹是一個對所有解的圖形描述。樹上的每個子節點的解都只有一個部分與父節點不同。
（三）擴展節點、活結點、死結點：所謂擴展節點，就是當前正在求出它的子節點的節點，在深度優先搜索中，爛亂只允許有一個擴展節點。活結點就是通過與約束函數的對照，節點本身和其父節點均滿足約束函數要求的節點；死結點反之。由此很容易知道死結點是不必求出其子節點的（沒有意義）。
利用回溯法解題的具體步驟
首先，要通過讀題完成下面三個步驟：
(1)描述解的形式，定義一個解空間，它包含問題的所有解。
(2)構造狀態空間樹。
(3)構造約束函數（用於殺死節點）。

然後就要通蔽臘過深度優先搜索思想完成回溯，完整過程如下：
(1)設置初始化的方案（給變數賦初值，讀入已知數據等）。
(2)變換方式去試探，若全部試完則轉(7)。
(3)判斷此法是否成功（通過約束函數），不成功則轉(2)。
(4)試探成功則前進一步再試探。
(5)正確方案還未找到則轉(2)。
(6)已找到一種方案則記錄並列印。
(7)退回一步（回溯），若未退到頭則轉(2)。
(8)已退到頭則結束或列印無解

『肆』 簡述回溯法的2種演算法框架,並分別舉出適合用這兩種框架解決的一個問題實例

回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
基本思想
在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索演算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束

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

規律
我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<=i）元組（x1，x2，…，xj）一定也滿足d中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反d中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反d中僅涉及到x1，x2，…，xi的一個約束，n≥i≥j。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…，xj）違反d中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題p的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。

『伍』 pascal 回溯 拼木條 問題 求解析 要詳細

一、回溯法的基本思想
回溯法又稱試探法。回溯法的基本做法是深度優先搜索，是一種組織得井井有條的、能避免不必要重復搜索的窮舉式搜索演算法。
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
具體說,就是：在搜索(依次用各種方法一一去試探)的過程中，當在P點有N種選擇，則從第一種開始嘗試，若第K種可行，即這一步搜索成功，打上標記，再向前(即 P+1點)搜索；如在P點搜索失敗(所有的方法都宴羨試探過，沒有一種可行)，為了擺脫當前的失敗，就返回搜索進程中的上一點(即P-1點)，再用第K+1種方法(假設上次在P-1點用第K種方法搜索成功，必須明確以前用過的方法不能再用，否則會陷入死循環)再去搜索，重新尋求解答。這樣搜索回溯，再搜索再回溯，如能搜索到終點，問題有解，如最後回溯到出發點，問題就無解。

這種在搜索的過程中，先對深度大的點進行擴展的演算法，叫深度優先搜索法。
設搜索深度指針為P，搜索方法指針為I，可把深度優先搜索演算法寫成如下形式：
P:=0;I:=0;
repeat
I:=I+1; (搜索到一種方法)
IF 搜索方法有效 THEN
begin
試探產生臨時新結點
IF 符合條件 THEN
begin
P:=P+1;(深入一步)，新結點記錄，I:=0，再全方位搜索
IF到達終點 THEN 結束搜索，輸出結果;
End;
End
ELSE (搜索的方法無效)
begin
I:=上次搜索的方法(下一輪將用I的下一方法去搜索);P:=P-1(後退一步返回上結點);
END;
UNTIL P=0;
IF P=0 THEN {深度飢祥岩指針P為0，表示已退到起始狀態，是本題無解的標}
無解
ELSE
輸出爛御結果;
END.

太長了，放不下。要的話可以吧課件給你。

『陸』 回溯演算法的基本思想

回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。八皇後問題就是回溯演算法的典型，第一步按照順序放一個皇後，然後第二步符合要求放第2個皇後，如果沒有位置符合要求，那麼就要改變第一個皇後的位置，重新放第2個皇後的位置，直到找到符合條件的位置就可以了。回溯在迷宮搜索中使用很常見，就是這條路走不通，然後返回前一個路口，繼續下一條路。回溯演算法說白了就是窮舉法。不過回溯演算法使用剪枝函數，剪去一些不可能到達 最終狀態（即答案狀態）的節點，從而減少狀態空間樹節點的生成。回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。

『柒』 四皇後問題求解

本章內容來自《妙趣橫生的演算法》蠢做一書中。

回溯法是一種非常有效，適用范圍相當廣泛的演算法設計思想。許多復雜的問題，規模較大的問題都可以使用回溯法求解。因此回溯法又有「通用解題方法」的美稱。

回溯法的基本思想是：在包含問題的所有解的解空間樹中，按照氏檔爛深度優先搜索的策略，從根結點出發深度 探索 解空間樹。當 探索 到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續 探索 下去；如果該結點不包含問題的解，那就說明以該結點為根結點的子樹一定不包含「剪枝」操作。

如果應用回溯法求解問題的所有解，要回溯到解空間樹的樹根，這樣根結點的所有子樹都被 探索 到才結束。如果只要求殲漏解問題的一個解，問題的最終解，因此要跳過對以該結點為根的子樹的系統 探索 ，逐層向其祖先結點回溯。這個過程叫做解空間樹的那麼在 探索 解空間樹時，只要搜索到問題的一個解就可以結束了。

應用回溯法的思想求解四皇後問題

分析：

上面一節中已經詳細介紹了回溯法解決四皇後問題的基本過程。在這里將給出具體的演算法描述和程序清單。

其實在解決四皇後問題時，並不一定要真的構建出這樣一棵解空間樹，它完全可以通過一個遞歸回溯來模擬。所謂解空間樹只是一個邏輯上的抽象。當然也可以用樹結構來真實地創建出一棵解空間樹，不過那樣會比較浪費空間資源。

運行結果：

『捌』 回溯演算法的基本思想及其在軟體開發中的應用

回溯演算法其實就是簡單的枚舉，只不過是加猜虧了一點技巧者笑。回溯演算法一般是已經完成的都是合法的，後續的操作不需要考慮先前已經完成的。短時間內通過文字也說不太明白，建議從一些題目去體會，八皇後、全排列。並綜合遞歸去理解這樣的話應該會有比較深刻的理解。
至於在軟體開發中的應用，演算法思想可以用在任首兆含何方面，最近甚至比較流行，將一些演算法用到硬體中，演算法提供的是一種思想，認真體會就會發現它會應用在任何方面。
希望能幫助到你。

『玖』 回溯演算法的基本思想

回溯演算法也叫試探法，它是慎枯一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。

問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。