tsp遞歸程序實現(Java)（zz）
程序設計中，如果一個程序直接調用自己或通過一系列的過程間接調用自己，那么這個程序就稱為遞歸程序，遞歸程序（直接或間接）調用自己的過程稱為遞歸調用，其中直接調用自己的成為直接遞歸調用，間接調用自己的稱為間接遞歸調用。直接遞歸調用形如：
funa（）
{ ．．．
funa（）；
．．．
}
間接遞歸調用形如：
funa（）
{ ．．．
funb（）；
．．．
}
funb（）
{ ．．．
funa（）;
．．．
｝
還有些數據結構如二叉樹，結構本身固有遞歸特性；此外，有一類問題，其本身沒有明顯的遞歸結構，但用遞歸程序求解比其他方法更容易編寫程序，如八皇后問題、漢諾塔問題等。
正因為遞歸程序的普遍性，我們應該學會使用遞歸來求解問題。直接遞歸程序與間接遞歸中都要實現當前層調用下一層時的參數傳遞，并取得下一層所返回的結果，
并向上一層調用返回當前層的結果。至于各層調用中現場的保存與恢復，均由程序自動實現，不需要人工干預。因此，在遞歸程序的設計中關鍵是找出調用所需要的
參數、返回的結果及遞歸調用結束的條件。如在階乘函數Fact(n)中，各層要求傳遞一個自然數n，返回n*
Fact(n-1)，遞歸調用結束的條件是n=0；據此，可以方便地寫出它的對應程序（Java語言）：
Class ClassFact
{ public static long Fact ( int n )
{
if (n==0) return 1；
return n*Fact(n - 1)；
}
}
在一些稍微復雜的問題中，依據上述方法也可以方便地寫出遞歸程序，下面結合旅行家問題談談遞歸的實現。
旅行家問題：旅行家要旅行N個城市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題，是有名的N-P難題。在N很大時，并不采用本文所用的遞歸遍歷方法，而是采用神經網絡、遺傳算法等方法得到問題的解。
要得到N個城市依次經歷的最短路徑，應把各個對N個城市的遍歷所經過的路程相比較，選出其中的最小值作為返回結果。當N比較小時，若N固定，可以用循環實現對N（N=3）個城市的遍歷，如下所示：
Class Cities
{
private int[][] cities = {{1,23}, {45,68}, {34,26}}；//各城市表示為（X,Y）X,Y為0到99之間的值
private long shortestLength = 1000000；//可能的最大路程
private long getLength(int i，int j，int k)
{．．．} //計算以i j k為經歷順序的路程
public int[] getShortestPath()
{
int[] shortestPath = new int[3]；
for(int i=0； i<3； i++)
{
for(int j=0； j<3； j++)
{
if (j==i) continue；
for(int k=0； k<3； k++)
{
if (k==j) | | (k==i) continue；
//計算以i ，j， k為經歷順序的路程
long tempLength = getLength(I，j，k)；
//更新最短路程、經歷順序
if (tempLength < shortestLength)
{
shortestLength = tempLength；
shortestPath[0] = i；
shortestPath[1] = j；
shortestPath[2] = k；
} // End if
} // End for k
} // End for j
} // End for i
return shortestPath；
}
顯然，當N變化時，要重新編寫程序。因此考慮使用遞歸程序實現對N可變時的求解。
用遞歸程序解決旅行家問題時，思路與循環方法一樣：找出各種可能的經歷順序，比較在各個順序下所走的路程，從中找出最短路程所對應的經歷順序。在該問題的
遞歸調用中，當前層對上一層傳遞的已經經歷的城市進行判斷，以決定是否已經遍歷，若已遍歷，則結束本次調用并向上一層返回；若未結束，則選擇一個未經歷的
城市經歷，再把經歷信息傳遞給下一層。在這里，第n層調用傳入的參數可以看成已經遍歷的城市和已確定的最短路程，返回的結果可以看成更新的經歷順序和最短
路程（若n<N則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可變時問題的求解。
由于遞歸過程結構清晰，程序易讀，而且正確性容易得到驗證。因此，利用允許遞歸的語言如Pascal 、C(++)
等進行程序設計時，給用戶編制程序和調試程序帶來很大的方便。但同時，由于遞歸調用過程中要保存大量的實參、局部變量，及程序控制的保存與恢復。因此，遞
歸程序運行的效率比較低，占用內存多，執行時間長，如果能在程序中消除過程的遞歸調用，肯定可以提高程序的時空效率。另一方面，并非一味地消除遞歸，因為
在一些情況下，程序結構簡單、可讀性強比運行效率高更具有意義。