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