为什么递归函数返回意外结果?

亚历克斯

我的程序是:

var maze = MazeFactory.FromPattern(Patterns.Maze3, Patterns.WallSymbol);
var a = maze.GetElementAt(0, 1);
var b = maze.GetElementAt(12, 0);

var printer = new PathPrinter(ConsoleColor.Yellow, ConsoleColor.Gray, ConsoleColor.Black);

Console.WriteLine("Maze");
printer.Print(maze, Path.Empty, Console.CursorLeft, Console.CursorTop);

var ab = new PathFinder(maze, a, b).GetPaths();
var abPath = ab.OrderBy(p => p.Elements.Count()).First();
Console.WriteLine("A -> B");
printer.Print(maze, abPath, Console.CursorLeft, Console.CursorTop);

var ba = new PathFinder(maze, b, a).GetPaths();
var baPath = ba.OrderBy(p => p.Elements.Count()).First();
Console.WriteLine("B -> A");
printer.Print(maze, baPath, Console.CursorLeft, Console.CursorTop);

输出为:

程序输出

我希望PathFinder.GetPaths()返回一个Paths的集合,以便我可以选择最短的一个,但是该集合仅包含一个元素。

欢迎回答任何问题。

  • 这是为什么?
  • 为什么“ a到b”的路径与“ b到a”的路径不同?
  • 为什么“ a to b”路这么长?
  • 如何使两条路径最短且相同?

注意:我不是在寻找一种新的解决方案,只是为了解决这个问题。

详细资料

我有一堂课MazeElement

class MazeElement
{
    public bool IsPass { get; }
    public int X { get; }
    public int Y { get; }

    public MazeElement(int x, int y, bool isPass) => (X, Y, IsPass) = (x, y, isPass);
}

MazeElement实例可以形成Maze

class Maze
{
    public IReadOnlyList<IReadOnlyList<MazeElement>> Elements { get; }
    public int MaxY { get; }
    public int MaxX { get; }

    public Maze(MazeElement[][] elements) =>
        (Elements, MaxY, MaxX) =
            (elements, elements.Length - 1, elements[0].Length - 1);

    public MazeElement GetElementAt(int x, int y) =>
        0 <= x && x <= MaxX && 0 <= y && y <= MaxY ?
        Elements[y][x] :
        null;
}

和一个Path

class Path
{
    public IEnumerable<MazeElement> Elements { get; }
    public bool ReachedDestination { get; }

    public static Path Empty => new Path(new MazeElement[0], false);

    private Path(IEnumerable<MazeElement> elements, bool reachedDestination) => (Elements, ReachedDestination) = (elements, reachedDestination);

    public Path Continued(MazeElement next, bool reachedDestination) => new Path(new List<MazeElement>(Elements) { next }, reachedDestination);

    public static Path FromStart(MazeElement start) => new Path(new[] { start }, false);
}

我有一个MazeFactory可以Maze从一组strings创建一个

static class MazeFactory
{
    public static Maze FromPattern(IEnumerable<string> pattern, char wallSymbol) =>
        new Maze(pattern.Select((line, y) => line.Select((c, x) => new MazeElement(x, y, c != wallSymbol)).ToArray()).ToArray());
}

和一些这样的集合:

static class Patterns
{
    public static readonly char WallSymbol = '#';

    public static readonly IReadOnlyList<string> Maze1 = new[]
        {
            "#########################",
            "                      ###",
            "##################### # #",
            "#                     # #",
            "# ##################### #",
            "# #                     #",
            "# ##################### #",
            "#                       #",
            "####################### #"
        };
    public static readonly IReadOnlyList<string> Maze2 = new[]
        {
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         "
        };
    public static readonly IReadOnlyList<string> Maze3 = new[]
        {
            "############ ############",
            "                      ###",
            "######## ############ # #",
            "#                     # #",
            "# ########## ######## # #",
            "# #                     #",
            "# ###### ############ # #",
            "#                       #",
            "####################### #"
        };
}

为了显示结果,我有一个PathPrinter

class PathPrinter
{
    private static readonly string mazeSymbol = "█";
    private static readonly string pathSymbol = "*";

    private readonly ConsoleColor wallColor;
    private readonly ConsoleColor passColor;
    private readonly ConsoleColor pathColor;

    public PathPrinter(ConsoleColor wallColor, ConsoleColor passColor, ConsoleColor pathColor) =>
        (this.wallColor, this.passColor, this.pathColor) = (wallColor, passColor, pathColor);

    public void Print(Maze maze, Path path, int x = -1, int y = -1)
    {
        x = x == -1 ? Console.CursorLeft : x;
        y = y == -1 ? Console.CursorTop : y;

        foreach (var line in maze.Elements)
            foreach (var e in line)
            {
                Console.SetCursorPosition(e.X + x, e.Y + y);
                Console.ForegroundColor = e.IsPass ? passColor : wallColor;
                Console.Write(mazeSymbol);
            }
        Console.ForegroundColor = pathColor;
        foreach (var e in path.Elements)
        {
            Console.SetCursorPosition(e.X + x, e.Y + y);
            Console.BackgroundColor = e.IsPass ? passColor : wallColor;
            Console.Write(pathSymbol);
        }
        Console.SetCursorPosition(0, maze.MaxY + y + 1);
        Console.ResetColor();
    }
}

最后,我要在PathFinder中找到路径Maze

class PathFinder
{
    private readonly Maze maze;
    private readonly MazeElement start;
    private readonly MazeElement end;
    private readonly Dictionary<MazeElement, bool> elementIsChecked;

    public PathFinder(Maze maze, MazeElement start, MazeElement end) =>
        (this.maze, this.start, this.end, elementIsChecked) =
        (maze, start, end, maze.Elements.SelectMany(i => i).ToDictionary(i => i, i => false));

    public Path[] GetPaths() => FindPath(Path.FromStart(start)).ToArray();

    private IEnumerable<Path> FindPath(Path path) =>
        GetContinuations(path).Where(next => next != null)
                              .SelectMany(next => next.ReachedDestination ? new[] { next } : FindPath(next));

    private IEnumerable<Path> GetContinuations(Path path)
    {
        var e = path.Elements.LastOrDefault();

        if (e == null)
            return new Path[] { null };

        return new[]
        {
            maze.GetElementAt(e.X, e.Y - 1),
            maze.GetElementAt(e.X, e.Y + 1),
            maze.GetElementAt(e.X - 1, e.Y),
            maze.GetElementAt(e.X + 1, e.Y)
        }
        .Where(i => i != null)
        .Select(i => GetContinuedPath(path, i));
    }

    private Path GetContinuedPath(Path path, MazeElement e)
    {
        if (e == null || elementIsChecked[e])
            return null;

        elementIsChecked[e] = true;

        if (e.IsPass)
            return path.Continued(e, e == end);

        return null;
    }
}
共生体

您正在函数FindPath中使用“深度优先”搜索,还将您遇到的所有点都标记为elementIsChecked,这是您第一次遇到它们时。标记后,您将不再关注这些点。

但是,由于您使用的是“深度优先”搜索,因此在完成长路径时,最终可能会遇到一个问题。然后,将其标记为elementIsChecked之后,其他路径将不再使用该点。长路径最终会阻塞随后的短路径。

之所以从A-> B开始走很长的路,是因为您在PathFinder.GetContinuations函数中将这些方向放在了优先位置:上,下,左,右。在(8,1),它选择向下,因为right的优先级较低。(使用条件断点可以节省很多麻烦)

因此,您实际上无法再次访问的唯一点就是路径上已经存在的点。一个简单的解决方法是摆脱PathFinder.elementIsChecked并在PathFinder.GetContinuedPath中替换:

if (e == null || elementIsChecked[e])

if (e == null || path.Elements.Contains(e))

然后,每条路径一直持续到阻塞自身为止。它效率不高,但是我想这很容易解决。

您可能应该使用“广度优先搜索”,并以相同的速率向所有可能的方向扩展,例如池塘中的涟漪,并在到达目的地后停止扩展

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章