寻找所有可能的路径 [英] Finding all possible paths

问题描述

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

I have a problem to find all possible paths.

a a b

b a a a

a b b a

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

Traveling from starting point at 0,0 to end point at 2,3. I need to get all possible paths.

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

Possible moves that I can do are moving down and moving right.

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

Let me tell you where I am stuck. I am trying to do with a recursive function . Starting with point at 0,0 and moving towards right whenever I can and moving down only when I must.

我的递归函数:

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;

        }

不确定我的递归移动函数.还是需要扩展一下.我不知道我应该如何实施.

Not sure about my recursive move function. Still need to expand it . I am not getting exactly how I should implement .

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

I am able to traverse upto the corner node using that move method but I need that function to retrace back whenever all possible moves from the corner top right point(0,4) is reached.

推荐答案

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

You need to stop and take a big step back.

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

The first step should be coming up with the signature of the method. What is the problem statement?

找出所有可能的路径

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

Not mentioned: starting from a particular coordinate.

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

So the method needs to return a set of paths:

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

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

OK, now we're getting somewhere; now it is clear what we need. We need a set of things, and we need a path, and we need coordinates.

什么是坐标?一对整数:

What's a coordinate? a pair of integers:

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

完成.所以弹出堆栈；什么是路径?路径可以是空的，也可以是第一步，然后是路径:

Done. So pop the stack; what is a path? A path can be empty, or it can be a first step followed by a path:

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.您将需要进行所有项目"和将这个集合与另一个联合以产生第三个"的操作.确保集合不可变.当你向它添加新项目时，你不想改变它；你想要一套不同的.和加1的时候不把3变成4的方法一样；3和4是不同的数字.

Now you implement Set<T>. You will need to have the operations "all items" and "union this set with another to produce a third". Make sure that sets are immutable. You don't want to change a set when you add new items to it; you want a different set. The same way you don't change 3 into 4 when you add 1; 3 and 4 are different numbers.

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

Now you have all the tools you need to actually solve the problem; now you can implement

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

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

So how does this work? Remember that all recursive functions have the same form:

• 解决小问题
• 如果我们不是在一个微不足道的案例中，请将问题缩小到一个较小的案例中，递归解决它，然后组合解决方案.

那么什么是微不足道的情况?

So what is the trivial case?

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

实施那个.

这里的教训是:

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

这篇关于寻找所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！