遞歸查找路徑

Question

我有一系列從0-9範圍內的數字。每個數字表示具有x和y座標的位置。所以，位置0可以表示（5，5）或類似的東西，總是（x，y）。現在我需要做的是遞歸地使用5個位置對每個可能的路線進行打擊以獲得用戶給出的位置。例如：

Input = (1, 2) //This is the co-ordinate the user gives. 

現在給出這個輸入，它應該採取每一個可能的路徑，並找到最短的一個。有些路徑可能是：

start 0 1 2 3 4 input 
start 0 1 2 3 5 input 
start 0 1 2 3 6 input 
start 0 1 2 3 7 input 
start 0 1 2 4 3 input 
start 1 0 2 3 5 input 
and so on.... 

它可能是0-9中5個數字的任意組合。它必須在輸入目的地結束並從起始目的地開始。數字不能重複使用。因此，我需要遞歸地添加給定課程的所有距離（例如，開始0 1 2 3 4輸入），並在通過這5個點時找到最短可能的課程。

問題：基數和遞歸情況會是什麼？

Answer 1

基本上你想要做的是從集合{1，...，n}生成大小爲k（路徑長度）的所有組合，然後計算它的路徑值。

這裏的一個C＃代碼示例：

void OPTPathForKSteps(List<int> currentPath, List<int> remainingPositions, int remainingSteps) 
    { 
     if (remainingSteps == 0) 
     { 
      // currentPath now contains a combination of k positions 
      // do something with currentPath... 
     } 
     else 
     { 
      for (int i = 0; i < remainingPositions.Count; i++) 
      { 
       int TempPositionIndex = remainingPositions[i]; 
       currentPath.Add(TempPositionIndex); 
       remainingPositions.RemoveAt(i); 

       OPTPathForKSteps(currentPath, remainingPositions, remainingSteps - 1); 

       remainingPositions.Insert(i, TempPositionIndex); 
       currentPath.RemoveAt(currentPath.Count - 1); 
      } 
     } 
    } 

這是初始呼叫的功能（假設位置是0-2的整數列表... n個位置，而k是路徑的長度）：

OPTPathForKSteps(new List<int>(), Positions, K); 

您可以更改函數並添加參數，以便返回最佳路徑和最小值。 還有其他（也許更短）的方式來創建這些組合，關於我的實現的好處是它在內存上很輕，並且不需要存儲所有可能的組合。