Java語言TSP遞歸程序的優化
|
程序設計中，有一種特殊的程序——遞歸程序，遞歸程序是直接調用自己或通過一系列的過程間接調用自己的程序。遞歸程序在程序設計中經常出現，因此應該學會使用遞歸程序求解問題，但遞歸程序運行的效率一般都比較低，因此應對遞歸程序進行優化。
下面結合旅行家問題談談遞歸的優化。
一．遞歸程序的實現
旅行家問題如下：旅行家要旅行N個城市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員問題，是有名的N—P難題之一。在N很大時，并不采用本文所用的遞歸遍歷方法，而是采用其他方法，如神經網絡、遺傳算法等，得到問題的解。
要得到N個城市依次經歷的最短路徑，應把各個對N個城市的經歷所經過的路程相比較，選出其中的最小值作為返回結果。
用遞歸程序解決旅行家問題時，思路與循環方法一樣：找出各種可能的經歷順序，比較在各個順序下所走的路程，從中找出最短路程所對應的經歷順序。該問題中如何通過遞歸得到對所有可能路徑的經歷應作為重點，而對路程的計算、比較、更新與循環方法類似。在該問題的遞歸調用中，第n對第n-1層傳遞過來的已經經歷的城市進行判斷，以決定是否已經遍歷，如果N個城市已經遍歷，則計算、比較、更新路程，然后向上一層返回；如果沒有遍歷，則選擇一個未經歷的城市加入已經歷的城市并一同傳遞給第n+1層。在這里，第n層調用傳入的參數可以看成已經經歷的城市和已確定的最短路程，返回的結果可以看成經更新的最短路程與經歷順序。
在Java中定義一個類
| Class Cities { private int[][] cities； //各城市表示為（X,Y）X,Y為0到99之間的值 private int[] shortestPath； //保存最短路程對應的經歷順序 private int num； //保存N（城市個數） private long shortestLength = 100000000；//N個城市遍歷時可能最大路程 private long getLength(int[] tPath) {．．．} //計算以tPath為經歷順序的路程 public Cities(int n) //構造n個城市的坐標，假設為0到99之間的隨機數 { ．．． } public int[] getShortestPath() //獲得最短路徑 { int[] tempPath = new int[num]； shortestPath = new int[num]； int[] citiesToured = new int[num]； //保存第I個城市是否已經經歷 int citiesNum = 0； //已經經歷城市的個數 for(int i=0； i<num； i++) citiesToured[i] = 0； goThrough(tempPath, citiesNum, citiesToured)；//遍歷各城市 for(int i=0； i<num； i++) tempPath[i] = shortestPath[i]； //得到遍歷順序 return tempPath； //返回結果 } private void goThrough(int[] tPath, int cNum, int[] cToured) //遍歷N個城市 { if (cNum == 0) //無經歷城市時，選擇第1個城市 { cNum++； tPath[0] = 0； cToured[0] = 1； goThrough(tPath, cNum, cToured)； } else if (cNum == num) //各個城市已經經歷，結束 { long tempLength = getLength(tPath)；//計算此經歷順序所走的路程 if (tempLength < shortestLength) //比較路程 { shortestLength = tempLength； //更新最短路程及其經歷順序 for(int i=0； i<num； i++) shortestPath[i] = tPath[i]； } } else { for(int i=0； i<num； i++) if (cToured[i] != 1) //選擇未經歷的城市 { cToured[i] = 1； //加入已經歷城市 tPath[cNum]= i； cNum++； //已經歷城市個數+1 goThrough(tPath, cNum, cToured)；//調用下一層 cToured[i] = 0； //恢復本層的狀態： cNum--； //已經歷城市及個數 } //End if in for(i) } //End else } private long getLength(int[] tPath) //以指定順序計算遍歷路程 { long length = 0； //路程 int nowPoint = 0； //當前城市，第一次取0 for(int i=1； i<num； i++) { int j = tPath[i]； length+=(long)Math.sqrt((cities[j][0]-cities[nowPoint][0])*(cities[j][0]-cities[nowPoint][0])+(cities[j][1]-cities[nowPoint][1])*(cities[j][1]-cities[nowPoint][1]))；//加上當前、下一城市間的距離 nowPoint = j； //更新當前城市 } length+=(long)Math.sqrt((cities[0][0]-cities[nowPoint][0])*(cities[0][0]-cities[nowPoint][0]) +(cities[0][1]-cities[nowPoint][1])*(cities[0][1]-cities[nowPoint][1]))；//加上首尾城市間的距離 return length； } } // Cities類定義結束 |
在這里使用遞歸，實現了對N可變時問題的求解。