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