跳转到内容

解迷宮演算法

出自维基百科，自由个百科全书
一个机械人垃拉行紧一个木造个迷宫，伊部电脑里面应该有个个上下功效个解迷宫演算法。

解迷宮演算法(英文：maze solving algorithm）是一类个演算法，顾名思义垃啥相关领域个研究者写来教啥电脑行迷宫个。解迷宫演算法有分好多种，而且各有强项，侬啥演算法当中有啲系预了部电脑是勿知个迷宫个样，但是又有啥系专为「部电脑经已鸟瞰式看到了所有个迷宫」个情况而设个。箇个啥演算法垃拉机械人学上好有用－帮到手教啥机械人探索伊拉四周围个环境。

顺带一提，解迷宫演算法跟图论（graph theory）有相关：勿包含任何循环（loop）垃门个迷宫系所谓慨「简单个连住」（simply connected）或者「完美」迷宫，相当于图论当中个树状图（tree graph）－如果将行一个完美迷宫哀阵个可能路线拉开，会得出一个好似图论里向所讲慨树状图图个物质。

随机老鼠演算法

[编辑]

随机老鼠演算法（random mouse algorithm）是最简单粗糙哀种解迷宫演算法，步骤如下：

  1. 沿住哀条路线一路直走，直至撞到一个交叉口。
  2. 门个交叉口咿個随机啖拣个方向转过去。
  3. 再重複上述嘅程序。

事实上，侬个演算法实会揾到出口（假设个迷宫真是有出口个话），但是用箇个方法行迷宫慢得好交关，衰实际应用上好难说服人用呢个演算法來解迷宫。

跟墙行演算法

[编辑]
用跟墙行演算法解一个迷宫个路线图

跟墙行演算法（wall follower）是最出名咿种解迷宫演算法，又有叫做左手法则（left-hand rule）或者右手法则（right-hand rule）。如果个迷宫是简单连连住个话，伊啥墙全部都是相连或者连住个迷宫个外围界限，个个人如果将伊其中一只手一路掂住个迷宫埲墙一路行个话实勿会荡失路，实会尋到个出口（假设个迷宫真是有个出口个话）。而如果个迷宫勿有出口，伊会去匀个迷宫个每条走廊之后只手会回到去开始垃点垃拉。

總結来讲，跟墙行演算法个做法如下：

  1. 将随便一只手掂住个迷宫埲墙。
  2. 一路走一路手要掂住埲墙－勿可以中途放手。
  3. 如果迷宫是简单连住，最后会出口走到去。
  4. 如果最后只手回到去原先个位置，就表示个迷宫勿是简单个连住。

為啥解決

[编辑]

由拓樸學个角度分析可以了解跟牆行演算法為啥掂。拉垃定义上，「简单个连住」个迷宫啥墙是全部都相连住，即是勿循环路，所以拉垃一个个迷宫门，每当走迷宫哀个人撞到分叉路，哀条分​​叉路净是有得再分叉或者做倔头路。即是表示，如果将个人个可能路线画做一幅树状图，咿幅树状图勿会有任何互相交叉个分枝，而且个迷宫有得变形做一个圆圈。即是讲靠跟墙行演算法解一个迷宫基本上等同沿住一个圆圈由起点行到去终点个样子。

弱点

[编辑]

当然，跟墙行演算法都有伊个弱点：首先，上述讲了呢柞物质是以「迷宫是个简单个连住」做前题，如果个迷宫勿是简单个连住（例如入口或是出口是个迷宫中心，拨循环路围住；又或是啥路彼此之间会垃对方上面或者下面去，而正确路线个衰部份拨循环路围住），跟墙行演算法就勿通会行；另一方面，如果一个人门行行吓到了半路先至开始用跟墙行演算法，而个迷宫​​勿是简单连住，伊可能会永世沿住一列循环个墙打转。如果一个人行到半路先开始用跟墙行演算法，伊可以搵个方法记低伊开始用跟墙行演算法哀点，而因为跟墙行演算法如果去勿到出口只手是会走返到去起点，所以起码会帮到伊知道个迷宫是简单连住了。

Pledge 演算法

[编辑]
左手边：一个斋向左行个人拨个迷宫难到；                            右手边：用 Pledge 演算法成功解到个迷宫。

正如刚才提了，跟墙行演算法有漏洞：例如是个起点喺个迷宫里面，而个迷宫​​唔系简单连住样子，个起点可能会垃正一个啥墙同个出口勿连接个地点，搞到用跟墙行演算法个人会永世垃个迷宫里面打转。但是 Pledge 演算法（Pledge algorithm；个名取自 Jon Pledge）晓解决箇个问题。

Pledge 演算法是为了要能够避开障碍物而设计，需要走迷宫哀个人或者拨指示哀个人随便拣个方向来做前进方向。当跟箇个演算法行迷宫哀个人撞到一旧障碍物那时，伊会转方向，同时会一只手会掂住旧嘢一路转，个人会数住伊转了个角度（例如顺时针当正，逆时针当负），并且时刻啖尝试将个总共转了个角变做0 度（例如系如果伊转了左，而行了一格就撞到可以转右个地方，伊会即刻转右）。当行迷宫哀个人转到面向回伊原本个前进方向，总共转了个角（图入面个「S」）会是0 度，而走迷宫哀个人会离开旧障碍物，继续向住伊原本个方向走。箇个个演算法能够帮到行迷宫嗰个人克服好似拉丁字母「G」啖形慨陷阱。

一个只是留意住自己目前方向个演算法会陷入一个无穷个循环：用回「G」形迷宫做例子，一个只是晓记得自己目前方向（图入面个「H」）个演算法会令到行迷宫哀个人垃拉去到最右下角哀埲墙转左，并且走返入去左手边。 Pledge 演算法勿会犯箇个错，因为垃最右下角哀埲墙个一点「总共转咗慨角」勿是0 度（360 度勿当是0 度），所以別人会沿住啥墙一路行回到去左下角哀一个出口。

Pledge 演算法帮到一个攞住指南针个人由一个两维慨迷宫里向隨一点行到去个迷宫外向－无论伊个起点垃边都好。但是箇个演算法做勿到相​​反个东西－勿能够帮个人由迷宫外向走去一个身处于迷宫内部个目的地。

Trémaux 演算法

[编辑]
用 Trémaux 演算法解一个迷宮。

Trémaux 演算法（Trémaux algorithm）是由法国数学家 Charles Pierre Trémaux 发明，是一种用到垃拉地下画线个解决迷宫方法，只要个迷宫有清楚定义了个通道就包保有效。箇种做法会将每条通道分做「未去过」、「去过一次」搭仔「去过两次」三种。并且会跟住以下个规则运行：

  • 每次第一次行经一条路哀阵要做记号，记号要垃条路个两端都看得到。所以如果个记号是物理性（而勿用电脑记住），记号要门条路慨两端都留低；
  • 勿好走入去做了两个记号个路里向；
  • 搿有三个可能性：
  • 如果走到去一个啥记号都勿哀垃交叉位，就是但拣一条路行，要跟住伊走，并且做好记号；
    • 如果走入去哀条路得一个记号，就回转头，再做多个记号－呢个情况表示前面是倔头路；
    • 再如果勿是来读，门净低行得个路哀度拣最少哀条记号，跟住伊走，并且记号做好了。

垃拉用箇个演算法走去出口之后，跟住啥得一个记号个路行就可以一路行返去起点。如果迷宫根本勿出口，箇个方法会带行迷宫哀个人返返去起点，而且每条路都会有两个记号－垃拉后者箇个情况下，每条路都行过两次，而两个方向各一次。呢个行路过程拨人称之为双向双重跟踪（bidirectional double-tracing）。

倔頭路充填法

[编辑]

倔头路充填法（dead-end filling）是一个演算法，做法如下：将个迷宫里向箇啥倔头路 全部揾了；再用记号填满了啥倔头路，一路填到第一个交叉位嗰度；就可以好容易看到了全个迷宫里向有边啥路。箇种做法可以攞来解一个完全已知个迷宫，例如系喺纸上面玩慨迷宫游戏，但是因为伊要求解迷宫嗰个人能够由上高鸟瞰睇到嗮成个迷宫，所以帮唔到手解啥未知个迷宫。

倔头路充填法个好处，无论个迷宫是否完美（勿循环）个都好，箇个演算法都会解到个迷宫：箇个做法勿会擝走啥勿是倔头个路，所以如果个迷宫是完美个，用了倔头路充填法之后只会净低条正确路线；而如果个迷宫是勿完美（有循环）个，用了倔头路充填法之后会净低所有个可行路线。

递回演算法

[编辑]

假如解迷宫哀个人知道了所有个迷宫个路线（例如纸上面玩个迷宫游戏），一个简单个递回演算法就帮到个人由起点一路行到终点。演算法会接收一个起始个值：X 搭仔 Y。如果X 跟Y 个值勿垃該一埲墙上面，演算法会记回所有周围邻近个X 搭仔 Y 值，确保自己勿会回用啥X 跟Y 值，而如果伊揾到终点个X搭仔Y 值，伊会以走过衰啥路个X 跟Y 值个型式记低条正确路线。以下是箇個演算法用 Java 程式语言写出来个样本：

int[][] maze = new int[width][height]; // 帮个迷宫每一点设回个 X 跟 Y 值代表伊方位－箇个演算法假设了个人知道了迷宫是啥个样子。
boolean[][] wasHere = new boolean[width][height];
boolean[][] correctPath = new boolean[width][height]; // 矩阵设回了，等阵用来记低正确路线。
int startX, startY; // 设两个变数做起点个 X 跟 Y 值。
int endX, endY; // 设两个变数做终点个 X 跟 Y 值。

public void solveMaze() {
   maze = generateMaze(); // 整个迷宫出来，「1」代表路，「2」代表墙。
   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);

// 会得出一个Boolean个排列
// 啥「真」个值会用来代表条正确路线。
//如果 b 是假，就代表个迷宫根本是勿可能解到个。
}

public boolean recursiveSolve(int x, int y) {
   if (x == endX && y == endY) return true; // 如果终点到了,拨回个「真」值出去。 ...
   if (maze[x][y] == 2 || wasHere[x][y]) return false;  
// 如果撞到墙或者经已来过箇一点，拨回个「假」值出去。...
   wasHere[x][y] = true;
   if (x != 0) // 检查是最左个边界到了。
      if (recursiveSolve(x-1, y)) {
         correctPath[x][y] = true;
         return true;
      }
   if (x != width - 1) // 检查是最右个边界到了。
      if (recursiveSolve(x+1, y)) {
         correctPath[x][y] = true;
         return true;
      }
   if (y != 0)  // 检查是最底个边界到了。
      if (recursiveSolve(x, y-1)) {
         correctPath[x][y] = true;
         return true;
      }
   if (y != height - 1) // 检查是最顶个边界到了。
      if (recursiveSolve(x, y+1)) {
         correctPath[x][y] = true;
         return true;
      }
   return false;
}

剷起迷宮演算法

[编辑]
两点之间个空间可以用格仔代表，绿色线是最短距离，但是现实个，好多时实际应用衰度都勿得由A 点直线走去B 点－好似是垃曼哈顿揸车寻食个差头司机个处境

铲起迷宫演算法（maze-routing algorithm）是一种用来揾出一个迷宫里向隨两点之间个路线个方法。呢个演算法识得看到哀两点之间是否真是有路通到，而且无论个迷宫几大都好，伊都帮到个由迷宫内部开始走、记忆力有限、兼事前完全勿知道个迷宫是啥样子个个体成功解到个迷宫，只是要求走迷宫哀个人记住4 个变数就可以揾到条路线出来。但是箇个演算法勿保证揾到最短嘅路線出嚟。

铲起迷宫演算法用了曼哈顿距离（Mahattan distance；简称「MD」）个概念。箇个概念指个是两点之间个空间可以用格仔代表，而假设一个个体净是可以沿住啥格仔个边线走，垃隨两点之间穿梭都会有好多条「最短路线」，箇啥路线个长度就是以所谓个MD 计。以下是一段虚拟码：

Point src, dst;// 起点搭仔终点个坐标
// 「cur」表示该歇个位置。
int MD_best = MD(src, dst);// 储起走迷宫哀个人搭目的地之间个最短 MD。
// 一条好个路线就是一条能够令到 MD 最细化个路线。
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;
        while(MD(cur, dst) != MD_best || there does not exist a productive path) {
            Follow the right-hand/left-hand rule; // 用回左右手法则。
    }
}

更多专题页面

[编辑]

参考资料

[编辑]

馱

[编辑]
取自“https://wuu.wikipedia.org/w/index.php?title=解迷宮演算法&oldid=305289”