1701742264
如果你是从一条新路到达的(也就是说,你的身后只有一行面包屑),转身沿原路退回上一个节点。否则:
1701742265
1701742266
如果有一条没走过的路,选择这一条。否则:
1701742267
1701742268
任选一条以前只走过一次的路。
1701742269
1701742270
这就是全部需要遵守的规则。根据特雷莫算法,你会在迷宫内完成一次完整的旅行,每一条路你都走过了两次,两个方向各一次。当然,在到达终点以后就可以停下了,没有必要完成整个巡回。
1701742271
1701742272
和右手法则一样,这种算法的效率极低。当然,你有可能非常走运地从入口直接走到终点,但是可能性更大的是,你走完了迷宫的大部分甚至是全部以后才到达终点。
1701742273
1701742274
在什么时机采用右手法则或者特雷莫算法都不算晚。你可以走进一个迷宫,随心所欲地走,在迷路以后再采用算法。在任意一个点都可以开始执行算法,把这个点当作另一个“入口”。特雷莫算法将引导你从这个点出发完整地游历整个迷宫,包括终点和实际的入口。这两种算法不仅可以用于花园迷宫,在令人晕头转向的建筑中也有效。如果你在五角大楼或卢浮宫里迷路了,你可以利用特雷莫算法走出来。
1701742275
1701742277
无限的迷宫
1701742278
1701742279
设想一个面积无限延展的迷宫。这个迷宫无边无际,遍布整个世界,所以根本没有入口和边界。你从迷宫中的任意一个点开始探索,你不知道自己在这个宏大的迷宫中的位置,正如我们不知道自己所处的星系在宇宙中的位置一样。
1701742280
1701742281
这个迷宫的结构非常简单。在每个节点上,恰好有三个枝交汇。各个节点通过标记相互区分,雕像、长椅、树木等各种各样的东西都可以充当标记,你寻找的终点可能就是其中的某一个。
1701742282
1701742283
和所有其他迷宫一样,这个迷宫在本质上也是非理性的。在寻找一个给定的目标的过程中,没有哪一条路比其他的路更优先,任何一条路都可能是“正确的”。正确与否依赖于这个迷宫是如何建造的。这个迷宫的结构是通过无止无休的自我复制实现的,在复制过程中又加入了变化——意识到这一点令人绝望。假定一个游客花了若干年探索迷宫中的一个特定区域,到达了已知区域的边界上的一个岔路口。他面对两条未探索过的枝,其中一条通向他寻找的标记,但哪一条是呢?实际上,在整个迷宫中他已经探索过的部分一定会多次重复,在某些重复结构中,熟悉的路线连接迷宫的其他部分,因而,右侧的路通向终点;但是在其他场合,左侧的路才是正确的。当然,这个游客无法知道他当前的处境属于哪种情况。对于任何企图以理性的方法选择路线的计划,这都构成了一个嘲讽。
1701742284
1701742285
假定你处在这个无限的迷宫中,闲逛了一段时间之后,绝望地发现自己迷路了。你没有沿路做标记,也不知道自己究竟走了多远。
1701742286
1701742287
在这个困境中,你不想采用特雷莫算法。只要你新走的路没有和以前走过的路交叉,特雷莫算法就不会对你的行动给予任何指导。你有可能在迷宫中深入若干英里,越陷越深。在一个无限的迷宫中,你甚至有可能从未与自己走过的路交叉,从未见到终点,也从未再次遇到熟悉的地点。
1701742288
1701742289
特雷莫算法和右手法则预先假定,即使走遍迷宫的全部或一个很大的部分也没什么大不了的,只要确保自己不是在不停地兜圈子,最终到达终点就行。特雷莫算法实际上鼓励优先探索迷宫中较远的区域。根据此算法,选择未走过的枝总是优先于熟悉的枝,而且,除非不得已,你应该尽量避免与自己走过的路交叉。在有限的迷宫中,这些建议是合理的,因为终点几乎总是距离入口相对较远。否则的话,迷宫的主人就浪费了自己的地产,付给维护灌木的园丁工资,却没有增加迷宫的趣味性,这是没道理的。
1701742290
1701742291
但是在无限的迷宫中,你不能浪费时间在未知的区域漫无目标地闲逛。当你迷失方向、但确知目标比较近(与迷宫的整体大小相比)时,你应当首先探索邻近的区域,在必要时再向外扩展。耶鲁大学的厄于斯泰因·奥尔(Oystein Ore)在1959年介绍的一种算法就是如此。
1701742292
1701742294
奥尔算法
1701742295
1701742296
为了解释清楚这种算法,最好假定你从一个节点开始。如果你的出发点不是一个节点,那就走到最近的一个节点处。如果不知道哪个方向可通向最近的节点,随便选一个方向,走到你遇到的第一个结点。这个点就是你的出发点。
1701742297
1701742298
从出发点开始,探索交汇于此的每一个枝。在进入每一个枝的时候,在入口处放一块鹅卵石。对每一个枝的探索仅限于到达下一个节点,然后在这个枝的终点处放一块鹅卵石,原路返回出发点。
1701742299
1701742300
如果遇到死胡同,你就做一个标记。一旦对一个枝做了死胡同的标记,以后就可以忽略这个枝了。做标记的方法可以是在死胡同的入口处拉一条封锁线,或者摆上一排鹅卵石。
1701742301
1701742302
如果某条路转了一圈又回到最初的节点,那么你也要把它标记为死胡同。这种路对你也是无用的。
1701742303
1701742304
你的兴趣在于确定那些通向有新枝的新节点的枝。在探索的第一个阶段结束之后,每一条有可能通向终点的潜在路线都已经做了记号——路的两端各有一块鹅卵石,而你重新回到了出发点。
1701742305
1701742306
下一步,探索的深度达到两个节点。沿着每一条非死胡同的枝走到新节点,从这个新节点出发探索每一条由此辐射出去的枝,探索方法照旧。在最初的那个枝的两端各加一块鹅卵石(此时,这个枝的两端各有两块鹅卵石),对于新探索的第二级的枝,两端各放一块鹅卵石。这个办法可以防止你找不到返回出发点的路,可返回出发点的路有一个特点:路口处的鹅卵石比其他路口多一块。和第一阶段一样,对死胡同和兜圈子的路做标记,予以排除。如果一个枝通向以前探索过的节点(这个节点至少有一块作为记号的鹅卵石),在这个枝的两端也做标记,予以排除。
1701742307
1701742308
探索的第三步,深度达到距出发点三个节点处,在每一个探索过的枝的两端各加一块鹅卵石。依照以上规则不断推进探索步骤,直到发现终点、入口或者其他想找的东西。
1701742309
1701742310
奥尔算法可以确定通向终点的最短路线(所谓最短是指枝的数量最少,而非物理距离最短)。当然,你的探索过程不是最简的。但是,如果最短路线需要经过五个节点,你一定可以在探索的第五个阶段发现它,而且可以确保它是最短的。
1701742311
1701742312
奥尔算法的效率同样低得可怜。它不是直接对准正确的路线,而是检查所有可能的路线。这是必不可少的,因为任何一条路线都可能是正确的。
1701742313
[
上一页 ]
[ :1.701742264e+09 ]
[
下一页 ]