10 用广度优先搜索去开锁（第2/3页）

“因为我们把那些新生成的更长的密码加到了列表的最后，所以我们会优先尝试所有短密码。”Frank突然补充道，“所以，你能做到这些吗？”

“这恐怕不合适吧……”Socks回应道。

“拜托！有没有搞错啊。”Frank打断道。

“这不就相当于一个开锁的咒语吗！”Socks说道。

“对。一点不错！”Frank大声叫道。

“算了，别管了。”Notation说道，用力地甩了甩手臂以表示自己的无奈，“要是他不想用咒语开锁的话，我们对他大喊大叫也没用。”她转过身，仔细地研究着那至少有十英尺高的石墙。过了一会儿，她对Frank说道：“Frank，要是你抬我一下的话，我也许可以爬过去。”

Frank用怀疑的眼光看了看那堵石墙。和大多数城堡的石墙不同，这堵墙虽然已经废弃多年，但并没有出现可以帮助人攀爬的大的裂口和青藤。这做工简直值得赞叹。从城墙顶上那错落有致的精致的尖刺可以看出，建这座墙的人一定也对自己的作品相当满意。

“也许吧。不过这座墙真的挺高的。而且那些尖刺看起来也相当锋利。”Frank说道。

“其实和在警察学校学的避开障碍那个项目没什么区别，”Notation说道，“不过这里地面是硬的，没有手可以抓住的地方，还有那些尖刺。”

“有了这些更刺激吧。”Frank说道。

“Frank，你快点闭嘴，来抬我一下。”

“算了算了，还是我来开锁吧，”Socks急切地说道，“我就用广度优先搜索咒语。不过我需要一个东西来写那个列表。你们有一卷羊皮纸吗？”

Frank和Notation对望了一眼，说道：“没有，就在地上写吧，反正足够泥泞，可以看清楚了。

“哦，那好吧。”

几分钟后，门上的锁开始发光。“开始了！”Socks说道。

门上的“确认”按钮短暂地闪了一下，紧接着发出了一声短暂的咔嚓声。不过门依然是锁着的。咒语刚刚尝试了第一个可能的密码——空密码。紧接着，泥泞的地上出现了一列字母和数字：

1，2，3，A，B，C

Frank在头脑中想象了一下这个选项列表所对应的搜索树：

数字1随即亮了起来，随后“确认”按钮也亮了起来。再一次，门发出了咔嚓一声，但依然是锁住的。地上的列表再一次变了，这次加入了搜索树第三层的一些可能的密码：

2，3，A，B，C

11，12，13，1A，1B，1C

但这些新的可能的密码被加到了列表的最后，而搜索算法本身依然还在继续尝试第二层剩下的密码。

密码2也不对，列表再一次变长了：

3，A，B，C

11，12，13，1A，1B，1C

21，22，23，2A，2B，2C

再一次，搜索树的最后一层延伸出了新的可能性。但搜索算法本身依然停留在第二层继续尝试，在尝试完所有一位的密码后才会进入到搜索树的下一层。

换句话说，搜索算法在尝试完当前层的所有可能密码后，才会进入下一层。

搜索算法又尝试了3、A、B、C这四个可能性，完成了整个搜索树的第二层的尝试。Socks这时说道：“这估计得花上一段时间了。”

Frank点了点头，眼睛一动不动地盯着地上不断变长的数字列表。“Notation，不如你去前面侦查一下吧？”

“好的，”她同意道，眼神中透出明显的解脱。新手警察一般都不善于长时间地等待，毕竟警察学院也没有办法教你如何一动不动地坐上几个小时。不过话说回来，听学院里Cloud教授的执法课其实也跟干坐着差不多无聊了。

Notation走后五分钟，锁发出了一声响亮的咔嚓声。随后，锈迹斑斑的大门随着巨大的噪声慢慢地打开了。随着搜索算法顺利完成，地上写着的列表也渐渐消失掉了。

“1111。”Frank说道，他看起来一点都不惊讶。毕竟密码必须设得足够简单，那些小喽啰们才能记住。

他用棍子把密码写在了地上的一块泥土上，又围着它画了两个圈。再怎么新手的警察也应该能看得出来这是留给她的消息。接着，他转向Socks，说道：“我们走吧。”

警用算法导论：广度优先搜索

节选自Drecker教授讲义

广度优先搜索是一个按顺序依次尝试可能的搜索选项的算法。换句话说，它每次都会选择尝试最先发现的但还没有尝试过的选项。

你可以想象一个列表（更具体地说，是一个队列），上面存着所有已知的但还没有尝试过的状态（选项）。每一步，算法都会选择从当前队列的第一个状态开始进行尝试。当发现新的可能性时，就将其加到队列的最后，以确保算法在尝试完所有先前已经发现的可能状态后才会去尝试这个新发现的状态。