迷宫求解算法

这是一个朴素的方法，可以由一个非常不聪明的机器人或者一只老鼠来实现。它只是简单地沿着当前的通道前进，直到到达一个交叉点，然后随机决定下一个要遵循的方向。尽管这种方法最终总能找到正确的解决方案，但这种算法可能非常慢。

摸墙算法，穿越迷宫最著名的规则，也称为左手规则或右手规则。如果迷宫是简单连接的，也就是说，它的所有壁都连接在一起或者连接到迷宫的外层边界，那么通过保持一只手与迷宫的一个壁接触，求解器保证不会迷路，并且如果有一个出口，将到达另一个出口；否则，该算法在穿过了与相连的墙段相邻的每个走廊至少一次的情况下将返回到入口。

另一个理解摸墙算法为什么起作用是从拓扑的角度。如果墙是连接的，那么它们可能会变形为一个环或圆。^[2] 然后摸墙算法就会减化为从头到尾走一圈。为了进一步阐述这一观点，请注意，通过将迷宫壁的连接组件组合在一起，这些组件之间的边界就是解决方案，即使有多个解决方案。

如果迷宫不是简单连接的(即，如果起点或终点位于由通道环包围的结构的中心，或者路径相互在上方和下方交叉，并且解决方案路径的这些部分被通道环包围)，摸墙算法这种方法将无法达到目的。

另一个令人担忧的问题是，在迷宫的入口处应该小心地开始沿着墙走。如果迷宫不是简单连接的，你在迷宫内的任意一点开始沿着墙壁行走，你会发现自己被困在一个单独的墙壁上，墙壁环绕着自己，没有入口或出口。如果摸墙算法开始较晚（从迷宫内部而不是从入口开始），应该尝试标记摸墙算法开始的位置。因为沿着墙走总是会把你带回到你开始的地方，如果你第二次遇到你的起点，你可以得出迷宫不是简单地连接在一起的结论，，你应该换一面还没有沿着墙走的另一面墙。参见下面的Pledge算法，作为摸墙算法的替代方法。

如果更高维的通道可以以确定性的方式投射到2D平面上，则可以在3D或更高维的迷宫中进行摸墙算法。例如，如果在3D迷宫中，可以假设“向上”通道指向西北，而“向下”通道指向东南，则可以应用标准摸墙规则。然而，与2D不同的是，这需要知道当前方向，以确定哪个方向是左边第一个还是右边第一个。

只要迷宫的入口和出口在迷宫的外壁上，不相交的迷宫可以用摸墙算法解决。然而，如果解算器从迷宫内部开始，它可能在与出口不相交的部分上，并且摸墙算法将持续围绕它们的环。Pledge算法(以埃克塞特的乔恩·质押(Jon Pledge of Exeter)命名)可以解决这个问题。^[3][4]

Pledge算法，旨在规避障碍，需要一个任意选择的方向作为优先的方向。当遇到障碍物时，一只手(比如右手) 保持沿着障碍物的状态，同时转动的角度被计数(顺时针转动是正的，逆时针转动是负的)。当求解器再次面向原始优先方向，并且转弯的角度和为0时，求解器离开障碍物并继续沿其原始方向移动。

只有当“圈数总和”和“当前航向”都为零时，手才会从墙上移开。这允许算法避免形状像大写字母“G”的陷阱。假设算法在第一面墙左转，并沿着墙绕了整整360度。一个只跟踪“当前航向”的算法会进入一个无限循环，因为它会离开最右边的下壁航向左侧，并再次进入左侧的弯曲部分。Pledge算法不会离开最右边的墙，因为“圈数之和”在该点不为零(注意360度不等于0度)。它一直沿着墙走，最后就在字母形状的下面离开朝着左方出去。

这种算法允许一个带指南针的人从任何有限的二维迷宫的任何内部点找到通往外部出口的路，而不管求解器的初始位置。然而，这种算法在做相反的操作时不起作用，即从迷宫外面的入口找到通往迷宫内某个最终目标的路。

查尔斯·皮埃尔·特雷毛发明的特雷毛算法，^[5]是一种寻找迷宫出路的有效方法，迷宫需要在地板上画线来标记路径，并且保证适用于所有具有明确通道的迷宫，^[6]但是不能保证找到最短的路径。

从交叉点开始的路径要么未被走过，要么被标记一次，要么被标记两次。该算法根据以下规则工作:

• 沿着每条路走一次做一次标记。标记需要在路径的两端可见。因此，如果它们是作为物理标记而不是作为计算机算法的一部分来存储的，那么在路径的两端应该做相同的标记。
• 切勿进入有两个标记的路径。
• 如果您到达一个没有标记的交叉点(可能除了您进入迷宫的路径上的那个)，选择一个任意的未标记路径，沿着它走并标记。
• 否则:
  • 如果你走的路只有一个标记，转身沿着那条路返回，再标记一次。尤其是这种情况应该发生在你到达死胡同的时候。
  • 如果没有，任意选择标记最少的剩余路径之一(如果可能，为零，否则为一)，沿着该路径，并标记它。

当您最终找到解决方案时，精确标记一次的路径将指示一条返回起点的路。如果没有出口，此方法将带您回到所有路径都标记两次的起点。在这种情况下，每条路径都正好向下走两次，每个方向走一次。由此产生的行走被称为双向双重追踪。^[7]

本质上，这种在19世纪发现的算法，大约一百年后才被被用作深度优先搜索。^[8][9]

死胡同填充是一种解决迷宫的算法，它填充所有的死胡同，只留下正确的方法未填充。它可以用于在纸上或计算机程序上解决迷宫，但它对一个未知迷宫中的人没有用处，因为这种方法需要同时观察整个迷宫。方法是1)找到迷宫中的所有死胡同，然后2)从每个死胡同“填充”路径，直到遇到第一个交叉点。请注意，一些通道不会成为死胡同通道的一部分，除非先移除其他死胡同。这里可以看到一段死胡同填充的视频: [1][2]。

死胡同填充不能意外地从终点“切断”起点，因为过程的每一步都保持迷宫的拓扑结构。此外，这个过程不会“太快”停止，因为最终结果不能包含任何死胡同。因此，如果在一个完美的迷宫(没有环的迷宫)上进行死胡同填充，那么只有解决方案会保留下来。如果它是在部分 辫子型迷宫(有一些环的迷宫)上完成的，那么所有可能的解决方案都会保留下来，但仅此而已。 [3]

如果给出迷宫的全知视图，一个简单的递归算法可以告诉人们如何到达终点。该算法将被赋予一个起始的X和Y值。如果X和Y值不在墙上，该方法将调用所有相邻的X和Y值，确保它以前没有使用过这些X和Y值。如果X和Y值是结束位置的值，它会将该方法的所有先前实例保存为正确的路径。下面是一个Java示例代码:

int[][] maze = new int[width][height]; // The maze
boolean[][] wasHere = new boolean[width][height];
boolean[][] correctPath = new boolean[width][height]; // The solution to the maze
int startX, startY; // Starting X and Y values of maze
int endX, endY;     // Ending X and Y values of maze

public void solveMaze() {
    maze = generateMaze(); // Create Maze (1 = path, 2 = wall)
    for (int row = 0; row < maze.length; row++)  
        // Sets boolean Arrays to default values
        for (int col = 0; col < maze[row].length; col++){
            wasHere[row][col] = false;
            correctPath[row][col] = false;
        }
    boolean b = recursiveSolve(startX, startY);
    // Will leave you with a boolean array (correctPath) 
    // with the path indicated by true values.
    // If b is false, there is no solution to the maze
}
public boolean recursiveSolve(int x, int y) {
    if (x == endX && y == endY) return true; // If you reached the end
    if (maze[x][y] == 2 || wasHere[x][y]) return false;  
    // If you are on a wall or already were here
    wasHere[x][y] = true;
    if (x != 0) // Checks if not on left edge
        if (recursiveSolve(x-1, y)) { // Recalls method one to the left
            correctPath[x][y] = true; // Sets that path value to true;
            return true;
        }
    if (x != width - 1) // Checks if not on right edge
        if (recursiveSolve(x+1, y)) { // Recalls method one to the right
            correctPath[x][y] = true;
            return true;
        }
    if (y != 0)  // Checks if not on top edge
        if (recursiveSolve(x, y-1)) { // Recalls method one up
            correctPath[x][y] = true;
            return true;
        }
    if (y != height - 1) // Checks if not on bottom edge
        if (recursiveSolve(x, y+1)) { // Recalls method one down
            correctPath[x][y] = true;
            return true;
        }
    return false;
}

迷宫路由算法 ^[10] 是一种低开销的方法，可以在迷宫的任意两个位置之间找到路径。该算法最初是针对芯片多处理器(CMPs)领域提出的，并保证适用于任何基于网格的迷宫。除了在网格(迷宫)的两个位置之间寻找路径之外，该算法还可以检测源和目的地之间何时没有路径。此外，无论迷宫的大小如何，该算法都将由事先不知道迷宫并具有固定记忆复杂性的内部旅行者使用；总共需要4个变量来找到路径和检测不可到达的位置。尽管如此，算法并不能用来寻找最短路径。

迷宫路由算法使用曼哈顿距离的概念，并且依赖于网格的属性，当从一个位置移动到任意4个相邻位置时，网格的距离精确地增加/减少1。这是伪代码，没有检测不可到达位置的能力。

Point src, dst;// Source and destination coordinates
// cur also indicates the coordinates of the current location
int MD_best = MD(src, dst);// It stores the closest MD we ever had to dst
// A productive path is the one that makes our MD to dst smaller
while(cur != dst){
    if(there exists a productive path){
        Take the productive path;
    }else{
        MD_best = MD(cur, dst);
        Imagine a line between cur and dst;
        Take the first path in the left/right of the line;// The left/right selection affects the following hand rule
        while(MD(cur, dst) != MD_best || there does not exist a productive path){
            Follow the right-hand/left-hand rule;// The opposite of the selected side of the line
    }
}

当迷宫有多个解时，求解器可能希望找到从开始到结束的最短路径。有几种算法可以找到最短路径，其中大多数来自图论。一种这样的算法通过实现广度优先搜索来找到最短路径，而另一种算法，A*算法，使用启发式技术。广度优先搜索算法使用队列从开始到到达终点以递增的距离顺序访问单元格。每个被访问的单元都需要记录它与起点的距离，或者哪个更靠近开始的相邻单元导致它被添加到队列中。找到终点位置后，沿着单元格的路径向后回到起点，从而得到最短的路径。最简单形式的广度优先搜索有其局限性，比如在加权图中找到最短路径时。