【文章內(nèi)容簡介】 子結點分別估算可能取得的目標函數(shù)值1()boundx ，其含義是以該孩子結點為根的子樹所可能取得 的目標函數(shù)值不大于 1()boundx ，也就是部分解應滿足： 1 1 2 1 2 1 2( ) ( , ) .. . ( , , .. ., ) .. . ( , , .. ., )knb o u n d x b o u n d x x b o u n d x x x b o u n d x x x? ? ? ? ? 本文本欲詳細討論該算法，但無奈在編程問題中，尚有問題有待解決，時間所限，不得已放棄。本人編程過程中所用算法思想與老師課上所教略有不同，在尋找下界時，是首先把每個結點所能到達的各個結點及其可能的路徑算出來，并添加到 PT 表中，但最后，不知是何原因，在還有一個城市尚未加入時， PT 表的添加出現(xiàn)了問題，思忖良久，仍未解決，時間所限，迫不得已，留待以后有時間再另行研究， 本文就只給出動態(tài)規(guī)劃法和貪心法的具體求解過程。 四、 總結 本文主要重點討論了動態(tài)規(guī)劃法和貪心法求解 TSP問題算法，并附錄給出了相應程序。 動態(tài)規(guī)劃法中對于頂點元素生成的子集本文中用字符串形式存儲，然后再用遞歸方法按照子集中元素個數(shù)從小到大開始賦值。因為后面元素個數(shù)較多的子集與前面比其元素個數(shù)少 1的子集間有一定對應關系，所以用遞歸方式，可以簡便很多。個人覺得這算本文的一大特色。另，在計算 d[i][j] =min(c[i][k]+d[k][j1])時，獲得 d[k][j1]的過程比較困難，運用字符串后，我們就可以首先找到指定字符，然后去掉該字符，返回剩余字符串，在與V[]逐個比較，找到與其相等的 V[]中元素對應下標，此下標即為 j1；具體求解過程可參考附錄源程序，有詳細說明。在求解最佳路徑所經(jīng)過城市順序時，本文是通過邊查找 d[i][j]邊記錄路徑的，這樣可以省掉很多麻煩，另，路徑也是采用字符串形式的數(shù)組，數(shù)組規(guī)模與存儲城市間距離的 c[][]數(shù)組相同，由于很多元素均不需賦值，這樣做可能會浪費內(nèi)存空間，但是目前還沒找到更好地求解方法。 想 貪心法中，由于貪心法相對動態(tài)規(guī)劃法要簡單很多，每次在查找最近城市時所得的頂點均為最后該法最佳路徑所經(jīng)過的城市編號，規(guī)模相對較小，容易確定，操作相對簡單，所以本文用數(shù)組 V[]存放最佳路徑所經(jīng)過的城市編號順序相對來說方便很多。另外，本文用path[]整型數(shù)組存放所經(jīng)路徑的長度，最后相加即可得最短路徑。 動態(tài)規(guī)劃法相對貪心法來說雖然要精確些，但代碼相對繁雜很多，對時間和空間要求很多，僅適用于城市數(shù)量較小的情況。貪心法雖然比較簡單，實現(xiàn)起來比較容易，但不是很精確，當圖中頂點個數(shù)較多并且各邊的 代價值分布比較均勻時，貪心法可以給出較好的近似解，不過，這個近似解以何種程度近似于最優(yōu)解，卻難以保證。 另外，動態(tài)規(guī)劃法有一個明顯的缺點，就是出發(fā)城市只能是第 0 個城市（城市從 0 開始編號），若出發(fā)城市改變，則必須以該城市為第 0個城市順序給其他城市編號，輸入城市間距離。由于若出發(fā)城市任意，編碼的難度大大增加，所以最后不得已放棄，但這大大地限制了程序的通用性。而對于貪心法，本文很好地避免了這個問題，一旦城市編號確定，可以從任意城市出發(fā)，這也是本文中貪心法優(yōu)于動態(tài)規(guī)劃法的一點。 本文程序優(yōu)點，各個子函 數(shù)功能分隔很明顯，沒有大量集中在一個函數(shù)里面，而是分成了幾個不同功能的小函數(shù)，這樣程序可閱讀性提高。另外，程序中有詳細注釋，程序中變量取名都是根據(jù)變量的性質和所代表的含義命名的，也相應提高了程序的可讀性。 對于動態(tài)規(guī)劃法，城市個數(shù)可以在算法時間允許的范圍內(nèi)任意，于這點來說，通用性較好；對于貪心法，出發(fā)城市可以任意，城市個數(shù)也可以任意，通用性較好。 5. 建議 當城市個數(shù)較少時，用動態(tài)規(guī)劃法求出最優(yōu)解；當城市個數(shù)較多并且各邊的代價值分布比較均勻時，貪心法可以給出較好的近似解。 參考文獻： （ 1） 《計算機算法分析與設計》第二版，王曉東編著，電子工業(yè)出版社 （ 2） Java語言與面向對象程序設計（第 2版）印旻、王行言編著，清華大學出版社 （ 3）求解 TSP算法，周康、強小利、同小軍、許進，計算機工程與應用 （ 4） 百度文庫 （ 5） 百度百科 附錄：源代碼 動態(tài)規(guī)劃法 ： package exp2。 import 。 public class TSPDynamic { String[] V。//頂點生成的子集，這里把每一個子集用一個字符串表示 int[][] c。//頂點間距離 int[][] d。//存放迭代結果 int N。 //城市個數(shù) String[][] path。//用于存放每種選擇下經(jīng)過的城市 static int IFINITE = 99999。//無窮大距離 表示城市自己到達自己時，距離無窮大，不作為考慮因素 //構造函數(shù) public TSPDynamic(){ initialC()。 initialV1()。 } //初始化數(shù)組 c[]，即頂點間距離 public void initialC(){ Scanner in = new Scanner( )。 (請輸入城市個數(shù)： （注意根據(jù)實際情況城市個數(shù)不可小于 1！）)。 N = ()。 if(N = 1){ (不符合要求，請認真核對！ )。 (0)。//輸入錯誤，結束！ } (請輸入城市相鄰城市間距離（城市從 0開始編號，且出發(fā)城市為第 0個城市！）： )。 c = new int[N][N]。//為 c分配空間 for(int i = 0 。 i N 。 i ++) for(int j = 0 。 j N 。 j ++){ c[i][j] = ()。 //輸入時，按城市編號從小到大，如若兩城市間沒有公路相連，則距離為無窮大。本城市與本城市間距離也為無窮大。 } } //初始化頂點生成的子集的對外調(diào)用函數(shù) public void initialV1(){ V = new String[(int)(2,N1)]。//為 V分配空間 initialV(0,0)。 } //具體的初始化頂點生成的子集 //本程序使用遞歸調(diào)用方法初始化 V，并按照數(shù)字大小順序排序。另，子集使用字符型形式存放的 //我們是按照子集中元素個數(shù)從小到大逐個添加的，后面的子集是前面對應子集加上一個元素組成的，故用遞歸 public void initialV(int m , int len) {//m代表下一個即將初始化的 V數(shù)