旅行售貨員問題.ppt

旅行售貨員問題,計算復(fù)雜性理論介紹,問題的描述,售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費(fèi))。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費(fèi))最小。旅行售貨員問題雖然易于被人理解，但其計算復(fù)雜度卻是問題的輸入規(guī)模的指數(shù)函數(shù),是一個NP完全問題。,問題的描述,路線是一個帶權(quán)圖。圖中各邊的費(fèi)用（權(quán)）為正數(shù)。圖的一條周游路線是包括V中的每個頂點(diǎn)在內(nèi)的一條回路。周游路線的費(fèi)用是這條路線上所有邊的費(fèi)用之和。用圖論的術(shù)語來描述旅行售貨員問題：即在一個正權(quán)完全圖中尋找一個具有最小權(quán)的哈密頓回路，對于此問題，由于完全圖中必然存在哈密頓回路，目前可以用于求解的方法有枚舉法，分枝限界法，這兩種算法可以求得此問題的精確解，但到目前為止，還沒有求解這一問題的有效算法，我們可以利用分支限界法，回溯法求解此問題的近似解，以求得與最優(yōu)解最為接近的解。,旅行售貨員問題,枚舉法,復(fù)雜度極高，可以求出精確解,通過對問題的排列樹的合理剪枝，大大縮減了問題需要求解的時間?？梢郧蟪鼍_解,基于三角不等式性質(zhì)等，進(jìn)一步抽象求解過程，可以求出近似解，復(fù)雜度為多項式級別,問題的精確解和近似解,分支限界法,NP問題近似算法,回溯法,通過對排列樹的剪枝，縮減問題需要的求解時間。可求精確解及近似解,共有6條周游路線：（1,2,4,3,1）66（1,2,3,4,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,設(shè)G=(V,E)是一個帶權(quán)圖。圖中各邊的權(quán)值為正數(shù)。圖的一條周游路線是包括V中的每個頂點(diǎn)在內(nèi)的一條回路。旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑定義了圖G的一條周游路線。周游路線的費(fèi)用是這條路線上所有邊的費(fèi)用之和。旅行售貨員問題要找出費(fèi)用最小的周游路線。實(shí)例：4個城市n=4葉節(jié)點(diǎn)個數(shù)(周游線路)=(n-1)!,枚舉法,665925662559,從第一個城市到第二個城市有n-1種走法，從第二個城市到第三個城市有n-2種走法因而共有(n-1)!種走法。若考慮v1v2vnv1和v1vnvn-1v2v1是同一條回路，還共有(1/2)(n-1)!條不同的哈密頓回路。為了比較權(quán)的大小，對每條哈密頓回路要做n-1次加法，故加法的總數(shù)為(1/2)(n-1)(n-1)!。時間復(fù)雜度O(n!)例如當(dāng)有40個城市時，(1/2)(n-1)(n-1)!的近似值為3.771047，假設(shè)一臺計算機(jī)每秒完成1011次（百億）次加法，將需要超過1.191029年才能完成所需的加法次數(shù)，顯然是不可能的。,算法效率,1、有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。2、回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。3、回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含（剪枝過程），則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。生成問題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn):一個正在產(chǎn)生兒子的結(jié)點(diǎn)活結(jié)點(diǎn):一個自身已生成但其兒子還沒有全部生成的結(jié)點(diǎn)死結(jié)點(diǎn):一個所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個兒子（如果存在）,回溯法,基本思想,一.解空間樹的動態(tài)搜索回溯法從根結(jié)點(diǎn)出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。初始時，根結(jié)點(diǎn)成為一個活結(jié)點(diǎn)，同時也稱為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)成為一個新的活結(jié)點(diǎn)，并成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向深方向移動，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)就成為一個死結(jié)點(diǎn)。此時，應(yīng)往回移動回溯至最近的一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘ㄒ赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點(diǎn)時為止。,二.常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死(剪枝)那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。回溯法=窮舉+剪枝,解空間樹的動態(tài)搜索,將圖中n個頂點(diǎn)編號為1,2,n，以頂點(diǎn)1為起點(diǎn)，旅行回路描述為1,x1,x2,.,xn,1，其中x1,x2,.,xn為頂點(diǎn)2,3,4,n的1個排列，因此解空間大小為(n-1)!,A,B,D,H,N,剪枝,算法描述,旅行售貨員問題的解空間是一棵排列樹。開始時，x=1,2,n相應(yīng)的排列樹由x=1:n的所有排列構(gòu)成。在遞歸算法Backtrack中，1.當(dāng)i=n時，當(dāng)前擴(kuò)展節(jié)點(diǎn)是排列樹的葉節(jié)點(diǎn)的父節(jié)點(diǎn)。檢測圖G是否存在一條從頂點(diǎn)xn-1到頂點(diǎn)xn的邊和一條從頂點(diǎn)xn到頂點(diǎn)1的邊。如果這兩條邊都存在，則找到一條旅行員售貨回路。此時，算法還需要判斷這條回路的費(fèi)用是否優(yōu)于已找到的當(dāng)前最優(yōu)回流的費(fèi)用bestc。如果是，則必須更新當(dāng)前最優(yōu)值bestc和當(dāng)前最優(yōu)解bestx。2.當(dāng)in時，當(dāng)前擴(kuò)展節(jié)點(diǎn)位于排列樹的第i-1層。圖G中存在從頂點(diǎn)xi-1到頂點(diǎn)xi的邊時，x1:i構(gòu)成圖G的一條路徑，且當(dāng)x1:i的費(fèi)用小于當(dāng)前最優(yōu)值時算法進(jìn)入樹的第i層，否則將剪去相應(yīng)的子樹。,13,privatestaticvoidbacktrack(inti)if(i=n)/當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹的葉結(jié)點(diǎn)的父結(jié)點(diǎn)if(axn-1xnmax_value/得到最優(yōu)值else/in,當(dāng)前擴(kuò)展結(jié)點(diǎn)位于第i-1層,cc:記錄當(dāng)前路徑x1:i的費(fèi)用a:圖G的鄰接矩陣,14,for(intj=i;j=n;j+)/搜索第i層的所有子樹/是否可進(jìn)入xj子樹？if(axi-1xjmax_value/還原xi,xj的值,Backtrack最壞情況下時間復(fù)雜度O(n-1)!)更新bestx時間復(fù)雜度O(n)時間復(fù)雜度很高O(n!),算法效率,1.分支限界法基本思想分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時為止。2.常見的兩種分支限界法從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的（1）隊列式(FIFO)分支限界法將活結(jié)點(diǎn)表組織成一個隊列，并按隊列的先進(jìn)先出原則選取下一個結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)（2）優(yōu)先隊列式分支限界法將活結(jié)點(diǎn)表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點(diǎn)優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)最大優(yōu)先隊列：使用最大堆，體現(xiàn)最大效益優(yōu)先最小優(yōu)先隊列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先,分支限界法,1.求解目標(biāo),回溯法：,找出解空間中滿足約束條件的所有解,分支限界法,找出滿足約束條件的一個解,在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值極大或極小的解,分支限界法和回溯法一樣都是在解空間上搜索問題解的算法,2.搜索方式,深度優(yōu)先DFS,回溯法：,分支限界法,廣度優(yōu)先BFS或最小損耗優(yōu)先,C=,30,11,4,26,6,25,14,59,25,24,算法描述：準(zhǔn)備工作：建立小根堆，用于存儲活動節(jié)點(diǎn)。計算每個頂點(diǎn)的最小出邊，若存在某個頂點(diǎn)沒有出邊，則算法終止。初始化樹根（頂點(diǎn)1）為第一個活動節(jié)點(diǎn)。判斷節(jié)點(diǎn)是否是葉結(jié)點(diǎn)的父節(jié)點(diǎn)：是的話，則檢查是否一定有最低耗費(fèi)，若是加入小根堆；不是葉結(jié)點(diǎn)的父節(jié)點(diǎn)，則生成子節(jié)點(diǎn)，并判斷子節(jié)點(diǎn)是否有可能取得最低耗費(fèi)，若可能則加入小根堆；取出下一個節(jié)點(diǎn)作為活動節(jié)點(diǎn)，若該節(jié)點(diǎn)已經(jīng)是葉結(jié)點(diǎn)，返回當(dāng)前最低耗費(fèi)值，即為最優(yōu)旅行。若不是葉結(jié)點(diǎn)則循環(huán)2、3步。,鄰接矩陣,優(yōu)先隊列式分支限界法用極小堆存儲活結(jié)點(diǎn)表,B被擴(kuò)展后，它的三個兒子結(jié)點(diǎn)C,D,E被依次插入堆中,E被擴(kuò)展后，它的兒子結(jié)點(diǎn)J,K被依次插入當(dāng)前堆中,D被擴(kuò)展后，它的兒子結(jié)點(diǎn)H,I被依次插入當(dāng)前堆中,初始擴(kuò)展結(jié)點(diǎn)為B，優(yōu)先隊列為空。,；BE,D,C；ED,J,K,C；DH,J,K,I,C；HJ,K,I,C；JK,I,C；KI,C；IC；C.,K被擴(kuò)展后，得到可行解費(fèi)用為59，高于當(dāng)前最優(yōu)解25,NP問題近似算法,從實(shí)際應(yīng)用中抽象出的旅行售貨員問題具有一些特殊性質(zhì)。比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)，即對任意3個頂點(diǎn)u,v,w有c(u,v)1，不存在性能比為的解旅行售貨員問題的多項式時間近似算法。,NP問題近似算法,voidapproxTSP(Graghg)(1)選擇g的任意頂點(diǎn)r；(2)用Prim算法找出帶權(quán)圖g的一顆以r為根的最小生成樹T；(3)前序遍歷樹T得到頂點(diǎn)表L；(4)將r加入到表L的末尾，按表L中頂點(diǎn)次序組成回路H，作為計算結(jié)果返回；,NP問題近似算法,(a)圖G頂點(diǎn)集abcdefgh)(b)找到的最小生成樹(MST)T完全遍歷DFSabcbhbadefegeda(c)對T作前序遍歷的順序abchdefga(d)L產(chǎn)生的哈密頓回路H取捷徑生成解(e)G的一個最小費(fèi)用旅行售貨員回路,NP問題近似算法,其中，a表示所給的圖G頂點(diǎn)集；b表示由算法找到的一顆最小生成樹T；c表示對樹T所做的前序遍歷訪問各頂點(diǎn)的次序；d表示由T的前序遍歷頂點(diǎn)表示L產(chǎn)生的哈密頓回路H；e表示圖G的一個最小費(fèi)用旅行售貨員回路。在b時，對T的完全遍歷W=abcbhbadefegeda，還不是一個旅行售貨員回路，它訪問了圖G中某些頂點(diǎn)多次。由于費(fèi)用函數(shù)滿足三角不等式，可以在W的基礎(chǔ)上，從中刪去已訪問過的頂點(diǎn)，而不會增加旅行費(fèi)用。若在W中刪去頂點(diǎn)u和w間的一個頂點(diǎn)v，就用邊(u,w)代替原來從u到w的一條路。反復(fù)用這個辦法刪去W中多次訪問的頂點(diǎn)，可得到圖G的一條旅行售貨員回路H=abchdefga。,總結(jié),(1)枚舉法枚舉法是最差的一種算法，即將所有可能的結(jié)果都排列一次，并比較解與當(dāng)前最優(yōu)解的大小，因此其時間復(fù)雜度很高O(n!)，在實(shí)際應(yīng)用中當(dāng)結(jié)點(diǎn)數(shù)很多時不可取。(2)回溯法如果不考慮更新bestx所需的計算時間，則算法backtrack需要O(n-1)!)計算時間。由于算法backtrack在最壞的情況下可能需要更新當(dāng)前最優(yōu)解O(n-1)!)次，每次更新bestx需O(n)計算時間，從而整個算法的計算時間復(fù)雜性為O(n!)。,(3)分支限界法由于是NP問題，其時間復(fù)雜度很高，當(dāng)相對于回溯法而言，分支限界法剪掉了一些不必要的計算，效率有很大的提高，但是在最壞的情況下可能需要滿歷所有的結(jié)點(diǎn)。此時的時間復(fù)雜度也是很高的。O(2n)搜索狀態(tài)空間O(2)指數(shù)時間對每個結(jié)點(diǎn)的計算O(n)(4)NP問題近似算法作為NP完全問題，相對于其他算法，基于三角不等式性質(zhì)的旅行售貨員近似算法，效率有很大的提高。其不存在最壞的情況，算法穩(wěn)定性較好，且性價比在常數(shù)級別。在采用樸素Prim算法時