1

我已经编程了大约五年了，我在创建动态迷宫时没有遇到任何问题。但是现在谈到递归回溯，我完全不知道从哪里开始。我已经阅读了很多教程、主题和一些算法维基（dijkstra 的算法），它们对我来说毫无意义。

我知道基本递归是如何工作的，但我根本无法理解如果不（在我看来）存储先前搜索的路径或者如果正在跟踪的路径突然分成两部分会发生什么情况下递归回溯是如何可能的。

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

这是它在运行时的样子（并且只有在没有从起始方块（红色）到左上角绿色方块的有效路径时才会显示错误消息：

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;
    }

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

4

2 回答 2

1

已经两年了，这个帖子没有得到答案。我当时正在寻找的答案是一个让我意识到递归回溯是如何工作的解释。我很难弄清楚该方法如何知道它以前的位置，似乎没有存储访问区域以防止一遍又一遍地走同样的路（无限循环）。但是一旦我意识到它是如何工作的，我立刻就想出了如何编写代码。

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

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

如果您仍然无法理解，请想一想您现在是如何被困在迷宫中的。你有一个超能力，它不是飞行，而是克隆。所以你继续前进，直到路径分裂。这是当您克隆自己并将他发送到您的位置时，而原来的您在克隆找到出口或遇到死胡同之前不会移动，这时克隆会传送回您并分享他的信息。但如果你的克隆人也跑进了一条分裂的道路，他会克隆自己并等待他的克隆人带着迷宫的知识回来。而且你的克隆的克隆也可以根据路径分裂的次数产生无限数量的克隆。最终，所有综合知识都会回到您身边。那时你就会确切地知道在哪里可以找到迷宫的出口。

于 2016-05-10T13:48:51.140 回答
0

你的问题太广泛了。您需要发布一个特定的问题。您似乎正在尝试完成家庭作业。

您的问题需要调试，这需要有人运行您的代码。您最好只包含一个指向您的代码的链接，以便有人可以在他们想花时间执行此操作时运行它。

您可能需要一个类级别的属性来存储最快的路径，因为您已经返回了一个布尔值，或者您可以使用一个 out 变量。您传递给递归方法的数组将是您存储我假设的所有先前检查的索引的地方。

于 2014-06-25T16:56:53.003 回答