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的头脑中，他已经将这些数字与它们所在房间里面霉菌的形状联系在了一起。