【文章內(nèi)容簡(jiǎn)介】 因此任何葉節(jié)點(diǎn)對(duì)應(yīng)的耗費(fèi)都不可能小于cc加上離開(kāi)各剩余頂點(diǎn)的出邊耗費(fèi)的最小值之和，因而可以把這個(gè)下限值作為節(jié)點(diǎn)所生成孩子的lcost值。如果新生成孩子的lcost 值小于目前找到的最優(yōu)旅行路徑的耗費(fèi)bestc，則把新生成的孩子加入活節(jié)點(diǎn)隊(duì)列(即最小堆)中。如果有向圖沒(méi)有旅行路徑，程序返回NoEdge，否則，返回最優(yōu)旅行路徑的耗費(fèi)，而最優(yōu)旅行路徑的頂點(diǎn)序列存儲(chǔ)在數(shù)組v 中。 回溯法思想簡(jiǎn)介 回朔法有“通用解題法”之稱，它采用深度優(yōu)先方式系統(tǒng)地搜索問(wèn)題的所有解，基本思路是:確定解空間的組織結(jié)構(gòu)之后，從根結(jié)點(diǎn)出發(fā)，即第一個(gè)活結(jié)點(diǎn)和第一個(gè)擴(kuò)展結(jié)點(diǎn)向縱深方向轉(zhuǎn)移至一個(gè)新結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向轉(zhuǎn)移，則當(dāng)前擴(kuò)展結(jié)點(diǎn)成為死結(jié)點(diǎn)。此時(shí)，回溯到最近的活結(jié)點(diǎn)處，并使其成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，回溯到以這種工作方式遞歸地在解空間中搜索，直到找到所求解空間中已經(jīng)無(wú)活結(jié)點(diǎn)為止。 回溯法求解旅行售貨員問(wèn)題旅行售貨員問(wèn)題的解空間是一棵排列樹(shù)。對(duì)于排列樹(shù)的回溯搜索與生成的所有排列的遞歸算法類似。設(shè)開(kāi)始時(shí)x=[ 1，2，… n ]，則相應(yīng)的排列樹(shù)由x[ 1: n ]的所有排列構(gòu)成。找旅行售貨員回路的回溯算法Backtrac是類Traveling的私有成員函數(shù)，TSP是Traveling的友員。TSP(v)返回旅行售貨員回路最小費(fèi)用。整型數(shù)組v返回相應(yīng)的回路。如果所給的圖不含旅行售貨員回路，則返回NoEdge。函數(shù)TSP所作的工作主要是為調(diào)用Backtrack所需要變量初始化。由TSP調(diào)用Backtrack(2)搜索整個(gè)解空間。在遞歸函數(shù)Backtrack中，當(dāng)i = n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹(shù)的葉結(jié)點(diǎn)的父結(jié)點(diǎn)。此時(shí)，算法檢測(cè)圖是否存在一條從頂點(diǎn)x[ n1 ]到頂點(diǎn)x[ n ]的邊和一條從頂點(diǎn)x[ n ]到頂點(diǎn)1的邊。如果這兩條邊都存在，則找一條旅行售貨員回路。此時(shí)，算法還需判斷這條回路的費(fèi)用是否優(yōu)于已找到的當(dāng)前最優(yōu)回路的費(fèi)用best。如果是，則必須更新當(dāng)前最優(yōu)值bestc和當(dāng)前最優(yōu)解bestx。當(dāng)時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹(shù)的第層。圖中存在從頂點(diǎn)x[ i1 ]到頂點(diǎn)x[ i ]的邊時(shí)，x[ 1: i ]構(gòu)成圖的一條路徑，且當(dāng)x[ 1: i ]的費(fèi)用小于當(dāng)前最優(yōu)值時(shí)，算法進(jìn)入排列樹(shù)的第層。否則將剪去相應(yīng)的子樹(shù)。算法中用變量cc記錄當(dāng)前路徑x[ 1:i ]的費(fèi)用。具體算法程序見(jiàn)附錄B。 回溯法的不足在沒(méi)有特殊條件約束的情況下,構(gòu)成問(wèn)題的是無(wú)向帶權(quán)圖，而周游路線是環(huán)形封閉路線；因此，可以明顯看出，回溯法構(gòu)成的解空間樹(shù)中存在著大量的重復(fù)解。個(gè)連通城市的問(wèn)題構(gòu)成的解空間樹(shù)中，其葉子結(jié)點(diǎn)的數(shù)目為，而經(jīng)過(guò)分析，重復(fù)的解路徑數(shù)目達(dá)到整個(gè)解空間路徑數(shù)目的一半。在不考慮約束函數(shù)時(shí)，整個(gè)搜索有一半是無(wú)效搜索，這大大降低了搜索的效率。 回溯算法的改進(jìn)對(duì)算法改進(jìn)的基本思想：在建立解空間樹(shù)后，使用新方法將已建立的解路徑反轉(zhuǎn)，找出其重復(fù)解，然后從解空間樹(shù)中將其刪除，直到刪除所有的重復(fù)解[4]。改進(jìn)算法的描述如下：建立解空間樹(shù)后，從第一條解路徑開(kāi)始，記錄當(dāng)前路徑,按照相反順序?qū)⑵浯嫒霐?shù)組recorder中，然后參照數(shù)組內(nèi)容,直接查找要?jiǎng)h除的枝,進(jìn)行子樹(shù)刪除；在刪除的過(guò)程中，先判斷其父節(jié)點(diǎn)有無(wú)其它子樹(shù)，如果有則刪除現(xiàn)有枝，如果沒(méi)有，繼續(xù)向上查找父節(jié)點(diǎn),直找到有其它子樹(shù)的父節(jié)點(diǎn)，刪除此枝。for ( i = 1。 i = leanfnum。 i++){ void recordpath [ i ] ( ){ int recordarr[ M ] = new array [ dep three( )]。for ( m=0。 m = pathedge[dep three()m]。search recorder[ ]。void deletesub( edge s){do{if super[ j](s){delete s。Leafnum 。break。}else j++。}while (j = dep three())}}}我們可以得到如下結(jié)論：經(jīng)過(guò)新解法的簡(jiǎn)化后，解空間樹(shù)變?yōu)樵瓉?lái)的二分之一，所需輔助空間復(fù)雜度較小，只有，而且實(shí)現(xiàn)簡(jiǎn)單,可以保證找到最優(yōu)解，這大量地減少了搜索路徑，并省掉了這些路徑的權(quán)值計(jì)算，節(jié)省了很多搜索時(shí)間，提高了搜索效率,有效的降低了算法的空間復(fù)雜度。 改進(jìn)后的回溯法的時(shí)間復(fù)雜度達(dá)到， 以目前的計(jì)算機(jī)的計(jì)算速度，只適合解決在20以下的問(wèn)題. 三種精確算法的比較 動(dòng)態(tài)規(guī)劃法和回溯法的比較 這本來(lái)就是兩個(gè)完全不同的領(lǐng)域，一個(gè)是算法領(lǐng)域，一個(gè)是數(shù)據(jù)結(jié)構(gòu)問(wèn)題。但兩者又交叉，又有區(qū)別。從本質(zhì)上講就是算法與數(shù)據(jù)結(jié)構(gòu)的本質(zhì)區(qū)別，回朔是一個(gè)具體的算法，動(dòng)態(tài)規(guī)劃是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)概念。動(dòng)態(tài)規(guī)劃講究的是狀態(tài)的轉(zhuǎn)化，以狀態(tài)為基準(zhǔn)，確定算法，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹(shù)中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。簡(jiǎn)單的說(shuō)就是:動(dòng)態(tài)規(guī)劃法是從小單元開(kāi)始積累計(jì)算結(jié)果。回朔講究過(guò)程的推進(jìn)與反還，隨數(shù)據(jù)的搜索，標(biāo)記，確定下一步的行進(jìn)方向，回朔是去搜索。如果想要搜索時(shí)，發(fā)現(xiàn)有很多重復(fù)計(jì)算，就應(yīng)該想到用動(dòng)態(tài)規(guī)劃了。動(dòng)態(tài)規(guī)劃和搜索都可以解決具有最優(yōu)子結(jié)構(gòu)的問(wèn)題，然而動(dòng)態(tài)規(guī)劃在解決子問(wèn)題的時(shí)候不重復(fù)計(jì)算已經(jīng)計(jì)算過(guò)的子問(wèn)題，對(duì)每個(gè)子問(wèn)題只計(jì)算一次。而簡(jiǎn)單的搜索則遞歸地計(jì)算所有遇到的的子問(wèn)題。搜索法的優(yōu)點(diǎn)是實(shí)現(xiàn)方便，缺點(diǎn)是在子問(wèn)題有大量的重復(fù)的時(shí)候要重復(fù)計(jì)算子問(wèn)題，效率較低。動(dòng)態(tài)規(guī)劃雖然效率高，但是階段的劃分和狀態(tài)的表示比較復(fù)雜，另外，搜索的時(shí)候只要保存單前的結(jié)點(diǎn)；而動(dòng)態(tài)規(guī)劃則至少要保存上一個(gè)階段的所有節(jié)點(diǎn)。另外，有一種折衷的辦法，就是備忘錄法，這是動(dòng)態(tài)規(guī)劃的一種變形。該方法的思想是：按照一般的搜索算法解決子問(wèn)題，但用一個(gè)表將所有解決過(guò)的子問(wèn)題保存起來(lái)，遇到一個(gè)子問(wèn)題的時(shí)候，先查表看是否是已經(jīng)解決，如果已解決過(guò)了就不用重復(fù)計(jì)算。自底向上的動(dòng)態(tài)規(guī)劃還有一個(gè)缺點(diǎn)，動(dòng)態(tài)規(guī)劃可能將與待解決問(wèn)題無(wú)關(guān)的部分也解決了一遍，這就造成了效率降低。而備忘錄法則可以避免這種問(wèn)題，備忘錄法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，且在子問(wèn)題空間中存在大量冗余子問(wèn)題的時(shí)候效率較高；但是要占用較大的內(nèi)存空間(需要開(kāi)一個(gè)很大的表來(lái)記錄已經(jīng)解決的子問(wèn)題)，而且如果用遞歸實(shí)現(xiàn)的話遞歸壓棧出棧也會(huì)影響效率；而自底向上的動(dòng)態(tài)規(guī)劃一般用for循環(huán)就可以了。 值得一提的是，用動(dòng)態(tài)規(guī)劃法來(lái)計(jì)算旅行售貨員的時(shí)間復(fù)雜度是指數(shù)型的。 分支限界法類似于回溯法，也是一種在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解的算法。但在一般情況下，分支限界與回溯法的求解目標(biāo)不同。回溯法的求解目標(biāo)是找出中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。 由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹(shù)上的搜索方式不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小消耗優(yōu)先的方式搜索解空間樹(shù)。分支限界法的搜索策略是，在擴(kuò)展結(jié)點(diǎn)處，先生成所有的兒子結(jié)點(diǎn)(分支)，然后再?gòu)漠?dāng)前的活動(dòng)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上的最優(yōu)解的分支推進(jìn)，以便盡快的找出一個(gè)最優(yōu)解。3 遺傳算法解決旅行售貨員問(wèn)題啟發(fā)式算法不能保證搜索問(wèn)題的全部解空間，所以也不能保證能夠搜到最優(yōu)解，甚至在某些實(shí)例上連解都得不到，但它們與精確算法相比卻具有運(yùn)算時(shí)間上的優(yōu)勢(shì)，即它們的運(yùn)算時(shí)間復(fù)雜度都只是多項(xiàng)式，并不會(huì)隨著輸入規(guī)模的擴(kuò)大而產(chǎn)生“組合爆炸”。這類算法采用的是啟發(fā)式策略來(lái)指導(dǎo)搜索，普遍比精確算法要快。對(duì)的啟發(fā)式算法的研究是本文的重點(diǎn)。但這種算法對(duì)數(shù)學(xué)及科學(xué)素養(yǎng)要求較高，在此我們不做過(guò)多討論，而簡(jiǎn)單的討論一下與生物學(xué)結(jié)合的遺傳算法。 遺傳算法介紹遺傳算法是一類模擬生物進(jìn)化過(guò)程與機(jī)制求解問(wèn)題的自適應(yīng)人工智能技術(shù)，是模擬自然界生物進(jìn)化過(guò)程的一類自組織、以概率論為基礎(chǔ)在解空間中進(jìn)行隨機(jī)化搜索，最終找到問(wèn)題的最優(yōu)解。遺傳算法的興起是在80年代末90年代初期，但是它的歷史可以追溯到06年代初期。早期的研究大多以對(duì)自然遺傳系統(tǒng)的計(jì)算機(jī)模擬為主。早期遺傳算法的研究特點(diǎn)是側(cè)重于對(duì)一些復(fù)雜的操作的研究。其中像自動(dòng)博弈、生物系統(tǒng)模擬、模式識(shí)別和函數(shù)優(yōu)化[5]等給人以深刻的印象，但總的說(shuō)來(lái)，這是一個(gè)無(wú)明確目標(biāo)的發(fā)展時(shí)期，缺乏帶有指導(dǎo)性的理論和計(jì)算工具的開(kāi)拓。這種現(xiàn)象直到70年代中期才得到改觀。1967年，首次提出了遺傳算法這一術(shù)語(yǔ)