c# - 在随机生成的迷宫上使用递归回溯

Question

我已经从事编程工作大约五年了，我可以毫不费力地创建一个动态迷宫。但是现在谈到递归回溯，我完全不知道从哪里开始。我已经阅读了很多教程、主题和一些 algorhytm wiki(dijkstra 的 algorhytm)，它们对我来说毫无意义。

我知道基本递归是如何工作的，但我根本无法开始理解递归回溯是如何在没有(在我看来)存储以前搜索过的路径或者如果正在跟踪的路径突然一分为二时会发生什么的.

我的程序是这样工作的:迷宫由 484 个面板组成(名为 mazeTiles 的 Panel[] 数组)。有 22 行，每行有 22 个面板。黑色面板背景是墙壁，白色面板背景是可穿越的。

这是它在运行时的样子(以及只有在没有从起始方 block (红色)到左上角绿色方 block 的有效路径时才会显示的错误消息:

http://postimg.org/image/6c7wgxtz1/

显示的错误消息是“迷宫无法解决”，即使它显然可以解决。此错误消息位于 Button2_Click 方法中。

下面是我从教程中获取(并修改)的代码，问题肯定出在方法中，但我不知道如何解决这个问题。

    private void button2_Click(object sender, EventArgs e)
    {
        int startPosition = 0;

        for (int i = 0; i < mazeTiles.Length; i++)
        {
            if (mazeTiles[i].BackColor == Color.Red)
            {
                startPosition = i;
            }
        }

        bool[] alreadySearched = new bool[484];

        if (!solveMaze(startPosition, alreadySearched))
            MessageBox.Show("Maze can not be solved.");
    }

    private bool solveMaze(int position, bool[] alreadySearched)
    {
        bool correctPath = false;

        //should the computer check this tile
        bool shouldCheck = true;

        //Check for out of boundaries
        if (position >= mazeTiles.Length || position < 0 )
            shouldCheck = false;
        else
        {
            //Check if at finish, not (0,0 and colored light blue)
            if (mazeTiles[position].BackColor == Color.Green)
            {
                correctPath = true;
                shouldCheck = false;
            }
            //Check for a wall
            if (mazeTiles[position].BackColor == Color.Black)
                shouldCheck = false;
            //Check if previously searched
            if (alreadySearched[position])
                shouldCheck = false;
        }
        //Search the Tile
        if (shouldCheck)
        {
            //mark tile as searched
            alreadySearched[position] = true;
            //Check right tile
            correctPath = correctPath || solveMaze(position + 1, alreadySearched);
            //Check down tile
            correctPath = correctPath || solveMaze(position + 22, alreadySearched);
            //check left tile
            correctPath = correctPath || solveMaze(position - 1, alreadySearched);
            //check up tile
            correctPath = correctPath || solveMaze(position - 22, alreadySearched);
        }

        //make correct path gray
        if (correctPath)
            mazeTiles[position].BackColor = Color.Gray;

        return correctPath;
    }

我需要找到并存储从红色方 block 到绿色方 block 的所有路径或最快的路径(并且只标记最快的路径)。绿色方 block 是静态的，但红色方 block 和整个迷宫是随机生成的。

Answer 1

已经两年了，这篇文章没有得到回复。我当时正在寻找的答案是一种解释，它让我意识到递归回溯是如何工作的。我在弄清楚该方法如何知道它之前在哪里时遇到了很多麻烦，似乎没有存储访问过的区域以防止一遍又一遍地走同样的路(无限循环)。但是一旦我意识到它是如何工作的，我立刻就想出了如何编写代码。

因此，如果有人在想同样的事情时偶然发现了这一点。理解递归回溯的一个简单方法是理解递归方法的工作原理。递归方法不断地调用自己，直到找到正确的答案。递归回溯不断在自身内部调用自身以找到正确的答案。所以很多基本的递归方法取代了 itelf，所以通常一次只有一个它的实例，而递归回溯方法经常堆叠在一起。

解决难题时，该方法不断在自身内部一遍又一遍地调用自身(初始风格)，同时不断朝一个方向迈出一步，直到在该方向上没有更多的步骤。那是该实例结束并且调用它的前一个实例继续运行的时候。一旦该实例结束，之前的实例将继续(并且它可以自己进行一千次启动)。

如果您仍然无法理解，请想一想您现在是如何被困在迷宫中的。你有一个超能力，它不是飞行，而是克隆。所以你继续前进，直到路径分开。这是当你克隆自己并让他代替你上路时，而原来的你不会移动直到克隆人找到导出或走到死胡同，那时克隆人会传送回你并分享他的信息。但是，如果您的克隆人也遇到了一条分路，他就会克隆自己并等待他的克隆人带着迷宫的知识返回。并且你的克隆体的那个克隆体也可以根据路径 split 的次数来制造无限数量的克隆体。最终，所有这些组合的知识都会返回给您。那时您就会确切地知道在哪里可以找到迷宫的导出。