11 废弃监狱中的深度优先搜索

进了监狱，刚走了两步，Frank就意识到他们走进了一个迷宫。曾几何时，这些计算型监狱几乎都不需要警卫，而是完全依靠自身结构的复杂与怪异去关住里面的犯人。那些想逃跑的犯人在付诸行动前都会三思：他们甚至都不知道溜过面前的这扇门后，等待着自己的会是自由，还是警卫的休息室。

“来点光吧？”Frank提议道。

“哦，对哦！”Socks回应道。他低声念了一个咒语，一团蓝色的光从他法杖的一端亮了起来，照亮了他们所在的毫不起眼的房间。

房间是正方形的，四周是粗糙的石墙，和几扇栎树木做的房门。环顾四周后，Frank愈发确信了自己的猜想：整个监狱是由很多网格状排列的房间组成的，而每间房内的一些墙上则有通向相邻房间的门。他们需要一间一间地找。但由于他们并不知道哪些房间之间门相连，所以他们必须得走一步看一步地搜索下去。

“看来是时候再来一次搜索了。”Frank说道。

“搜索？”Socks问道，“搜索什么？”

“当然是那些纸了。”Frank回答道。他确信那些纸一定是被藏在了这里。相比一般人用的仓库，一个废弃监狱毫无疑问是藏偷来物品的更好场所。当然，如果能找得到一座有护城河的城堡的话，那可能会更理想一点。现在的问题就是他们能否在这里找到那些纸，以及找到之后能不能从中得到任何有用的线索。

“千万别再来个广度优先搜索了。”Socks抗议道。

Frank考虑了一番。理论上，在一个网格状的监狱上用广度优先搜索没什么问题。每一个格子便是一个搜索状态，而每当你探索过一个格子后，就可以把与之相邻的尚未被探索的格子加到你的搜索列表中。Frank在头脑中想象出了整个搜索过程，就像水面上的水波逐步扩散的过程。

不过，如果把广度优先搜索用在现实生活中，比如在一栋建筑物里搜索，就会有一个很严重的问题，那就是会引起大量的倒退。由于每次都是将新的搜索状态加到列表的最后，所以需要探索的下一个状态可能离你特别远。即使在一个没有墙阻挡的空网格上，你也需要走相当长的一段距离才能抵达下一个状态。

而Frank正是不想走这样没有用的路。

“不，”Frank说道，“需要太多次倒退了。我们最好用深度优先搜索。”

“深度优先搜索，深度优先搜索，”Socks不断地对自己重复着这个词，像是在试图把它印在脑中似的，“我好像不记得……”

Frank对他挥了挥手，自信地向走廊深处走去。他说道：“我们不需要用咒语来做这个。当你还是个用纸尿裤的婴儿时我就已经在做这套深度优先搜索了。”

“所以用深度优先搜索不需要倒退了？”Socks问道。

“绝大多数搜索算法都会需要倒退。不过深度优先搜索中的倒退更适合人来走。”

“哦，我明白了。”

“不，你并不明白，”Frank毫不留情地说道，“如果你不懂这个算法的话，问就是了。不懂装懂只会给你自己带来麻烦。我见识过太多新手警察在搜索上栽跟头了，和你一样的新手。”

“好吧。那什么是深度优先搜索？”Socks问道。

“它是一个很简单的算法，”Frank解释道，“简单来说，我们就是沿着每条路往深处走，直到遇到一条死路。而当遇到死路后，我们就倒退一步，找到我们还没有走过的另一条路走下去。如此反复，直到找到我们的目标为止。

“现在我们就按顺时针的顺序开始吧。当我们有多个选择时，我们就按北→东→南→西的顺序来走，当然我们需要跳过之前已经走过的路。在每一个路口我们都按同样的顺序来选择方向，所以我们在能够向北走的时候总会优先向北走。不过现在，我们只有一个选择，那就是往南走。”

Frank正说着，他们就走到了第一个需要做决定的房间。Frank思考了一下他们可以走的方向：由于他们是从北边来的，不能往回走，所以Frank选择了顺时针顺序中的下一个方向：东边。在走出这间房之前，Frank从口袋中拿出了一支粉笔，在墙上做了一个记号。

又经过了两个分叉口，向北又向东之后，他们遇到了第一个死路。到目前，他们走过的房间要么是完全空着的，要么只有一个监牢。由于没有任何其他可以用来分辨房间的特征，Frank在每个房间的墙上都写上了一个不同的数字。而在Frank的头脑中，他已经将这些数字与它们所在房间里面霉菌的形状联系在了一起。

“现在我们退回上一个经过的房间，5号房间，那里面的霉菌形状像马一样。”当他们倒退回去的时候，Frank这样解释道。这次，他们选择了5号房间内唯一还没走过的方向——西边。不幸的是，他们立刻就遇到了另一个死路——一个空房间，里面有一堆像花的形状的蓝色和绿色绒毛状霉菌。

由于刚刚经过的房间的所有选项都已经尝试过了，他们继续倒退，回到了4号房间。4号房间的东边是死路，而北边他们已经走过了，于是这次他们走了南边。

他们走过了8号和9号两个空房间。这两个房间唯一的区别就是里面那一大团像钟乳石一般的霉菌的形状。Frank和Socks走过的时候，都下意识地和那团霉菌保持着距离，因为那团霉菌看起来随时都会坍塌。在又一次遇到死路后，他们只能连续倒退到了2号房间。

“我们会不会已经走过了？”Socks问道，语气还是一如既往地忧心忡忡，“或者会不会我们迷失在一个环中了？会这样一直无限走下去？”

Frank哼了一声：“年轻人，这不是我第一次做深度优先搜索了。跟着我做就没错的。”

“但不会有环吗？”

“你想想我为什么要在墙上做记号？”Frank问道，“如果我们不重复经过已经做过记号的墙上的门，我们就不会困在环中。”

Frank是在一次警用算法课的练习中学会这样做的。在那次练习中，Frank在全班的注视下绕着竹篱做的迷宫内的一个环走了六次。旁观的一个同学甚至大声开玩笑说：“看，他又走了一次！”

他们继续沿着一条曲折的路线向迷宫深处探索，时不时在遇到死路时倒退几步。