c# - 寻找所有可能的路径

Question

我无法找到所有可能的路径。

a a a b

b a a a

a b b a

从起点 0,0 到终点 2,3。 我需要获得所有可能的路径。

我可以做的可能 Action 是向下移动和向右移动。

让我告诉你我被困在哪里。 我正在尝试使用递归函数。从 0,0 点开始，尽可能向右移动，只有在必须时才向下移动。

我的递归函数:

public static move(int i,int j)
{
     if(possible(x,y+1))
    {
       move(x,y+1);
       move(x+1,y);
    }

}


public static bool possible(int i,int j)
        {
            if((i >=0 && i<3 ) && (j>=0 && j<4))
                return true;
            else
                return false;

        }

不确定我的递归移动函数。还是需要扩充吧。我不知道应该如何实现。

我能够使用该移动方法遍历到角节点，但我需要该函数在到达角右上角点 (0,4) 的所有可能移动时回溯。

Answer 1

你需要停下来，向后退一大步。

第一步应该是提出方法的签名。问题陈述是什么？

Find all possible paths

未提及:从特定坐标开始。

因此该方法需要返回一组路径:

static Set<Path> AllPaths(Coordinate start) { /* a miracle happens */ }

好的，现在我们到了某个地方；现在很清楚我们需要什么。我们需要一组东西，我们需要一条路径，我们需要坐标。

什么是坐标？一对整数:

struct Coordinate
{
  public int X { get; }
  public int Y { get; }
  public Coordinate(int x, int y) : this() 
  {
    this.X = x;
    this.Y = y;
  }
}

完成。所以弹出堆栈；什么是路径？路径可以为空，也可以是第一步后跟路径:

sealed class Path 
{
  private Path() { }
  private Path(Coordinate first, Path rest)
  {
    this.first = first;
    this.rest = rest;
  }
  public static readonly Path Empty = new Path();
  private Coordinate first;
  private Path rest;
  public bool IsEmpty => this == Empty;
  public Coordinate First 
  { 
    get  
    {
      if (this.IsEmpty) throw new Exception("empty!");
      return first;
    }
  }
  public Path Rest
  {   
    get 
    {
      if (this.IsEmpty) throw new Exception("empty!");
      return rest;
    }
  }
  public Path Append(Coordinate c) => new Path(c, this);
  public IEnumerable<Coordinate> Coordinates()
  {
    var current = this;
    while(!current.IsEmpty)
    {
      yield return current;
      current = current.Rest;
    }
  }
}

完成。

现在你实现Set<T> .您将需要操作“所有项目”和“将此集合与另一个结合以产生第三个”。确保集合是不可变的。您不想在向集合中添加新项目时更改集合；你想要一套不同的。就像你加 1 时不把 3 变成 4 一样； 3和4是不同的数字。

现在您拥有了实际解决问题所需的所有工具；现在你可以实现了

static Set<Path> AllPaths(Coordinate start) 
{ 
   /* a miracle happens */ 
}

那么这是如何工作的呢？请记住，所有递归函数都具有相同的形式:

• 破案
• 如果我们不是在一个微不足道的情况下，将问题缩小到一个较小的情况，递归地解决它，并组合解决方案。

那么什么是微不足道的情况呢？

static Set<Path> AllPaths(Coordinate start) 
{ 
   /* Trivial case: if the start coordinate is at the end already
      then the set consists of one empty path.  */

实现。

什么是递归情况？

   /* Recursive case: if we're not at the end then either we can go
      right, go down, or both.  Solve the problem recursively for
      right and / or down, union the results together, and add the 
      current coordinate to the top of each path, and return the
      resulting set. */

实现。

这里的教训是:

• 列出问题中的所有名词:集合、路径、坐标等。
• 制作一个代表每一个的类型。保持简单，并确保准确实现每种类型所需的操作。
• 现在您已经为每个名词实现了抽象，您可以开始设计使用这些抽象的算法，并确信它们会起作用。
• 记住递归的基本规则:尽可能解决基本情况；如果不是，解决较小的递归情况并组合解决方案。