程序設(shè)計(jì)中，有一種特殊的程序——遞歸程序，遞歸程序是直接調(diào)用自己或通過一系列的過程間接調(diào)用自己的程序。遞歸程序在程序設(shè)計(jì)中經(jīng)常出現(xiàn)，因此應(yīng)該學(xué)會(huì)使用遞歸程序求解問題，但遞歸程序運(yùn)行的效率一般都比較低，因此應(yīng)對(duì)遞歸程序進(jìn)行優(yōu)化。
下面結(jié)合旅行家問題談?wù)勥f歸的優(yōu)化。
一．遞歸程序的實(shí)現(xiàn)
旅行家問題如下：旅行家要旅行N個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是有名的N—P難題之一。在N很大時(shí)，并不采用本文所用的遞歸遍歷方法，而是采用其他方法，如神經(jīng)網(wǎng)絡(luò)、遺傳算法等，得到問題的解。
要得到N個(gè)城市依次經(jīng)歷的最短路徑，應(yīng)把各個(gè)對(duì)N個(gè)城市的經(jīng)歷所經(jīng)過的路程相比較，選出其中的最小值作為返回結(jié)果。
用遞歸程序解決旅行家問題時(shí)，思路與循環(huán)方法一樣：找出各種可能的經(jīng)歷順序，比較在各個(gè)順序下所走的路程，從中找出最短路程所對(duì)應(yīng)的經(jīng)歷順序。該問題中如何通過遞歸得到對(duì)所有可能路徑的經(jīng)歷應(yīng)作為重點(diǎn)，而對(duì)路程的計(jì)算、比較、更新與循環(huán)方法類似。在該問題的遞歸調(diào)用中，第n對(duì)第n-1層傳遞過來的已經(jīng)經(jīng)歷的城市進(jìn)行判斷，以決定是否已經(jīng)遍歷，如果N個(gè)城市已經(jīng)遍歷，則計(jì)算、比較、更新路程，然后向上一層返回；如果沒有遍歷，則選擇一個(gè)未經(jīng)歷的城市加入已經(jīng)歷的城市并一同傳遞給第n+1層。在這里，第n層調(diào)用傳入的參數(shù)可以看成已經(jīng)經(jīng)歷的城市和已確定的最短路程，返回的結(jié)果可以看成經(jīng)更新的最短路程與經(jīng)歷順序。
下面結(jié)合旅行家問題談?wù)勥f歸的優(yōu)化。
一．遞歸程序的實(shí)現(xiàn)
旅行家問題如下：旅行家要旅行N個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是有名的N—P難題之一。在N很大時(shí)，并不采用本文所用的遞歸遍歷方法，而是采用其他方法，如神經(jīng)網(wǎng)絡(luò)、遺傳算法等，得到問題的解。
要得到N個(gè)城市依次經(jīng)歷的最短路徑，應(yīng)把各個(gè)對(duì)N個(gè)城市的經(jīng)歷所經(jīng)過的路程相比較，選出其中的最小值作為返回結(jié)果。
用遞歸程序解決旅行家問題時(shí)，思路與循環(huán)方法一樣：找出各種可能的經(jīng)歷順序，比較在各個(gè)順序下所走的路程，從中找出最短路程所對(duì)應(yīng)的經(jīng)歷順序。該問題中如何通過遞歸得到對(duì)所有可能路徑的經(jīng)歷應(yīng)作為重點(diǎn)，而對(duì)路程的計(jì)算、比較、更新與循環(huán)方法類似。在該問題的遞歸調(diào)用中，第n對(duì)第n-1層傳遞過來的已經(jīng)經(jīng)歷的城市進(jìn)行判斷，以決定是否已經(jīng)遍歷，如果N個(gè)城市已經(jīng)遍歷，則計(jì)算、比較、更新路程，然后向上一層返回；如果沒有遍歷，則選擇一個(gè)未經(jīng)歷的城市加入已經(jīng)歷的城市并一同傳遞給第n+1層。在這里，第n層調(diào)用傳入的參數(shù)可以看成已經(jīng)經(jīng)歷的城市和已確定的最短路程，返回的結(jié)果可以看成經(jīng)更新的最短路程與經(jīng)歷順序。