旅行售貨員問題的回溯演算法

『壹』 9.2 回溯演算法的例子

在4 * 4的方格棋盤上放置4個皇後棋子，使得沒有兩個皇後在同一行、同一列，也不在同一條45度的斜線上， 問有多少種布局?
回溯演算法的解一般是向量，而這個題也不例外，設4維向量的<x1,x2,x3,x4>，Xi中i表示第幾個皇後，Xi表示在棋盤第i行的位置，比如其中一個解是<2,4,1,3>，如下圖

1.四皇後問題中，葉節點就是一個解。
2.四皇後每一個節點的子樹代表著下一個皇後可以放的列數，因為都是n，所以子樹都是n叉樹，故四皇後是一顆 n叉樹
3.四皇後的解至少有兩個，因為棋盤可以沿著中心線翻折

有n種物品，每種物品只有1個。第i種物品價值為vi，重量為wi，i=1，2，3...n. 問如何選擇放入背包的物品，使得總重量不超過B，而價值達到最大?
同樣，此問題的解可用一個向量來表示，該向量就代表了所有的物品，如果對應物品為1，則表示裝入背包，反之，沒有被裝入。
因此，回溯的每層可以表示為對應的物品，分支左右可以表示取或者不取（向量中表示為1或0）
總而言之，每一個節點也就是物品只有0和1兩種狀態，因此該樹一棵二叉樹，或者為 子集樹

1.選擇第一個物品，目前總重量為8，總價值為12。
2.再選擇第二個物品，總重量為14 > 13，觸發回溯。
3.不選擇第二個物品，選擇第三個商品，總重量是12，總價值為21。
4.再選擇第四個物品，總重量為15 > 13，觸發回溯。
5.不選擇第四個物品，總重量為12，總價值為21，與目前最優解價值進行比較，如果最優解價值大於21則替換目前的最優解向量和最優解價值。

1.背包問題只有在葉節點才能生成一個滿足條件的解，而之後將該解和最優解比較。
2.背包問題必須遍歷完所有的分支，才能夠獲得最終的解。
3.背包問題是一顆子集樹。

有n個城市，已知任兩個城市之間的距離， 求一條每個城市恰好經過一次的迴路，使得總長度最小 。
貨郎問題中主要的一點就是每一個點（除了第一個點）其他點必須經過且只能經過1次，這就很像數學中的排列。
因此，我們採用一個向量來表示貨郎問題的城市排列

1.貨郎問題是一顆分支不斷減少的排列數（和數學的排列類似）
2.貨郎問題也得遍歷完所有的情況，比較後得出最優解。

1.解都是用向量表示
2.搜索空間都是樹
3.搜索策略多種，有深度優先、寬度優先和跳躍式遍歷搜索樹。

『貳』 什麼是回溯演算法

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 1、定義一個解空間，它包含問題的解。 2、利用適於搜索的方法組織解空間。 3、利用深度優先法搜索解空間。 4、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。 1.跳棋問題： 33個方格頂點擺放著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規則是任一棋子可以沿水平或成垂直方向跳過與其相鄰的棋子，進入空著的頂點並吃掉被跳過的棋子。試設計一個演算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。 演算法實現提示 利用回溯演算法，每次找到一個可以走的棋子走動，並吃掉。若走到無子可走還是剩餘多顆，則回溯，走下一顆可以走動的棋子。當吃掉31顆時說明只剩一顆，程序結束。 2.中國象棋馬行線問題： 中國象棋半張棋盤如圖1(a)所示。馬自左下角往右上角跳。今規定只許往右跳，不許往左跳。比如 圖4（a）中所示為一種跳行路線，並將所經路線列印出來。列印格式為： 0，0->2,1->3,3->1,4->3,5->2,7->4,8… 演算法分析： 如圖1(b),馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為： 1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:從Ａ[1]出發，按移動規則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續搜索下 一個到達的頂點； S3:列印路徑。 演算法設計： procere try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {試遍4個方向} if 新坐標滿足條件 then begin 記錄新坐標; if 到達目的地 then print {統計方案，輸出結果} else try(i+1); {試探下一步} 退回到上一個坐標，即回溯; end; end;

『叄』 回溯演算法的介紹

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為：1、定義一個解空間，它包含問題的解。2、利用適於搜索的方法組織解空間。3、利用深度優先法搜索解空間。4、利用限界函數避免移動到不可能產生解的子空間。問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。

『肆』 什麼是旅行售貨員

一 問題的重述

售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發，經過每個城市一次，最後回到駐地的路線，使總的路程(或總旅費)最小。
路線是一個帶權圖。圖中各邊的費用（權）為正數。圖的一條周遊路線是包括V中的每個頂點在內的一條迴路。周遊路線的費用是這條路線上所有邊的費用之和。
旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結點到任一葉結點的路徑定義了圖的一條周遊路線。旅行售貨員問題要在圖G中找出費用最小的周遊路線。設有p個城市，假設每兩個城市之間都有直通通道，兩個城市之間的路程已知，一個售貨員要到每個城市推銷產品，然後返回原出發地，問這個售貨員應該如何選擇路線，能使每個城市都經過一次且僅一次，並且行程最短，這就是著名的旅行售貨員問題，也即貨郎擔問題。
用圖論的術語來描述旅行售貨員問題：即在一個正權完全圖中尋找一個具有最小權的哈密頓迴路，對於此問題，由於完全圖中必然存在哈密頓迴路，那麼目前可以用於求解的方法有枚舉法，分枝限界法，這兩種演算法可以求得此問題的精確解，但到目前為止，還沒有求解這一問題的有效演算法，我們可以利用分支限界法，回溯法求解此問題的近似解，以求得與最優解最為接近的解。

二問題的求解方法

1枚舉法
枚舉法就是一一列出問題的所有解，然後進行比較，取權值最小的解為最優解，這種方法雖然可以求取問題的最優解，但是我們知道旅行售貨員問題是對完全圖而言的，對有N個結點的完全圖，存在 個不同的哈密頓迴路，如果採用枚舉法求解，則要對上述數目的不同的哈密頓迴路一一進行運算且需要相互之間比較，當N取值較小時，此種求解方法沒有任何問題，但若N值較大時，計算量則以級數級別遞增，況且沒有有效的演算法，所以在計算機中也較難實現，故枚舉法在大多數的實際應用中是不可取的。

2回溯法
旅行售貨員問題的解空間是一棵排列樹。對於排列樹的回溯搜索與生成1，2，…，n的所有排列的遞歸演算法perm類似。開始時 ，相應的排列樹由 的所有排列構成。
在遞歸演算法backtrack中，當i=n時，當前的擴展結點是排列樹的葉結點的父結點。此時演算法檢測圖G是否存在一條從頂點 到頂點 的邊和從頂點 到頂點1的邊。如果這兩條邊都存在，則找到一條旅行售貨員迴路。此時演算法還需要判別這條迴路的費用是否優於當前已經找到的最優迴路的費用bestc。如果是，則必須更新當前的最優值bestc和當前的最優解bestx。
當 時，當前的擴展結點位於排列樹的第 層。圖G中存在從頂點 到達頂點 的邊時， 構成圖G中的一條路徑，且當 的費用小於當前最優值時演算法進入排列樹的第i層；否則，則剪去相應的子樹。演算法中用變數cc記錄當前路徑 的費用。
3 分枝限界法
分枝限界法的基本思想：
分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。問題的解空間樹時表示問題解空間的一棵有序樹，常見的由子集樹和排列樹。在搜索問題的解空間樹時，分支限界法與回溯法的主要不同在於它們對當前擴展結點所採用的擴展方式。在分支限界法中，每一個活結點只有一次機會成為擴展檢點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點總，導致不可行的解或者非最優解的兒子結點被舍棄，其餘兒子結點被加入活結點表中。此後從活結點表中取下一結點成為當前擴展結點，並重復上述擴展過程。這個過程一直持續到找到所需的解或活結點表空為止。
從活結點表中選擇下一擴展結點的不同方式將導致不同的分支限界法。最常見的有以下兩種方式。
（1）隊列式（FIFO）分支限界法
隊列式分支限界法將活結點表組織成一個隊列，並按照隊列的先進先出FIFO(first in first out )原則選取下一個結點為當前擴展結點。
（2） 優先隊列式分支限界法
優先隊列式的分支限界法將活結點表組織成一個優先隊列，並按照優先隊列中規定的結點優先順序選取優先順序最高的下一個結點成為當前擴展結點。
優先隊列中規定的結點優先順序常用一個與該結點相關的數值p表示。結點優先順序的高低與p值的大小相關。最大優先隊列規定p值較大的結點優先順序較高。在演算法是現實通常用最大堆來實現最大優先隊列，用最大堆的removeMax運算抽取堆中下一個結點成為當前擴展結點，體現最大效益優先的原則。類似的，最小優先隊列規定p值較小的結點優先順序較高。在演算法實現時通常用最小堆來實現最小優先隊列，用最小堆的removeMin運算抽取堆中下一個結點成為當前的擴展結點，體現最小費用優先的原則。用優先隊列式分支限界法解具體問題式，應該根據具體問題的特點確定選用最大優先隊列或者最小優先隊列表示解空間的活結點表。
考察4城市旅行售貨員的例子，如圖3-1所示。該問題的解空間樹一棵排列樹。解此問題的隊列式分支限界法以排列樹中結點B作為初始擴展結點。此時，活結點隊列為空。由於從圖G的頂點1到頂點2，3，4均有邊相連，所以結點B的兒子結點C，D，E均為可行結點，它們被加入到活結點隊列中，並捨去當前擴展結點B。當前活結點隊列中的隊首結點C成為下一個擴展結點。由於圖G的頂點2到頂點3和4有邊相連，故結點C的2個兒子結點F和G均為可行結點，從而被加入到活結點隊列中。接下來，結點D和結點E相繼成為擴展結點而被擴展。此時，活結點隊列中的結點為F，G，H，I，J，K。
結點F成為下一個擴展結點，其兒子結點L是一個葉結點。找到了一條旅行售貨員迴路，其費用為59。從下一個擴展結點G得到葉結點M，它相應的旅行售貨員迴路的費用為66。結點H依次成為擴展結點，得到結點N相應的旅行售貨員迴路，其費用為25。這已經時最好的一條迴路。下一個擴展結點時結點I。以結點I為根的子樹被剪去。最後，結點J，K被依次擴展，活結點隊列成為空，演算法終止。演算法搜索得到最優值為25，相應的最優解時從根結點到結點N的路徑（1，3，2，4，1）。
解同一問題的優先隊列式分支限界法用一極小堆來存儲活結點表，。其優先順序是結點的當前費用。演算法還是從排列樹的結點B和空優先隊列開始。結點B被擴展後，它的3個兒子結點C，D和E被一次插入堆中。此時，由於E是堆中具有最小當前費用的節點，所以處於堆頂位置，它自然成為下一個擴展結點。結點E被擴展後，其兒子結點J和K被插入當前堆中，它們的費用分別為14和24。此時堆頂元素是結點D，它成為下一個結點。如此，它的兩個兒子結點H和I被插入堆中。此時，堆中含有結點C，H，I，J，K。在這些結點中，結點H具有最小費用，從而它成為下一個擴展結點。擴展結點H後得到一條旅行售貨員迴路（1，3，2，4，1），相應的最小費用為25。接下來結點J成為擴展結點，由此得到另外一條旅行售貨員迴路（1，4，2，3，1），相應的費用為25。此後的擴展結點為K，I。由結點K得到的可行解費用高於當前最優解。結點I本身的費用已高於當前最優解。從而它們都不是最好的解。最後，優先隊列為空，演算法終止。

圖2-1
三 問題的求解結果與演算法分析

1問題的求解結果
(1)當結點數為N=4，其各個點之間的邊的權矩陣為 時，其最優解為：

圖3-1

即其解為(1,4,2,3,1)，最優解值為13。
(2)當結點數為N=5，其各個點之間的邊的權矩陣為 時，其最優解為：

圖3-2

則其解為（1,5,4,2,3,1），最優解值為18。
(3)當結點數為N=6，其各個點之間的邊的權矩陣為 時，其解為：

圖3-3

則其解為（1，2，3，4，5，6，1），最優解值為20。
(4)當其結點數為N=7時，其各個點之間的邊的權矩陣為 時，其解為：

圖3-4

則其解為（1，6，2，7，3，5，4，1）,最優解值為23。

(5)當其結點數為N=8時，其相應的各個點之間的邊的權矩陣為 時，
其解為：

圖3-5

則其最優解為（1，7，3，5，6，8，2，4，1），最優解值為19。

2演算法分析
(1)枚舉法
枚舉法是最差的一種演算法，即將所有可能的結果都排列一次，並比較解與當前最優解的大小，因此其時間復雜度很高，在實際應用中當結點數很多時不可取。
(2)回溯法
如果不考慮更新bestx所需的計算時間，則演算法backtrack需要 計算時間。由於演算法backtrack在最壞的情況下可能需要更新當前最優解 次，每次更新bestx需 計算時間，從而整個演算法的計算時間復雜性為 。
(3)分支限界法
由於是NP問題，其時間復雜度很高，當相對於回溯法而言，分支限界法剪掉了一些不必要的計算，效率有很大的提高，但是在最壞的情況下可能需要滿歷所有的結點。此時的時間復雜度也是很高的。

四心得體會

課程設計是對於知識的綜合運用，通過學習演算法分析也設計了解了一些關於實際問題的解決辦法。還有一點就是在學習過程中只停留在書本，只是知道書中某一演算法的幾個應用的例子。知識面很窄，考慮問題也只會從書本出發。想在例題中是如何解決問題的。其實我們在平常的學習中應該多研究一些實際問題，擴展視野。這樣就可以用不同的辦法解決同一問題，使用同一方法解決不同問題，也可以使復雜問題簡單化。