时间戳

首页 > 解决方案 > 为什么我的递归寻路算法行为不正确？

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

问题描述

对于一个项目，我在程序上生成了一系列“瓦片”，其坐标为 (0,0) --> (x, y)，其中 (x,y) 是瓦片数组的最大宽度和高度。然后这个瓦片阵列随机填充正方形，并给出一个入口和多个出口点。我正在尝试创建一个算法，给定一个起点，检查是否可以到达所有出口点。为此，每个图块都包含有关其 NESW 相邻图块的数据，并调用一个递归函数来检查当前图块是否有出口，然后移动到北图块，然后对东、西和南图执行相同操作。

这是代码的（伪）示例，除了检查退出之外，它访问所有可用的图块并计算它们（或它的意思是）：

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，Visted 是布尔值，如果瓷砖已被访问，则返回 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 并按预期工作。

为什么有副作用的无结果递归函数起作用，而没有副作用的有结果函数不起作用？

标签： c#algorithmrecursion

解决方案

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

像这样的东西：

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--;结束时。

推荐阅读