1701742294
奥尔算法
1701742295
1701742296
为了解释清楚这种算法，最好假定你从一个节点开始。如果你的出发点不是一个节点，那就走到最近的一个节点处。如果不知道哪个方向可通向最近的节点，随便选一个方向，走到你遇到的第一个结点。这个点就是你的出发点。
1701742297
1701742298
从出发点开始，探索交汇于此的每一个枝。在进入每一个枝的时候，在入口处放一块鹅卵石。对每一个枝的探索仅限于到达下一个节点，然后在这个枝的终点处放一块鹅卵石，原路返回出发点。
1701742299
1701742300
如果遇到死胡同，你就做一个标记。一旦对一个枝做了死胡同的标记，以后就可以忽略这个枝了。做标记的方法可以是在死胡同的入口处拉一条封锁线，或者摆上一排鹅卵石。
1701742301
1701742302
如果某条路转了一圈又回到最初的节点，那么你也要把它标记为死胡同。这种路对你也是无用的。
1701742303
1701742304
你的兴趣在于确定那些通向有新枝的新节点的枝。在探索的第一个阶段结束之后，每一条有可能通向终点的潜在路线都已经做了记号——路的两端各有一块鹅卵石，而你重新回到了出发点。
1701742305
1701742306
下一步，探索的深度达到两个节点。沿着每一条非死胡同的枝走到新节点，从这个新节点出发探索每一条由此辐射出去的枝，探索方法照旧。在最初的那个枝的两端各加一块鹅卵石（此时，这个枝的两端各有两块鹅卵石），对于新探索的第二级的枝，两端各放一块鹅卵石。这个办法可以防止你找不到返回出发点的路，可返回出发点的路有一个特点：路口处的鹅卵石比其他路口多一块。和第一阶段一样，对死胡同和兜圈子的路做标记，予以排除。如果一个枝通向以前探索过的节点（这个节点至少有一块作为记号的鹅卵石），在这个枝的两端也做标记，予以排除。
1701742307
1701742308
探索的第三步，深度达到距出发点三个节点处，在每一个探索过的枝的两端各加一块鹅卵石。依照以上规则不断推进探索步骤，直到发现终点、入口或者其他想找的东西。
1701742309
1701742310
奥尔算法可以确定通向终点的最短路线（所谓最短是指枝的数量最少，而非物理距离最短）。当然，你的探索过程不是最简的。但是，如果最短路线需要经过五个节点，你一定可以在探索的第五个阶段发现它，而且可以确保它是最短的。
1701742311
1701742312
奥尔算法的效率同样低得可怜。它不是直接对准正确的路线，而是检查所有可能的路线。这是必不可少的，因为任何一条路线都可能是正确的。
1701742313
1701742314
推理的迷宫：悖论、谜题及知识的脆弱性 [:1701739730]
1701742315
迷宫的NP完全性
1701742316
1701742317
下面考虑一个问题。这个问题也许可以称为无限迷宫问题。你位于E点（E点代表入口，不过这个点和其他点一样，淹没于无边无际的无限迷宫中），你在寻找G点，这个点代表终点，终点可以是迷宫中的任意点。你不知道G点在哪儿，无法在地图上对G点定位（根本就没有地图）。你确信，如果你走到了终点，便可以认出它来，因为终点处有一个已知的标记。根据以上对迷宫的明确规定提出我们的问题：“连接E点和G点的简单路线是哪条？”
1701742318
1701742319
所谓的“简单路线”，是指不出现自身交叉的路线。如果路线自身交叉，就是在兜圈子。兜圈子总是不必要的，而简单路线要求的成本较低。简单路线可能不止一条。如果存在多条简单路线，其中最短的一条更受欢迎。但是，对于一条简单路线是否具备“最短”这个优点，你并不是很在乎。毕竟，探索这个无限迷宫是一个令人恐惧的任务，几乎任何一条能通向G点的路线都是令人满意的。
1701742320
1701742321
1701742322
1701742323
1701742324
另一个问题与无限迷宫问题密切相关，这个问题可以称为“迷宫存在性问题”：是否存在从E点通向G点的简单路线？
1701742325
1701742326
我们来看一下为什么这个问题比较简单。一旦无限迷宫问题得到了答案（具体指明了一条路线），这个答案本身就回答了存在性问题：简单路线确实是存在的。即使它无法具体地指明一条路线，在某些情况下，仍有可能表明简单路线是存在的。我们很自然地认为，一个只需回答“是—否”的问题要比一个也许需要为一个长达数十亿个枝的路线不厌其烦地定向的问题简单。
1701742327
1701742328
只有怀疑主义者才会问存在性问题。大多数迷宫探索者有一个基本观念：所有的点都是以某种方式连在一起的，从此处总可以走到彼处。尽管路线可能曲折而漫长，但是它毕竟是存在的。然而，实情未必如此。有这样一种可能：迷宫是骗人的，它只有问题却没有答案。也许所有道路构成了两个互相缠绕但彼此分离的网络，从一个部分无法到达另一个部分。即使假定整个迷宫属于一个单一网络，对此我们也永远无法证明，因为我们的知识仅限于迷宫的局部。在一条具体的路线被发现并得到证实以前，我们总是可以设想通向目的地的路并不存在。
1701742329
1701742330
这个“存在性问题”属于NP完全问题的一种，被称为“最长路径”问题。NP完全问题以“困难”著称，但是这个存在性问题有时不难回答。例如，当G点碰巧距离E点只有一个枝时，随机的探索几乎会立刻发现G点，存在性问题和无限迷宫问题同时得到解决。
1701742331
1701742332
这很正常。一个一般性问题的特例有可能非常简单。我们要寻找的是解决存在性问题的成体系的通用方法，这对于最简单的迷宫和无限的迷宫都有效。
1701742333
1701742334
对于一个未知的迷宫而言，不存在快速的解法，事先我们无法知道哪条路更好。我们所能采取的最好的方案就是检验几乎每一条路，直到发现终点。各种各样的迷宫算法其实只有一个功能：避免不知不觉地兜圈子或者在已知的死胡同和环道上浪费更多的时间。在探索迷宫中的新领域时，算法并不能给你“聪明”的指导。
1701742335
1701742336
我们看一下奥尔算法，这个算法的效率和其他算法一样。你从出发点开始可以发现：这个节点发出了三个枝，每个邻近的节点同另外两个节点相连。（在一个邻近的节点上有三个枝，其中一个枝把这个节点与出发点连在一起，这个枝已经考虑过了。）这六个点中的每一个依次与另外两个节点相连，这样新的节点距离出发点又远了一层。迷宫的节点和枝层出不穷。你探索的枝把你带到新的节点，而新的节点又产生更多的枝。这些枝中的一部分可能以前探索过（根据以前做的记号可以证明）。在多数场合，需要探索的枝的数量呈指数关系剧烈增长。你对迷宫的了解越多，你就越感觉到自己对迷宫的无知。
1701742337
1701742338
假定探索一个枝需要1分钟，奥尔算法的执行过程大致如下：
1701742339
1701742340
1701742341
1701742342
1701742343
在所有有限的迷宫中，发现新枝的过程最终一定会结束。在某个具体的探索阶段过后，大多数新枝会指向已经去过的节点。最终，所有的枝都被走过了，终点一定已经发现。然而，在无限迷宫中，指数增长永不停息。即使终点相对较近，找到终点也会耗费大量的时间，以至于实际上难以找到。也许相距5个节点，需要花费将近一天的时间，但是实际上一旦发现了路线，走到终点只需要5分钟。搜索一个15个节点远的终点需要若干年。如果到终点的距离是45个节点，那么为了找到终点，宇宙的全部时间都不够用。