1. 五大基本演算法——回溯法
回溯法是一種選優搜索法（試探法）。
基本思想：將問題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-皇後問題
具體問題可網路詳細內容。
2. 常見演算法思想6：回溯法
回溯法也叫試探法，試探的處事方式比較委婉，它先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一進行枚舉和檢驗。當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探演算法中，放棄當前候選解，並繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。
（1）針對所給問題，定義問題的解空間。
（2）確定易於搜索的解空間結構。
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。
回溯法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，馬上會自覺地退回一步重新選擇，然後繼續向前試探，如此這般反復進行，直至得到解或證明無解時才死心。
下面是回溯的3個要素。
（1）解空間：表示要解決問題的范圍，不知道範圍的搜索是不可能找到結果的。
（2）約束條件：包括隱性的和顯性的，題目中的要求以及題目描述隱含的約束條件，是搜索有解的保證。
（3）狀態樹：是構造深搜過程的依據，整個搜索以此樹展開。
下面是影響演算法效率的因素：
回溯法搜索解空間時，通常採用兩種策略避免無效搜索，提高回溯的搜索效率:
為縮小規模，我們用顯示的國際象棋8*8的八皇後來分析。按照國際象棋的規則，皇後的攻擊方式是橫，豎和斜向。
皇後可以攻擊到同一列所有其它棋子，因此可推導出每1列只能存在1個皇後，即每個皇後分別占據一列。棋盤一共8列，剛好放置8個皇後。
為了擺放出滿足條件的8個皇後的布局，可以按如下方式逐步操作：
把規模放大到N行N列也一樣，下面用回溯法解決N皇後問題：
執行：
3. 用遞歸回溯法設計旅行售貨員問題的演算法
一、回溯法：
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
二、演算法框架：
1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
2、回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；
3、遞歸回溯：由於回溯法是對解空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法如下：
procere try(i:integer);
var
begin
if i>n then 輸出結果
else for j:=下界 to 上界 do
begin
x[i]:=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，回溯到(xi,x2,……x(i-1))，添加那些未考察過的x1屬於s1，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。