Java學習:TSP遞歸程序的優化

MILY: 宋體; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">　　程序設計中，有一種特殊的程序——遞歸程序，遞歸程序是直接調用自己或通過一系列的過程間接調用自己的程序。遞歸程序在程序設計中經常出現，因此應該學會使用遞歸程序求解問題，但遞歸程序運行的效率一般都比較低，因此應對遞歸程序進行優化。

　　下面結合旅行家問題談談遞歸的優化。

　　一．遞歸程序的實現

　　旅行家問題如下：旅行家要旅行N個城市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員問題，是有名的N—P難題之一。在N很大時，并不采用本文所用的遞歸遍歷方法，而是采用其他方法，如神經網絡、遺傳算法等，得到問題的解。

　　要得到N個城市依次經歷的最短路徑，應把各個對N個城市的經歷所經過的路程相比較，選出其中的最小值作為返回結果。

　　用遞歸程序解決旅行家問題時，思路與循環方法一樣：找出各種可能的經歷順序，比較在各個順序下所走的路程，從中找出最短路程所對應的經歷順序。該問題中如何通過遞歸得到對所有可能路徑的經歷應作為重點，而對路程的計算、比較、更新與循環方法類似。在該問題的遞歸調用中，第n對第n-1層傳遞過來的已經經歷的城市進行判斷，以決定是否已經遍歷，如果N個城市已經遍歷，則計算、比較、更新路程，然后向上一層返回；如果沒有遍歷，則選擇一個未經歷的城市加入已經歷的城市并一同傳遞給第n+1層。在這里，第n層調用傳入的參數可以看成已經經歷的城市和已確定的最短路程，返回的結果可以看成經更新的最短路程與經歷順序。

　　在Java中定義一個類

　　ClassCities

　　{
　　
　　privateint[][]cities；//各城市表示為（X,Y）X,Y為0到99之間的值
　　
　　privateint[]shortestPath；//保存最短路程對應的經歷順序
　　
　　privateintnum；//保存N（城市個數）
　　
　　privatelongshortestLength=100000000；//N個城市遍歷時可能最大路程
　　
　　privatelonggetLength(int[]tPath){．．．}//計算以tPath為經歷順序的路程
　　
　　publicCities(intn)//構造n個城市的坐標，假設為0到99之間的隨機數
　　
　　{
　　
　?。?BR>　　
　　}
　　
　　publicint[]getShortestPath()//獲得最短路徑
　　
　　{
　　
　　int[]tempPath=newint[num]；
　　
　　shortestPath=newint[num]；
　　
　　int[]citiesToured=newint[num]；//保存第I個城市是否已經經歷
　　
　　intcitiesNum=0；//已經經歷城市的個數
　　
　　for(inti=0；i<num；i++)
　　
　　citiesToured[i]=0；
　　
　　goThrough(tempPath,citiesNum,citiesToured)；//遍歷各城市
　　
　　for(inti=0；i<num；i++)
　　
　　tempPath[i]=shortestPath[i]；//得到遍歷順序
　　
　　returntempPath；//返回結果
　　
　　}
　　
　　privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)//遍歷N個城市
　　
　　{
　　
　　if(cNum==0)//無經歷城市時，選擇第1個城市
　　
　　{
　　
　　cNum++；
　　
　　tPath[0]=0；

　　cToured[0]=1；
　　
　　goThrough(tPath,cNum,cToured)；
　　
　　}
　　
　　elseif(cNum==num)//各個城市已經經歷，結束
　　
　　{
　　
　　longtempLength=getLength(tPath)；//計算此經歷順序所走的路程
　　
　　if(tempLength<shortestLength)//比較路程
　　
　　{
　　
　　shortestLength=tempLength；//更新最短路程及其經歷順序
　　
　　for(inti=0；i<num；i++)
　　
　　shortestPath[i]=tPath[i]；
　　
　　}
　　
　　}
　　
　　else
　　　　
　　{
　　

　　for(inti=0；i<num；i++)
　　
　　if(cToured[i]!=1)//選擇未經歷的城市
　　
　　{
　　
　　cToured[i]=1；//加入已經歷城市
　　
　　tPath[cNum]=i；
　　
　　cNum++；//已經歷城市個數+1
　　
　　goThrough(tPath,cNum,cToured)；//調用下一層
　　
　　cToured[i]=0；//恢復本層的狀態：
　　
　　cNum--；//已經歷城市及個數
　　
　　}//Endifinfor(i)
　　
　　}//Endelse
　　
　　}
　　
　　
　　
　　privatelonggetLength(int[]tPath)//以指定順序計算遍歷路程
　　
　　{
　　
　　longlength=0；//路程
　　
　　intnowPoint=0；//當前城市，第一次取0
　　
　　for(inti=1；i<num；i++)
　　
　　{
　　
　　intj=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]))；//加上首尾城市間的距離
　　
　　returnlength；

　　}
　　
　　}//Cities類定義結束
　　
　　在這里使用遞歸，實現了對N可變時問題的求解。
　　
　　三．遞歸程序的優化

　　遞歸程序的優化是程序優化的一種，具有程序優化的一般性，同時更應考慮它的特殊性。遞歸程序優化中應主要著眼盡快結束遞歸，避免無謂的調用，因為結束得越早，程序所付出的代價就越小。
　　
　　在旅行家問題中，對城市的遍歷goThrough函數是遞歸程序，下面討論對它的優化。
　　
　?、瘢搯栴}的第一次優化：各個城市之間的距離在Cities類構造時就已經確定，而每一次遍歷各個城市后，getLength函數都要計算一次相鄰兩城市及首尾城市間的距離，顯然城市間距離的計算只要進行一次就可以了。因此可以定義一個函數InitDistance，在構造函數Cities()中調用，并重新定義getLength函數，直接對相鄰及首尾城市的距離取和。如下：
　　
　　1．類中增加屬性privatelong[]distance；//在InitDistance方法中構造
　　
　　2．定義私有方法privatevoidInitDistance()//計算各個城市之間的距離（由于僅計算一次，故未優化）
　　
　　privatevoidInitDistance()
　　
　　{
　　
　　distance=newlong[num][num];
　　
　　for(inti=0；i<num；i++)
　　
　　for(intj=0；j<num；j++)
　　
　　{
　　
　　if(i==j)
　　
　　distance[i][j]=0L；
　　
　　else
　　
　　distance[i][j]=(long)Math.sqrt(
　　
　　(cities[i][0]-cities[j][0])*(cities[i][0]-cities[j][0])+(cities[i][1]-cities[j][1])*(cities[i][1]-cities[j][1]))；
　　
　　}
　　
　　}
　　
　　3．重新定義getLength
　　
　　privatelonggetLength(int[]tPath)
　　
　　{
　　
　　longlength=0L；
　　
　　for(inti=1；i<num；i++)
　　
　　length+=distance[tPath[i-1]][tPath[i]]；
　　
　　length+=distance[tPath[0]][tPath[num-1]]；
　　
　　returnlength；
　　
　　}

　　4．重新定義構造函數Cities(intr)
　　
　　publicCities(intr)
　　
　　{．．．
　　　　
　　InitDistance()；//計算各個城市間的距離
　　
　　}
　
　
　?、颍搯栴}的第二次優化：考慮下面的情況，經歷順序為1—2—3—4—5—6—與1—2—3—4—6—5—二者中前四個城市經歷順序相同，可以定義一個變量來保存已經歷的路程，只有在經歷順序改變的時候才對已經歷的路程進行更新。進行如下優化：
　　
　　1．增加privatelongtouredLength屬性并初始化為0，用來記錄到“目前”為止所經歷的路程。
　　
　　2．重新定義goThrough
　　
　　privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)
　　
　　{
　　
　?。?/同上

　　elseif(cNum==num)
　　
　　{
　　
　　longtL=touredLength+distance[tPath[num-1]][tPath[0]]；▲//tL記錄已經歷的路程
　　
　?。ㄓ谩鴺酥靖倪M點，下同）
　　
　　if(tL<shortestLength)
　　
　　{
　　
　　shortestLength=tL；
　　
　　for(inti=0;i<num;i++)
　　
　　shortestPath[i]=tPath[i]；
　　
　　}

　　}
　　
　　else//0<citiesNum<N
　　
　　{
　　
　　for(inti=0；i<num；i++)
　　
　　if(cToured[i]!=1)//NotToured
　　
　　{
　　　　
　　tPath[cNum]=I；
　　
　　cToured[i]=1；
　　
　　touredLength+=distance[tPath[cNum-1]][i]；▲
　　
　　cNum++；
　　
　　goThrough(tPath,cNum,cToured)；
　　
　　cNum--；
　　
　　touredLength-=distance[tPath[cNum-1]][i]；▲
　　
　　cToured[i]=0；
　　
　　}
　　
　　}
　　
　　}

　　3．去除getLength。
　　
　?、螅搯栴}的第二次優化：進一步考慮對路程的計算，設想下面的情況：N=5，已經歷了2個城市，且旅行路程為200，目前已知的最短路程為260，而其他三個城市的任意兩個城市之間的距離大于30。在這種情況下，再繼續遍歷只是徒勞，此時就可以結束調用返回。針對這種情況，如下優化：
　　
　　1．增加屬性privatelongshortestDistance[]，來保存城市之間的最短距離，次最短距離，次次最短距離，．．．，并在InitDistance中得到各距離的值。
　　
　　privatevoidInitDistance()
　　
　　{
　　
　?。?BR>　　
　　shortestDistance=newlong[num+1]；
　　　　
　　shortestDistance[0]=0；

　　for(inti=0；i<num；i++)

　　{

　　longdis=10000L；
　　
　　for(intj=i+1；j<num；j++)
　　
　　if(distance[i][j]<dis)
　　
　　dis=distance[i][j]；
　　
　　shortestDistance[i+1]=shortestDistance[i]+dis；
　　
　　}
　　
　　}
　　
　　2．更新goThrough
　　
　　privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)
　　
　　{
　　
　?。?BR>　　
　　elseif(cNum==num)
　　
　　{
　　
　　longtL=touredLength+distance[tPath[num-1]][tPath[0]]；
　　
　　if(tL<shortestLength)
　　
　　{
　　

　　shortestLength=tL；
　　
　　for(inti=0；i<num；i++)
　　
　　shortestPath[i]=tPath[i]；
　　
　　}
　　
　　}
　　
　　else//0<citiesNum<num
　　
　　{
　　
　　if(touredLength+shortestDistance[num-cNum]<shortestLength)▲
　　
　　//如果已經歷的路程+可能的最短路程>已知的最短路程，則不再繼續走下去
　　
　　{
　　
　　for(inti=0；i<num；i++)
　　
　　if(cToured[i]!=1)//NotToured
　　
　　{
　　
　　tPath[cNum]=i；
　　
　　cToured[i]=1；
　　
　　touredLength+=distance[tPath[cNum-1]][i]；

　　cNum++；
　　　　
　　goThrough(tPath,cNum,cToured)；

　　cNum--；
　　
　　touredLength-=distance[tPath[cNum-1]][i]；
　　
　　cToured[i]=0；
　　
　　}
　　
　　}
　　
　　}
　　
　　}
　　
　　比較各種優化方法的求解時間，得到下表的數據（Windows98，PIII550，128M）：

       從以上數據可以得出結論：遞歸程序一般都有很大的優化空間，遞歸程序經過優化后，可以在很大程度上提高程序的效率。經過優化的程序既保留了遞歸程序簡單易讀的特點，又在一定程度上彌補了程序時間效率低的不足。

       同時，也可以看出遞歸程序的先天缺陷，在現實中大規模的旅行商問題遞歸程序是無法解決的（在可以接受的時間內），普遍采用的是遺傳算法來解決，因此應事先決定是否采用遞歸程序來解決自己的問題。即使如此，本文對于可以應用的遞歸程序來講也具有一定的參考意義。