旅行售貨員問題

1、一 問題的重述售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費)最小。 路線是一個帶權(quán)圖。圖中各邊的費用（權(quán)）為正數(shù)。圖的一條周游路線是包括V中的每個頂點在內(nèi)的一條回路。周游路線的費用是這條路線上所有邊的費用之和。 旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結(jié)點到任一葉結(jié)點的路徑定義了圖的一條周游路線。旅行售貨員問題要在圖G中找出費用最小的周游路線。設有p個城市，假設每兩個城市之間都有直通通道，兩個城市之間的路程已知，一個售貨員要到每個城市推銷產(chǎn)品，然后返回原出發(fā)地，問這個售貨員應該如何選擇路

2、線，能使每個城市都經(jīng)過一次且僅一次，并且行程最短，這就是著名的旅行售貨員問題，也即貨郎擔問題。用圖論的術(shù)語來描述旅行售貨員問題：即在一個正權(quán)完全圖中尋找一個具有最小權(quán)的哈密頓回路，對于此問題，由于完全圖中必然存在哈密頓回路，那么目前可以用于求解的方法有枚舉法，分枝限界法，這兩種算法可以求得此問題的精確解，但到目前為止，還沒有求解這一問題的有效算法，我們可以利用分支限界法，回溯法求解此問題的近似解，以求得與最優(yōu)解最為接近的解。二問題的求解方法1枚舉法 枚舉法就是一一列出問題的所有解，然后進行比較，取權(quán)值最小的解為最優(yōu)解，這種方法雖然可以求取問題的最優(yōu)解，但是我們知道旅行售貨員問題是對完全圖而言的

3、，對有N個結(jié)點的完全圖，存在個不同的哈密頓回路，如果采用枚舉法求解，則要對上述數(shù)目的不同的哈密頓回路一一進行運算且需要相互之間比較，當N取值較小時，此種求解方法沒有任何問題，但若N值較大時，計算量則以級數(shù)級別遞增，況且沒有有效的算法，所以在計算機中也較難實現(xiàn)，故枚舉法在大多數(shù)的實際應用中是不可取的。2回溯法旅行售貨員問題的解空間是一棵排列樹。對于排列樹的回溯搜索與生成1，2，n的所有排列的遞歸算法perm類似。開始時，相應的排列樹由的所有排列構(gòu)成。在遞歸算法backtrack中，當i=n時，當前的擴展結(jié)點是排列樹的葉結(jié)點的父結(jié)點。此時算法檢測圖G是否存在一條從頂點到頂點的邊和從頂點到頂點1的邊

4、。如果這兩條邊都存在，則找到一條旅行售貨員回路。此時算法還需要判別這條回路的費用是否優(yōu)于當前已經(jīng)找到的最優(yōu)回路的費用bestc。如果是，則必須更新當前的最優(yōu)值bestc和當前的最優(yōu)解bestx。 當時，當前的擴展結(jié)點位于排列樹的第層。圖G中存在從頂點 到達頂點的邊時，構(gòu)成圖G中的一條路徑，且當?shù)馁M用小于當前最優(yōu)值時算法進入排列樹的第i層；否則，則剪去相應的子樹。算法中用變量cc記錄當前路徑的費用。3 分枝限界法分枝限界法的基本思想：分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹時表示問題解空間的一棵有序樹，常見的由子集樹和排列樹。在搜索問題的解空間樹

5、時，分支限界法與回溯法的主要不同在于它們對當前擴展結(jié)點所采用的擴展方式。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展檢點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點總，導致不可行的解或者非最優(yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表空為止。從活結(jié)點表中選擇下一擴展結(jié)點的不同方式將導致不同的分支限界法。最常見的有以下兩種方式。（1）隊列式（FIFO）分支限界法 隊列式分支限界法將活結(jié)點表組織成一個隊列，并按照隊列的先進先出FIFO(first in fir

6、st out )原則選取下一個結(jié)點為當前擴展結(jié)點。（2） 優(yōu)先隊列式分支限界法 優(yōu)先隊列式的分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，并按照優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p表示。結(jié)點優(yōu)先級的高低與p值的大小相關(guān)。最大優(yōu)先隊列規(guī)定p值較大的結(jié)點優(yōu)先級較高。在算法是現(xiàn)實通常用最大堆來實現(xiàn)最大優(yōu)先隊列，用最大堆的removeMax運算抽取堆中下一個結(jié)點成為當前擴展結(jié)點，體現(xiàn)最大效益優(yōu)先的原則。類似的，最小優(yōu)先隊列規(guī)定p值較小的結(jié)點優(yōu)先級較高。在算法實現(xiàn)時通常用最小堆來實現(xiàn)最小優(yōu)先隊列，用最小堆的removeMi

7、n運算抽取堆中下一個結(jié)點成為當前的擴展結(jié)點，體現(xiàn)最小費用優(yōu)先的原則。用優(yōu)先隊列式分支限界法解具體問題式，應該根據(jù)具體問題的特點確定選用最大優(yōu)先隊列或者最小優(yōu)先隊列表示解空間的活結(jié)點表。考察4城市旅行售貨員的例子，如圖3-1所示。該問題的解空間樹一棵排列樹。解此問題的隊列式分支限界法以排列樹中結(jié)點B作為初始擴展結(jié)點。此時，活結(jié)點隊列為空。由于從圖G的頂點1到頂點2，3，4均有邊相連，所以結(jié)點B的兒子結(jié)點C，D，E均為可行結(jié)點，它們被加入到活結(jié)點隊列中，并舍去當前擴展結(jié)點B。當前活結(jié)點隊列中的隊首結(jié)點C成為下一個擴展結(jié)點。由于圖G的頂點2到頂點3和4有邊相連，故結(jié)點C的2個兒子結(jié)點F和G均為可行結(jié)

8、點，從而被加入到活結(jié)點隊列中。接下來，結(jié)點D和結(jié)點E相繼成為擴展結(jié)點而被擴展。此時，活結(jié)點隊列中的結(jié)點為F，G，H，I，J，K。結(jié)點F成為下一個擴展結(jié)點，其兒子結(jié)點L是一個葉結(jié)點。找到了一條旅行售貨員回路，其費用為59。從下一個擴展結(jié)點G得到葉結(jié)點M，它相應的旅行售貨員回路的費用為66。結(jié)點H依次成為擴展結(jié)點，得到結(jié)點N相應的旅行售貨員回路，其費用為25。這已經(jīng)時最好的一條回路。下一個擴展結(jié)點時結(jié)點I。以結(jié)點I為根的子樹被剪去。最后，結(jié)點J，K被依次擴展，活結(jié)點隊列成為空，算法終止。算法搜索得到最優(yōu)值為25，相應的最優(yōu)解時從根結(jié)點到結(jié)點N的路徑（1，3，2，4，1）。解同一問題的優(yōu)先隊列式分支

9、限界法用一極小堆來存儲活結(jié)點表，。其優(yōu)先級是結(jié)點的當前費用。算法還是從排列樹的結(jié)點B和空優(yōu)先隊列開始。結(jié)點B被擴展后，它的3個兒子結(jié)點C，D和E被一次插入堆中。此時，由于E是堆中具有最小當前費用的節(jié)點，所以處于堆頂位置，它自然成為下一個擴展結(jié)點。結(jié)點E被擴展后，其兒子結(jié)點J和K被插入當前堆中，它們的費用分別為14和24。此時堆頂元素是結(jié)點D，它成為下一個結(jié)點。如此，它的兩個兒子結(jié)點H和I被插入堆中。此時，堆中含有結(jié)點C，H，I，J，K。在這些結(jié)點中，結(jié)點H具有最小費用，從而它成為下一個擴展結(jié)點。擴展結(jié)點H后得到一條旅行售貨員回路（1，3，2，4，1），相應的最小費用為25。接下來結(jié)點J成為擴展

10、結(jié)點，由此得到另外一條旅行售貨員回路（1，4，2，3，1），相應的費用為25。此后的擴展結(jié)點為K，I。由結(jié)點K得到的可行解費用高于當前最優(yōu)解。結(jié)點I本身的費用已高于當前最優(yōu)解。從而它們都不是最好的解。最后，優(yōu)先隊列為空，算法終止。 ABCDEFGHIJKLMNOPQ圖2-1三 問題的求解結(jié)果與算法分析1問題的求解結(jié)果(1)當結(jié)點數(shù)為N=4，其各個點之間的邊的權(quán)矩陣為時，其最優(yōu)解為：圖3-1即其解為(1,4,2,3,1)，最優(yōu)解值為13。(2)當結(jié)點數(shù)為N=5，其各個點之間的邊的權(quán)矩陣為時，其最優(yōu)解為：圖3-2則其解為（1,5,4,2,3,1），最優(yōu)解值為18。(3)當結(jié)點數(shù)為N=6，其各個點之

11、間的邊的權(quán)矩陣為時，其解為：圖3-3則其解為（1，2，3，4，5，6，1），最優(yōu)解值為20。(4)當其結(jié)點數(shù)為N=7時，其各個點之間的邊的權(quán)矩陣為 時，其解為：圖3-4則其解為（1，6，2，7，3，5，4，1）,最優(yōu)解值為23。(5)當其結(jié)點數(shù)為N=8時，其相應的各個點之間的邊的權(quán)矩陣為時，其解為：圖3-5 則其最優(yōu)解為（1，7，3，5，6，8，2，4，1），最優(yōu)解值為19。2算法分析(1)枚舉法 枚舉法是最差的一種算法，即將所有可能的結(jié)果都排列一次，并比較解與當前最優(yōu)解的大小，因此其時間復雜度很高，在實際應用中當結(jié)點數(shù)很多時不可取。(2)回溯法 如果不考慮更新bestx所需的計算時間，則算法backtrack需要計算時間。由于算法backtrack在最壞的情況下可能需要更新當前最優(yōu)解次，每次更新bestx需計算時間，從而整個算法的計算時間復雜性為。(3)分支限界法 由于是NP問題，其時間復雜度很高，當相對于回溯法而言，分支限界法剪掉了一些不必要的計算，效率有很大的提高，但是在最壞的情況下可能需要滿歷所有的結(jié)點。此時的時間復雜度也是很高的。四心得體會 課程