使用遞歸尋找數組中所有元素的組合

Question

我知道有很多類似於這個問題的問題，並且我在過去的一個小時內回顧了他們，但是我無法弄清楚如何使用提供的答案。

我的任務如下：

編寫提示用戶輸入城市，那裏 每個城市都有一個名字和X和Y座標列表中的程序。輸入所有城市 後，程序應使用遞歸算法 來打印所有可能路線的長度，這些路線始於 輸入的第一個城市，在輸入的最後一個城市結束，並訪問列表中的每個城市 。對於每條路線，程序應打印每個訪問城市的名稱 ，然後打印路線的長度。

我打破了這個問題，我可以找出大部分代碼。什麼讓我卡住是找到所有可能的組合之間的第一和最後一個城市。我到底該怎麼辦？ 我想解決它與一個簡單的5整數數組和我的生活我無法弄清楚如何打印所有組合。

你能否幫助我克服這個可怕的問題？

謝謝。

Answer 1

而不是使用陣列我建議你使用圖形。

你可以閱讀更多關於旅行商問題這裏TSP或Brute-force for TSP

Answer 2

你不得不使用遞歸算法？

如果沒有，這裏是我的建議：

假設進入城市是A，C1，...，CN，B，其中A和B是第一和最後一個城市。第一個和最後一個城市不能改變，所以你應該計算n城市的所有組合。要計算所有組合，您可以計算從0到2^n-1。對於計數器的每個值，您都有一個從A到B的路徑。每個計數器值的每一位可能與一個城市（Ci）有關。現在的計數器的每個值可以打印路徑形式A到B（有一些詞）：

• 如果在計數器值一個城市的相關位爲0，因此相關的城市是不是在路徑
一個觀看城市
• 如果計數器值的城市的相關位是1，那麼相關的城市就是路徑中的被查看城市。

Answer 3

這是一個衆所周知的圖表方法。如果您有關於圖表的知識，只需看一看DFS (recursively)就很可能符合您的期望。