寻找所有可能的路径

Question

我有一个问题,找到所有可能的路径.

AAAB

咩咩咩

ABBA

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

我能做的可能动作是向下移动并向右移动.

让我告诉你我被困在哪里.我正在尝试使用递归函数.从点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

你需要停下来后退一大步.

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

找到所有可能的路径

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

所以该方法需要返回一组路径:

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. */

实现这一点.

这里的课程是:

• 列出问题中的所有名词:集合,路径,坐标等.
• 创建一个代表每个类型的类型.保持简单,并确保您完全实现每种类型所需的操作.
• 现在您已经为每个名词实现了抽象,您可以开始设计使用抽象的算法,并确信它们可以正常工作.
• 记住递归的基本规则:如果可以的话,解决基本情况; 如果没有,解决较小的递归情况并组合解决方案.