10 用广度优先搜索去开锁

Frank、Socks和警官Notation现在正围在监狱外墙的后门边。尽管铁门上锈迹斑斑，但在Frank用力踢了两脚后，铁门依然完好无损。只不过这两脚让铁门上的铁锈粉末和灰尘全都扬到了空中。而Frank在整个过程中一如既往地骂骂咧咧，让站在一旁的Notation学会了至少六个新的用Boolean来骂人的词汇。

“所以……看来这样行不通。”Socks说道。Frank无视了他，开始研究门锁的结构。这是一种很常见的密码锁，第一行上放着1、2、3、A、B、C共六个按钮，而第二行则放着一个确定按钮。

“看来我们得用老办法了。”Frank说道。

“我们的老办法不就是踢门吗？”Notation说道。

Frank同样无视了Notation。“Socks，你知道任何开锁的咒语吗？”

“当然不知道，”Socks大声回答道，“那些咒语是违法的！”

“那有没有可以削弱这个锁的咒语？让锁链变脆弱点的？”Frank接着问道。

“你想让我帮助你去破坏别人的财产？”Socks看起来吓坏了，“这比开锁还要糟糕。你知道我会惹上多大的麻烦吗？”

“搜索咒语呢？完全组合咒语？或者广度优先搜索咒语？”Notation插话道。她不想再听Socks谈论咒语合法与非法的话题了，在之前Frank问Socks能不能用魔法去复制一枚金币时，Socks已经说得够多了。当然，她和Socks都觉得用魔法去复制金币这个事情是不道德的。

“我用过几次广度优先搜索咒语，”Socks回答道，“我真正擅长的是二叉搜索树。不过我对很大一部分计算用的方法都很熟悉。曾经有次……”

“广度优先搜索算法对这个锁会有用吗？”Frank打断道。多年来，Frank在办案中和很多巫师都合作过。其中既有声名远扬的大牌巫师，也有相对不那么出名的巫师。他至少已经见识过十多种用来开锁的咒语了，不过还从来没有遇到过用广度优先搜索咒语真正把锁打开的。

Notation笑着说：“肯定有用！听起来有点抽象，不过我最近在警用算法课上见过一个类似的问题。你仔细想想看，其实开密码锁就是一个搜索问题。你需要输入一串字符去打开锁，而搜索空间就是所有可以用那些字符组成的字符串。每一个这样的字符串，从只有一个字符的，比如A和1，到那些复杂的字符串，比如ABC123CBA321，都是一个有效的选项。而我们要搜索的目标就是那个可以打开锁的字符串。”

“不过我们都不知道这个密码里有多少个字符，”Socks说道，“有可能这个锁的密码有30位那么长。”

“所以她才会建议用广度优先搜索。”Frank说道，边回答Socks的问题边思考着。

“我不明白。”Socks说。

Notation紧接着解释道：“你看，广度优先搜索从一个起点开始，慢慢沿着一个边界推进。所以理所当然地它就会由短到长地尝试所有可能的字符串。”

“啊？”Socks说道，看起来Socks已经困惑得有些惊慌失措了，“我以为广度优先搜索是用一个魔法表的。我从来都只是用一个魔法表的。难道它不就是用一个魔法表来搜索的吗？”

“是的，”Notation说道，“广度优先搜索会记录下包含所有接下来需要尝试的选项的一个列表。整个算法说到底就是一个不停在执行的循环。每次循环时，这个算法都会从那个选项列表最前面拿出选项去尝试，同时将新的选项加到列表后面。每一次循环执行的时候，我们都会选出列表第一个可能的选项。如果它并不是我们的搜索目标，我们就将所有由它可以演变成的之前还没有尝试过的选项加到列表最后。

“整个搜索过程从一个起始点开始。在我们现在这个情况下，这个起始点就是一个空密码字符串。而我们每尝试一个密码，都会将所有由这个密码可以演变到的其他密码加到列表最后。具体来说，每次尝试一个密码之后，我们都会尝试在这个密码后面再加上一个字符。举个例子，我们现在知道这个密码锁的密码只会包含1、2、3、A、B、C这六个字符。所以在我们尝试过3A之后，就需要将3A1、3A2、3A3、3AA、3AB、3AC加到我们列表的最后。”

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

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