26 启发式搜索

那个夜晚，Frank反复回顾着所有线索。一边密切关注着窗外的Rebecca Vinettee，一边抱怨安全屋里竟没有什么可以吃的。很快，他意识到这里不只是缺乏食物，就连警察大楼里的很多基础设施都没有，例如空白笔记本、羽毛笔及坚实的家具等。这时，Frank在窗户上发现了一个超大的“出租”（Safehouse forRente！）标志。还好，目前这里只是修改了密码，还没有被租出去。

几个小时后，Frank确认Vinettee集团的人找不到自己后，他不再盯着窗外，开始在空荡荡的房间中走来走去，研究案情。确定案件的时间和地点很容易——线索暗示有人明晚会攻击城堡。不幸的是，除了时间和地点，Frank还没有找到任何有更加价值的线索，特别是：谁去攻击？为什么攻击？怎样攻击？还有一个重要的问题：如何才能偷偷溜出去找点吃的又不被Vinettee集团的人发现？

然而，在一小时的踱步并仔细推敲案件的蛛丝马迹后，Frank甚至开始怀疑案发的时间和地点了。攻击城堡的意图似乎太过明显，并且警察们都已准备就绪。Socks甚至将此消息告诉了他所熟知的每个人，并让他们特别留意。

Frank停下来，猛然意识到Socks可能有问题。Frank恢复了原有的理智，“我就知道我不应该相信任何人”，Frank的脑海中重演了过去几天发生的事，这次他理清了种种迹象。他警觉到是Socks“不小心”点燃了监狱中的文件，并毁掉了证据；他应该意识到有人已经将他去披风商店的消息泄露了出去；他至少应该对那次荒谬又凑巧的几桶腌鳗鱼救援行动产生怀疑。但最重要的是，Socks曾经错误地将一个点加入了二叉搜索树，可没有任何一个二叉搜索树专家会犯这样的错误。无疑，Socks一直令人怀疑。不过话又说回来，Frank也一直在怀疑每一个人。

这种想法给他带来了更多的问题，而且时间和地点的问题还是没能解决。如果Socks一直在给他们提供虚假信息，那么Frank不得不质疑每一件事。巫师要做什么，怎么做？作案动机是什么？不过Frank发现，每当他摸透精心设计的情节时，犯罪者往往会无缘无故喋喋不休地谈论案发动机。此时，他也已放弃溜出去寻找食物，尽管肚子不停地咕噜咕噜叫。

“魔法面具将如何实现伪装？”Frank喃喃自语道。如果盗贼计划攻击城堡，他们还会用这个面具吗？或者弃之，想办法使Marcus魔法身份徽章失效？难道他们只是需要借助它闯入警察局吗？盗贼循着的是什么样的规律？Frank开始在他的笔记本中一一列举问题，很快这些问题的数量超过了已有线索的数量。

Frank开始思考接下该采取什么措施。时间非常紧迫，他需要深入研究启发式搜索算法——如何依据经验来帮助算法快速达到目标。比如说，搜寻一只丢失的乌龟时，因为乌龟行动缓慢，所以Frank使用“附近优先”的寻找法则；在车站寻找最新鲜的咖啡时，他依赖“大咖啡壶优先”的法则，因为这种经常是最近刚泡的；在前往一个位于未知城市的高大城堡时，“优先沿着城堡方向行走”的法则通常能让他仅仅遇到几个死胡同后就能抵达目的地。启发式搜索并非永远完美无缺，但往往能提供有用的信息。

在警队工作期间，Frank逐渐喜欢以“优先追查最可靠线索”的方式来进行启发式搜索，因为特定名称和实物证据总好过那些流言和无端的揣测。

在Frank的职业生涯中，只有一次查案忽略了使用启发式搜索。当时，“玻璃箱”Billy对于一次即将发生的盗窃案已留下多种提示。首先，Billy告诉Frank逃亡车的准确等候地点、车型甚至车轮发出的特殊声音。另外，Billy在玩飞镖游戏的喧闹欢呼声中无意间听到了谣言，说Rebecca Vinettee也亲自参与了，而且目标和鱼有关系。

但是Frank忽略了所有更有效的搜索算法，而是选择直接去追捕Rebecca Vinettee。他明白在他们装好车之前Rebecca Vinettee可能就会消失，或可能利用另外一个路线退避到藏身处。他需要在她消失之前逮住她。他监视了首都的鱼仓，那里离逃跑的车辆仅隔两个街区。

事后警长声嘶力竭地解释道：“鱼仓是与此处仅相隔两个街区，但是在另一个方向！”另外，Orb商场与逃跑的车辆只相隔四分之一个街区，一伙与Vinettee集团毫不相关的人偷窃了64块高质量的球状玻璃宝珠和两个立方宝珠，装上车逃跑了，车轮子令人讨厌地咯吱咯吱叫，就像Billy说的那样。Frank对Billy提示的描述，以及他坚持应该始终怀疑Vinettee集团的做法，都没能让警长信服。

但是，在目前的情况下，Frank甚至连模糊的线索也没有了。他已经用尽大部分可靠线索，早就开始凭猜测和怀疑办案了。如果想要取得任何进展，就还需要更多信息。他转向自己第二种最可信赖的搜索法：当走进死胡同时，收集更多信息。他需要知道更多有关魔法面具的信息：如何使用面具，何种防御魔法能够挫败它。面对这种情况，他必须要找到一位专家才行。

警用算法导论：启发式搜索

节选自Drecker教授讲义

启发式搜索是依据经验来帮助算法快速达到目标。你可能亲耳听某些警察说启发式搜索法只不过是随意乱猜，但你也能看到这些警察同样是在依靠过去帮过他们的那些经验技巧和法则。当然，与你所能得到的信息一样，不同的启发式搜索算法质量不同，认清这一点是非常重要的。

启发式搜索算法的一个最显而易见的例子是在生活中导航。不管你要穿越蜿蜒的迷宫、寻找一个未知城市，还是要找到通往餐厅的路，你都会发现自己在使用启发式搜索作为指导。如果有两条道路，你要先走哪一条？一种通常可靠的常见搜索法是根据简单的距离测量来进行优先选择。我喜欢的方法是使用“和鸟类飞翔路径”一样的距离测量法：如果路上没有挡路的东西，目标有多远？在实践中，这种搜索法意味着我总是要选择看起来让我离目标更近的路径——至少这条路径的方向是正确的。在这条路上，我可能会走进几个死胡同，但就整体而言，我发现这是一种有效的搜索法。

当然，还有很多糟糕的启发式搜索法。警察们如果在使用新的搜索法时没有仔细检查的话，很容易让自己深陷麻烦中。几年前，一位年轻的警察创造了一种特别不好的搜索法。在捣毁一个走私集团取得前所未有的成功之后，他认为所有的调查必须从码头上开始。事实证明这种启发式搜索法是错误的，并没有帮助他朝正确的方向进行调查，而是经常让他很快就走进死胡同。在18次的调查失败后，他的警长就让他永远从事巡逻码头的工作了。