旅行售貨員問(wèn)題.ppt

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