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个节点，那么为了找到终点，宇宙的全部时间都不够用。
1701742344
1701742345
我们从计算机程序员的角度来看一下最长路径问题。你希望用计算机来判定，在一个比较大的迷宫中的两个点是否被某条路线连在一起。为此，你必须为计算机提供一幅迷宫“地图”。这幅地图以表格的形式列出了迷宫中的所有节点和所有的枝。节点标明数字或名字，通过明确一个枝连接哪些节点以及节点之间的距离可以确定枝。（无论采用什么计数单位，距离都用整数表示。）一个枝可能被表示为“节点16，节点49∶72英尺”。距离是游客所走的实际长度，而非直线距离。充当入口和终点的节点同样如此表示。
1701742346
1701742347
最长路径问题还需要考虑一个因素：一个特定的距离n。最长路径问题问的是，在入口和终点之间是否存在长度大于n的直接路径。如果你愿意，n可以取任意小的值，甚至是0。当n取0时，最长路径问题转化为：是否存在一条长度大于0的路径，这等价于是否存在一条连接入口和终点的任意形态的路径。
1701742348
1701742349
既然存在性问题属于NP完全问题，比它更难的无限迷宫问题至少和NP完全问题一样难。如果判定通向G点的路径是否存在这个问题的难度已经达到了实际不可解的程度，那么具体指明这样一条路径的问题更是如此。
1701742350
1701742351
推理的迷宫：悖论、谜题及知识的脆弱性 [:1701739731]
1701742352
迷宫先知
1701742353
1701742354
NP完全问题有一个令人惊异的属性：其答案很容易验证。设想你遇到一个先知，无论你问什么问题，这个先知都能依靠神的启示立刻给出答案。那些相信先知的全知能力的人带着问题来问先知，这些问题如此之难，以至于他们解决不了，但是先知却能立即做出回答。
1701742355
1701742356
然而，当先知试图向所有人证明自己的特异功能时，他遇到了麻烦。他的想法是，通过表明他给出的答案的正确性来证明自己确实是全知的。但有时这是不可能的。
1701742357
1701742358
人们问他的问题分两类。最常见的一类是其他人无法回答的难题：为什么存在邪恶？神存在吗？圆周率的十进制小数展开式中小数点后第10100位数字是几？实际情况是，先知的回答从各个角度来说都是正确而精准的，但是他无法证明这些答案。怀疑者对他冷嘲热讽：对于这些问题先知可以胡乱给出任意的答案，反正别人也无法揭穿他。即使是相对而言比较现实的问题（例如圆周率的第10100位的数字）也难以验证，其难度已超出了世界上最强大的计算机的处理能力。
1701742359
1701742360
为了证明他的特异功能，这个先知必须回答那些答案可以被检验的问题。人们问他的问题中也包括这种，其中某些是怀疑者提出的，提问的目的就是拆穿他。基里巴斯的首都是哪儿？622 521的平方根是多少？《小妇人》中的姐妹们叫什么名字？这只密封的箱子里装的是什么？
1701742361
1701742362
先知正确地回答了所有这些问题，而且提问者知道先知的答案是正确的。提问者知道这一点，是因为提问者本来就知道答案。问题就出在这儿。这些问题太简单了，因而不足以确切无疑地证明先知的神力。既然提问者早已通过普通的方法知道了答案，那么可以设想，先知同样可以利用普通的方法了解或发现。怀疑者会说，他的全知可能是假冒的：他不过是一个计算天才，在一些琐细的事情方面的知识非常渊博。至于最后一个问题，他采用了“测心术”——表演者在舞台上施展的不入流的骗术。
1701742363
1701742364
这两种结果都是先知的失败。如果一个问题是其他人无法回答的，怀疑者会指控他捏造；如果一个问题的答案是已知或者可知的，怀疑者会指控他假冒。为了证明自己的全知，先知需要第三类问题，其特点在于：问题很难回答，可一旦说出答案，便很容易验证。存在这样的问题吗？
1701742365
1701742366
无限迷宫问题就满足这个要求。让怀疑者在这个迷宫中选两个随机点，然后让先知在两点间确定一条路线。任何人都能轻而易举地验证答案正确与否，他们需要做的不过是沿着指定的路线走，验证一下自己是否到达正确的地点。
1701742367
1701742368
这个问题不会是另一个“简单”的问题吗？我们必须确保选定的这两个点足够远，没有人知道连接这两个点的路线，甚至没有人可以用正常方法找到一条这样的路线。算法（包括奥尔算法）的相对低效性保证了这样一对点的普遍存在。如果两个点相距20个节点，用普通方法找到一条路线需要若干个世纪。[3]另外，这个问题不会是另一个“困难”的问题吗？不会，因为我们只需20分钟就可以检验先知的答案（假定每分钟走过一个枝）。迷宫的一个解比迷宫本身容易太多了。