旅行售貨員問題PPT學習課件.ppt

1、旅行售貨員問題,計算復雜性理論介紹,問題的描述,售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā)，經過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費)最小。 旅行售貨員問題雖然易于被人理解，但其計算復雜度卻是問題的輸入規(guī)模的指數函數,是一個NP完全問題。,2,問題的描述,路線是一個帶權圖。圖中各邊的費用（權）為正數。圖的一條周游路線是包括V中的每個頂點在內的一條回路。周游路線的費用是這條路線上所有邊的費用之和。 用圖論的術語來描述旅行售貨員問題：即在一個正權完全圖中尋找一個具有最小權的哈密頓回路，對于此問題，由于完全圖中必然存在哈密頓回路， 目前可以

2、用于求解的方法有枚舉法，分枝限界法，這兩種算法可以求得此問題的精確解，但到目前為止，還沒有求解這一問題的有效算法，我們可以利用分支限界法，回溯法求解此問題的近似解，以求得與最優(yōu)解最為接近的解。,3,旅行售貨員問題,枚舉法,復雜度極高，可以求出精確解,通過對問題的排列樹的合理剪枝，大大縮減了問題需要求解的時間?？梢郧蟪鼍_解,基于三角不等式性質等，進一步抽象求解過程，可以求出近似解，復雜度為多項式級別,問題的精確解和近似解,分支限界法,NP問題近似算法,回溯法,通過對排列樹的剪枝，縮減問題需要的求解時間?？汕缶_解及近似解,4,共有6條周游路線： （1,2,4,3,1） 66 （1,2,3,4,

3、1） 59 （1,3,2,4,1） 25 （1,3,4,2,1） 66 （1,4,2,3,1） 25 （1,4,3,2,1） 59,設G=(V,E )是一個帶權圖。圖中各邊的權值為正數。圖的一條周游路線是包括V中的每個頂點在內的一條回路。 旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結點到任一葉結點的路徑定義了圖G的一條周游路線。 周游路線的費用是這條路線上所有邊的費用之和。 旅行售貨員問題要找出費用最小的周游路線。 實例：4個城市 n=4 葉節(jié)點個數(周游線路)=(n-1)!,枚舉法,66 59 25 66 25 59,5,從第一個城市到第二個城市有n-1種走法，從第二個城市到第三個城市

4、有n-2種走法因而共有(n-1)!種走法。 若考慮v1v2vnv1和v1 vn vn-1v2 v1是同一條回路，還共有(1/2)(n-1)!條不同的哈密頓回路。 為了比較權的大小，對每條哈密頓回路要做n-1次加法， 故加法的總數為(1/2)(n-1)(n-1)!。 時間復雜度O(n!) 例如當有40個城市時，(1/2)(n-1)(n-1)!的近似值為3.771047，假設一臺計算機每秒完成1011次（百億）次加法，將需要超過1.191029年才能完成所需的加法次數，顯然是不可能的。,算法效率,6,1、有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法

5、。2、回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數相當大的問題。 3、回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含（剪枝過程），則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 生成問題狀態(tài)的基本方法 擴展結點:一個正在產生兒子的結點活結點:一個自身已生成但其兒子還沒有全部生成的結點死結點:一個所有兒子已經產生的結點 深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產生了它的一個兒

6、子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子（如果存在）,回溯法,7,基本思想,一.解空間樹的動態(tài)搜索 回溯法從根結點出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。 初始時，根結點成為一個活結點，同時也稱為當前的擴展結點。 在當前擴展結點處，搜索向縱深方向移至一個新結點。這個新結點成為一個新的活結點，并成為當前的擴展結點。 如果在當前的擴展結點處不能再向深方向移動，則當前的擴展結點就成為一個死結點。此時，應往回移動回溯至最近的一個活結點處，并使這個活結點成為當前的擴展結點。 回溯法以這種工作方式遞歸地在解

7、空間中搜索，直至找到所要求的解或解空間中已無活結點時為止。,8,二.常用剪枝函數： 用約束函數在擴展結點處剪去不滿足約束的子樹； 用限界函數剪去得不到最優(yōu)解的子樹。 為了避免生成那些不可能產生最佳解的問題狀態(tài)，要不斷地利用限界函數(bounding function)來處死(剪枝)那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數的深度優(yōu)先生成法稱為回溯法。 回溯法 = 窮舉 +剪枝,9,解空間樹的動態(tài)搜索,將圖中n個頂點編號為1,2,n，以頂點1為起點，旅行回路描述為1,x1,x2,.,xn,1， 其中x1,x2,.,xn為頂點2,3,4,n的1個排列，因此解空間大小為(n

8、-1)!,A,B,D,H,N,10,剪枝,11,算法描述,旅行售貨員問題的解空間是一棵排列樹。 開始時，x=1,2,n相應的排列樹由x=1:n的所有排列構成。 在遞歸算法Backtrack中， 1.當i=n時，當前擴展節(jié)點是排列樹的葉節(jié)點的父節(jié)點。 檢測圖G是否存在一條從頂點xn-1到頂點xn的邊和一條從頂點xn到頂點1的邊。 如果這兩條邊都存在，則找到一條旅行員售貨回路。 此時，算法還需要判斷這條回路的費用是否優(yōu)于已找到的當前最優(yōu)回流的費用bestc。 如果是，則必須更新當前最優(yōu)值bestc和當前最優(yōu)解bestx。 2. 當in時，當前擴展節(jié)點位于排列樹的第i-1層。 圖G中存在從頂點xi-

9、1到頂點xi的邊時，x1:i構成圖G的一條路徑，且當x1:i的費用小于當前最優(yōu)值時算法進入樹的第i層， 否則將剪去相應的子樹。,12,13,private static void backtrack(int i) if(i=n) /當前擴展結點是排列樹的葉結點的父結點 if(axn-1xnmax_value /得到最優(yōu)值 else /in,當前擴展結點位于第i-1層,cc:記錄當前路徑x1:i的費用 a:圖G的鄰接矩陣,14,for(int j=i;j=n;j+) /搜索第i層的所有子樹 /是否可進入xj子樹？ if(axi-1xj max_value /還原xi,xj的值 ,Backtrac

10、k最壞情況下時間復雜度O(n-1)!) 更新bestx時間復雜度 O(n) 時間復雜度很高O(n!),算法效率,15,1.分支限界法基本思想 分支限界法常以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。 在分支限界法中，每一個活結點只有一次機會成為擴展結點。 活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。 此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。 2. 常見的兩種分支限界法 從活結點表中選擇下一擴展結

11、點的不同方式導致不同的 （1）隊列式(FIFO)分支限界法 將活結點表組織成一個隊列，并按隊列的先進先出原則選取下一個結點為當前擴展結點 （2）優(yōu)先隊列式分支限界法 將活結點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結點 優(yōu)先級選取優(yōu)先級最高的下一個結點為當前擴展結點 最大優(yōu)先隊列：使用最大堆，體現最大效益優(yōu)先 最小優(yōu)先隊列：使用最小堆，體現最小費用優(yōu)先,分支限界法,16,1.求解目標,回溯法：,找出解空間中滿足約束條件的所有解,分支限界法,找出滿足約束條件的一個解,在滿足約束條件的解中找出使某一 目標函數值極大或極小的解,分支限界法和回溯法一樣都是在解空間上搜索問題解的算法,2.搜索方式,深

12、度優(yōu)先 DFS,回溯法：,分支限界法,廣度優(yōu)先BFS或最小損耗優(yōu)先,17,C =,30,11,4,26,6,25,14,59,25,24,算法描述： 準備工作：建立小根堆，用于存儲活動節(jié)點。 計算每個頂點的最小出邊，若存在某個頂點沒有出邊，則算法終止。 初始化樹根（頂點1）為第一個活動節(jié)點。 判斷節(jié)點是否是葉結點的父節(jié)點：是的話，則檢查是否一定有最低耗費，若是加入小根堆； 不是葉結點的父節(jié)點，則生成子節(jié)點，并判斷子節(jié)點是否有可能取得最低耗費，若可能則加入小根堆； 取出下一個節(jié)點作為活動節(jié)點，若該節(jié)點已經是葉結點，返回當前最低耗費值，即為最優(yōu)旅行。若不是葉結點則循環(huán)2、3步。,鄰接矩陣,18,優(yōu)

13、先隊列式分支限界法用極小堆存儲活結點表,B被擴展后，它的三個兒子結點C,D,E被依次插入堆中,E被擴展后，它的兒子結點J,K被依次插入當前堆中,D被擴展后，它的兒子結點H,I被依次插入當前堆中,初始擴展結點為B，優(yōu)先隊列為空。,19,； BE,D,C； ED, J,K, C； DH,J,K,I,C； HJ,K,I,C；JK,I,C；KI,C；IC；C.,K被擴展后，得到可行解費用為59，高于當前最優(yōu)解25,20,NP問題近似算法,從實際應用中抽象出的旅行售貨員問題具有一些特殊性質。比如，費用函數c往往具有三角不等式性質，即對任意3個頂點u,v,w有c(u,v)1，不存在性能比為的解旅行售貨員問

14、題的多項式時間近似算法。,21,NP問題近似算法,void approxTSP(Gragh g) (1)選擇g的任意頂點r； (2)用Prim算法找出帶權圖g的一顆以r為根的最小生成樹T； (3)前序遍歷樹T得到頂點表L； (4)將r加入到表L的末尾，按表L中頂點次序組成回路H，作為計算結果返回； ,22,NP問題近似算法,(a)圖G頂點集abcdefgh) (b)找到的最小生成樹(MST) T完全遍歷DFS abcbh ba def egeda (c) 對T作前序遍歷的順序 abch def g a (d) L產生的哈密頓回路H取捷徑生成解 (e) G的一個最小費用旅行售貨員回路,23,NP

15、問題近似算法,其中，a表示所給的圖G頂點集；b表示由算法找到的一顆最小生成樹T；c表示對樹T所做的前序遍歷訪問各頂點的次序；d表示由T的前序遍歷頂點表示L產生的哈密頓回路H；e表示圖G的一個最小費用旅行售貨員回路。 在b時，對T的完全遍歷W=abcbhbadefegeda，還不是一個旅行售貨員回路，它訪問了圖G中某些頂點多次。由于費用函數滿足三角不等式，可以在W的基礎上，從中刪去已訪問過的頂點，而不會增加旅行費用。若在W中刪去頂點u和w間的一個頂點v，就用邊(u,w)代替原來從u到w的一條路。反復用這個辦法刪去W中多次訪問的頂點，可得到圖G的一條旅行售貨員回路H=abchdefga。,24,總

16、結,(1)枚舉法 枚舉法是最差的一種算法，即將所有可能的結果都排列一次，并比較解與當前最優(yōu)解的大小，因此其時間復雜度很高O(n!) ，在實際應用中當結點數很多時不可取。 (2)回溯法 如果不考慮更新bestx所需的計算時間，則算法backtrack需要O(n-1)!)計算時間。 由于算法backtrack在最壞的情況下可能需要更新當前最優(yōu)解O(n-1)!)次，每次更新bestx需O(n)計算時間，從而整個算法的計算時間復雜性為O(n!) 。,25,(3)分支限界法 由于是NP問題，其時間復雜度很高，當相對于回溯法而言，分支限界法剪掉了一些不必要的計算，效率有很大的提高，但是在最壞的情況下可能需要滿歷所有的結點。此時的時間復雜度也是很高的。 O(2 n ) 搜索狀態(tài)空間O(2 ) 指數時間 對每個結點的計算O(n ) (4)NP問題近似算法 作為NP完全問題，相對于其他算法，基于三角不等式性質的旅行售貨員近似算法，效率有很大的提高。其不存在最壞的情況，算法穩(wěn)定性較