旅行售貨員問題

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

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

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

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

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

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

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

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

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

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

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