为什么我的递归寻路算法行为不正确？

Question

对于一个项目，我已经程序化地生成了一系列坐标为（0，0)-->的“瓦片”； （x，y）其中（x，y）是平铺数组的最大宽度和高度。 然后用方块随机填充这个平铺数组，并给出一个入口和多个出口点。 我正在尝试创建一个算法，在给定一个起点的情况下，检查是否可以到达所有的出口点。 为此，每个瓦片包含关于其N-E-S-W相邻瓦片的数据，并且调用一个递归函数，该函数检查当前瓦片的出口，然后移动到北瓦片，然后对东，西，然后对南进行同样的操作。

下面是代码的一个（伪）示例，除了不检查出口，而是访问所有可用的瓦片并对它们进行计数（或者应该这样做）:

public class Algo
{
    public int Count(Tile tile)
    {
        tile.Visited = true;
        foreach (direction in NESW)
        {
            if(!tile.direction.IsPopulated & !tile.direction.Visited)
            {
                 return Count(tile.direction) + 1;
            }
        }
        return 0;
     }
}

IsPopulated是一个布尔值，如果平铺中填充了一个正方形，则返回true；Visited是一个布尔值，如果平铺已被访问，则返回true。 在瓦片空间周围有一个方块周长，它确保算法保持在瓦片空间的边界内

对于像这样的平铺布局:

箭头指示算法的起始点，方向和结束点（较暗的位是填充的平铺）

算法返回17而不是预期的21。

看起来，当算法到达一个不能在任何方向移动的块时，函数返回计数，而不是返回调用堆栈并重试。

我尝试过的另一个版本如预期的那样工作，然而，它没有结果，并且在方法之外变异了类的一个成员变量。

public class Algo2
{
    count = 0;
    public void Count(Tile tile)
    {
        tile.Visited = true;
        count += 1;
        foreach (direction in NESW)
        {
            if(!tile.direction.IsPopulated & !tile.direction.Visited)
            {
                 return Count(tile.direction);
            }
        }
     }
}

这将返回值21，并按预期工作。

为什么有副作用的非成果递归函数能工作，而没有副作用的成果函数却不工作？

Answer 1

寻找路径需要回溯。 即，您试图找到一条路径。 如果你到达目标，你就停下来。 如果到达死胡同或已经访问过的路径，则清除访问过的标志并返回，即将控件放回嵌套较少的递归级别。 这个级别然后尝试其他方向。

像这样的东西:

bool FindPath(Tile tile)
{
    tile.Visited = true;
    if (tile.IsTarget)
    {
        return true;
    }
    foreach (direction in NESW)
    {
        var nextTile = tile.direction;
        if(!nextTile.IsPopulated && !nextTile.Visited && FindPath(nextTile))
             return true;
        }        
    }
    // Back tracking
    tile.Visited = false;
    return false;
}

如果对findPath的初始调用返回true，则目标的路径将用visited=true块标记。

另一个选择是找到所有可能的路径到目标（或到几个目标）。 为此，您需要输出当前找到的路径，然后继续。

List<Tile> _path = new List<Tile>();

void FindAllPaths(Tile tile)
{
    tile.Visited = true;
    _path.Add(tile);
    if (tile.IsTarget)
    {
        OutputPath(_path);
        return; // If you want to go past a target to
                // find other targets, remove this `return`.
    }
    foreach (direction in NESW)
    {
        var nextTile = tile.direction;
        if(!nextTile.IsPopulated && !nextTile.Visited)
        {
             FindPath(nextTile);
        }        
    }
    // Back tracking
    tile.Visited = false;
    _path.Remove(tile);
}

不是在outputPath方法中使用带有路径块的列表，您还可以循环遍历所有块并检查visited标志。 对于大型迷宫，使用列表可能更有效。

这两种算法并不是针对所有未填充的瓦片进行计数。 但您可以计算路径平铺，从而得到路径长度。 如果您使用列表，这是列表计数，否则您也会回溯计数。 即tile.visited=true； count++；，tile.visited=false； 末尾的count--；。