【正文】 最短。此時，數(shù)學模型是在加權(quán)圖上求一個生成回路，使。任意兩個城市之間來回均存在路徑或至少有兩個城市之間僅存在單行路徑；這種類型可以歸結(jié)為完全圖或者非完全圖問題。對于滿足三角不等性的對稱旅行售貨員問題，可以在多項式的計算時間內(nèi)求得近似解。除此之外，的研究經(jīng)過了幾十年的發(fā)展，還引申出其它擴展形式，比如多旅行售貨員問題(Multi Salesman Problem)，它是由多人完成環(huán)游的，該問題可轉(zhuǎn)化為等價的單人問題求解。 啟發(fā)式算法啟發(fā)式算法不能保證搜索問題的全部解空間，所以也不能保證能夠搜到最優(yōu)解，甚至在某些實例上連解都得不到，但它們與精確算法相比卻具有運算時間上的優(yōu)勢，即它們的運算時間復雜度都只是多項式[2]，并不會隨著輸入規(guī)模的擴大而產(chǎn)生“組合爆炸”。2 精確算法求解策略及優(yōu)化算法 動態(tài)規(guī)劃思想簡介我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃，這種動態(tài)規(guī)劃是在研究多階段決策問題時推導出來的，具有嚴格的數(shù)學形式，適合用于理論上的分析。 動態(tài)規(guī)劃求解旅行售貨員問題旅行售貨員問題其實就是一個最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。 或者，我們可以用：， in ，即為所求 ()其中表示從出發(fā)，經(jīng)過中每個城市一次且一次，最短路徑。每個節(jié)點包括如下區(qū)域：x ，從到的整數(shù)排列，其中x [ 0 ] = 1 ；s，一個整數(shù)，使從排列樹根節(jié)點到當前節(jié)點的路徑定義了旅行路徑的前綴x[0: s]；而剩余待訪問的節(jié)點是x [ s + 1 : n 1 ]；cc，旅行路徑前綴，即解空間樹中從根 節(jié)點到當前節(jié)點的耗費；lcost，該節(jié)點子樹中任意葉節(jié)點中的最小耗費；rcost，從頂點x [ s : n 1 ]出發(fā)的所有邊的最小耗費之和?；罟?jié)點按其lcost值從最小堆中取出。根的孩子作為第一個節(jié)點，在此節(jié)點上，所生成的旅行路徑前綴只有一個頂點1，因此s=0， x[0]=1， x[1: n1]是剩余的頂點(即頂點 )。while 循環(huán)不斷地展開節(jié)點，直到找到一個葉節(jié)點。由于算法本身的性質(zhì)，在葉節(jié)點上lcost 和cc恰好等于葉節(jié)點對應的旅行路徑的耗費。 其余的節(jié)點都放在while 循環(huán)的第二種情況中處理。由于每個包含此前綴的旅行路徑都必須包含離開每個剩余頂點的出邊，因此任何葉節(jié)點對應的耗費都不可能小于cc加上離開各剩余頂點的出邊耗費的最小值之和，因而可以把這個下限值作為節(jié)點所生成孩子的lcost值。如果在當前擴展結(jié)點處不能再向縱深方向轉(zhuǎn)移，則當前擴展結(jié)點成為死結(jié)點。設開始時x=[ 1，2，… n ]，則相應的排列樹由x[ 1: n ]的所有排列構(gòu)成。如果所給的圖不含旅行售貨員回路，則返回NoEdge。此時，算法檢測圖是否存在一條從頂點x[ n1 ]到頂點x[ n ]的邊和一條從頂點x[ n ]到頂點1的邊。當時，當前擴展結(jié)點位于排列樹的第層。具體算法程序見附錄B。 回溯算法的改進對算法改進的基本思想：在建立解空間樹后，使用新方法將已建立的解路徑反轉(zhuǎn)，找出其重復解，然后從解空間樹中將其刪除，直到刪除所有的重復解[4]。 i++){ void recordpath [ i ] ( ){ int recordarr[ M ] = new array [ dep three( )]。void deletesub( edge s){do{if super[ j](s){delete s。}while (j = dep three())}}}我們可以得到如下結(jié)論：經(jīng)過新解法的簡化后，解空間樹變?yōu)樵瓉淼亩种?，所需輔助空間復雜度較小，只有，而且實現(xiàn)簡單,可以保證找到最優(yōu)解，這大量地減少了搜索路徑，并省掉了這些路徑的權(quán)值計算，節(jié)省了很多搜索時間，提高了搜索效率,有效的降低了算法的空間復雜度。動態(tài)規(guī)劃講究的是狀態(tài)的轉(zhuǎn)化，以狀態(tài)為基準，確定算法，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。如果想要搜索時，發(fā)現(xiàn)有很多重復計算，就應該想到用動態(tài)規(guī)劃了。動態(tài)規(guī)劃雖然效率高，但是階段的劃分和狀態(tài)的表示比較復雜，另外，搜索的時候只要保存單前的結(jié)點；而動態(tài)規(guī)劃則至少要保存上一個階段的所有節(jié)點。而備忘錄法則可以避免這種問題，備忘錄法的優(yōu)點是實現(xiàn)簡單，且在子問題空間中存在大量冗余子問題的時候效率較高；但是要占用較大的內(nèi)存空間(需要開一個很大的表來記錄已經(jīng)解決的子問題)，而且如果用遞歸實現(xiàn)的話遞歸壓棧出棧也會影響效率；而自底向上的動態(tài)規(guī)劃一般用for循環(huán)就可以了?；厮莘ǖ那蠼饽繕耸钦页鲋袧M足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值(限界)，并根據(jù)這些已計算出的函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上的最優(yōu)解的分支推進，以便盡快的找出一個最優(yōu)解。但這種算法對數(shù)學及科學素養(yǎng)要求較高，在此我們不做過多討論，而簡單的討論一下與生物學結(jié)合的遺傳算法。早期遺傳算法的研究特點是側(cè)重于對一些復雜的操作的研究。1970年，遺傳算法應用于模式識別中。之后，有人將選擇、交叉和變異操作進一步完善和系統(tǒng)化，同時又提出了諸如代溝等新的遺傳操作技術，為遺傳算法及其應用打下了堅實的基礎。遺傳算法的智能性包括自組織、自適應和自學習等，應用遺傳算法求解問題時，在確定了編碼方案、適應值函數(shù)及遺傳算子后，算法將應用演化過程中獲得的信息進行自組織搜索，適者生存的選擇策略賦予了遺傳算法自適應的能力，同時也賦予了它根據(jù)環(huán)境的變化自動發(fā)現(xiàn)環(huán)境的特征和規(guī)律的能力。通常假設一個合理的切割模式的余料不應該大于等于客戶需要的鋼管的最小尺寸。遺傳算法用與優(yōu)化問題時，其最主要的特征就是：它不在單點尋優(yōu)，而是從整個種群中選擇生命力強的個體產(chǎn)生新的種群；它使用隨機轉(zhuǎn)換原理而不是確定性規(guī)則工作。在使用遺傳算法求解問題時，可以將數(shù)字1到的任何一個全排列均看作一個個體，而則作為個體的適應度。Step3：計算城市間的距離矩陣。Step6：根據(jù)累積選擇概率，以輪盤賭方式選擇個個體，以順序交叉方式產(chǎn)生下一代種群，并計算其個體的適應度。步驟5當中，個體的選擇概率與其適應度成正比。本章介紹了遺傳算法的基本原理和發(fā)展歷程。智能計算是連接主義、分布式人工智能、和自組織系統(tǒng)理論共同發(fā)展的產(chǎn)物。鳥群飛向的棲息地類比為優(yōu)化算法可能解的位置[8]。 微粒子算法結(jié)合旅行售貨員問題微粒群算法在問題上的研究，既為大規(guī)模復雜問題的求解提供了新的設計方法，又為這樣具有實際應用價值的問題的解決提供了新的思路。其研究成果必將推動組合優(yōu)化、微粒群算法的研究和發(fā)展。5 旅行售貨員問題的應用廣泛的應用于運輸、生產(chǎn)、國防、生物、計算機應用等領域以外，還為離散優(yōu)化中其他各類算法提供了思想方法平臺，例如：印刷電路板的鉆孔路線方案，連鎖店的貨物配送路線，數(shù)控機床的運作等問題，經(jīng)過簡單處理，均可建模為問題，因而對尋找出有效的啟發(fā)式算法，就具有重要的理論意義。從1940年開始問題的第二個應用包括從某地運輸農(nóng)耕設備到另一個地方去檢測土壤。在減少費用上就扮演了一個非常重要的角色。它在廣泛的應用于運輸、生產(chǎn)、國防、生物、計算機等領域以外，還為離散優(yōu)化中各類算法提供了思想方法平臺。這包括了精確算法和啟發(fā)式算法。由于水平的不足，在論文的寫作中有很多遺憾。 // 計算MinOut = 離開頂點i的最小耗費邊的耗費 T MinSum = 0。 for (int j = 1。 (a[j] Min || Min == NoEdge)) Min = a[j]。 } MinHeapNode E。 i++) = i + 1。 T bestc = NoEdge。amp。 = bestc。} else {// 產(chǎn)生孩子 for (int i = + 1。 T b = cc + rcost。 for (int j = 0。 = [+1]。 = rcost。} // 對本節(jié)點的處理結(jié)束 try {H。 // 沒有旅行路徑 // 將最優(yōu)路徑復制到v[1:n] 中 for (i = 0。 try {(E)?！rivate:　void Backtrack(int i)。 //當前最優(yōu)解　Type * *a。 //無邊際記　}。amp?！　estc =cc + a[x[n1]][x[n]]+ a[x[n]][1]。amp?！　c = a[x[i1]][x[i]]。 // 置x為單位排列for(int i=1。=n。 = No