递归查找路径

我有一系列从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个点时找到最短可能的课程。

问题：基数和递归情况会是什么？

来源

2013-10-01 Marshall Lyon

看看Dijkstra's_algorithm https://en.wikipedia.org/wiki/Dijkstra's_algorithm –

基本上你想要做的是从集合{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);

您可以更改函数并添加参数，以便返回最佳路径和最小值。还有其他（也许更短）的方式来创建这些组合，关于我的实现的好处是它在内存上很轻，并且不需要存储所有可能的组合。

来源

2013-10-01 10:01:08

递归查找路径

回答

相关问题