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

Socks聚精会神地思考着，随后问道：“我们怎么知道之后应该加哪些选项？”

“把它想象成一棵由所有可能选项组成的树，”Notation说道，“树的每一个分枝，即节点就是我们列表中的一个可能的密码，比如3A。而由这个分叉点分出去的那些节点就是由这个密码再加上一位可以得到的新的可能字符。而广度优先搜索就是在搜索完树的一层后再开始搜索下一层。”

“因为我们把那些新生成的更长的密码加到了列表的最后，所以我们会优先尝试所有短密码。”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这时说道：“这估计得花上一段时间了。”