2 穷举搜索寻线人（第2/2页）

“Billy！”Frank叫道。

Billy怀有愧疚感地跳了起来。“Frank？”他咧嘴笑了起来，很高兴有人对他打招呼，然后又坐了回去，“拉把椅子过来呗。”

“我正在找一些信息，”Frank一边解释，一边在Billy对面坐了下来。

“说不准我有呢，”Billy说，“不过，最近我觉得有些事情想起来挺吃力的。”Billy说道，同时朝一个空了很久的杯子瞧着，估计并不是他的。

Frank示意咖啡师很快在桌上放了一杯啤酒。“记得任何有关警局失窃案的事吗？”Frank问Billy。

Billy睁大眼睛，畏缩了。“你是说……抢劫？”他心虚地问道。他的双眼扫视着屋内，但一如既往，并没人留意他。

Frank在桌上放了两枚金币，并努力让自己不要心疼这两枚金币。他花不起这钱，尤其当他不知道自己花钱买的是线索还是闲话时。但他清楚，让Billy提供信息不会便宜的。他俯身凑近一些：“前天晚上，”他悄然说道，“一大堆文件被贼偷走了。”

“听起来不像是容易想起来的事情啊。”Billy说，他盯着金币，“恐怕你问错人了，Frank。”

“这可是金子啊！”Frank咆哮道。

“抱歉，我帮不到你。”Billy说，他再次环视一下屋内，然后补充道，“即便我知道一些关于失窃的事，我也会努力忘掉的。或许我知道一些小事，比如是谁帮忙运走了文件，但这不值得冒险，免得我睡醒一睁眼发现自己的鞋里塞满了牛粪。”

Frank瞪大了眼睛，但Billy沉默不语了。作为一个靠分享信息过活的人，Billy不肯透露这件事情的行为显得非常奇怪。“牛粪？”Frank问。

Billy点点头，但不再多说。

“你就不能再具体点吗？”Frank问道，“是说北方或南方的牦牛吗？”

“这重要吗？”Billy问，“问题在于，即使知道是谁安排的运输，我也不会记住的。如果那些人碰巧在镇外大约五英里处拥有一个大农场，在那儿可以轻易地让某人消失，那我就更不会记住了。而如果那座农场的主人有着非法活动的历史记录和危险的幽默感，那我就加倍更不会记住了。在这种情况下，记住任何事情都是绝对不明智的。”

“太糟糕了，”Frank笑着说，“也许下次能记起来点。”他朝金币点点头，“希望它能让你将来能记住事儿。”

Frank起身，大步走出Exponentiated Expresso。他向左转，沿着街继续走。一走出三比特巷，他便可以兜回去，前往Crannock的农场——唯一与Billy的描述有点相似的农场。

在他经过第六家店Faulty Register时，他注意到一道影子钻进了附近的小巷。他压低嗓音骂了一句，但没有停步。Frank意识到自己被人跟踪了：看来警长上门找他时没有十分地谨慎。

但当他离开城里，踏上前往Crannock农场的粗糙泥土路时，发现自己的心情很好。Billy给他的并不多，但即便利用这一点点信息，也能看出使用高效搜索算法和使用穷举算法的不同。

警用算法导论：穷举搜索

节选自Drecker教授讲义

用穷举搜索算法搜索目标值是要在整个搜索空间范围内尝试每一种可能性。最常见的穷举搜索是线性搜索，即按照顺序简单地检查所有不同的可能性。

想象一下，当你正在追逐强盗进入了一个废弃旅馆的二楼走廊时，接下来会发生什么？走廊里有30道门，全部是关闭的。如果你遵循正确的警方工作程序，你的同伴已经封锁了对面的楼梯，你和强盗被困在这层楼上，你将如何找到强盗？是随机选择一扇门打开，发现没有强盗，然后出来再随机打开一扇门，就这样跑来跑去，直到你幸运地找到了强盗？不！你应该搜索整个楼层，把所有的门依次踢开。

或者来思考一个算法，在一个数字列表（数组）中寻找一个目标值。线性搜索算法要从第一个数字开始查找，逐个地检查数字列表中的每一个值，直到找到目标值。假如我们要在一个数组中搜索5，那么搜索的过程如下：

线性搜索算法的优势是它们在任何领域都容易实现，即使要处理的是非结构化数据。你不必猜测强盗会在哪个房间，你只需要依次检查所有房间。穷举搜索算法的缺点是，在已经结构化的数据中采用这种搜索方式往往不够高效。如果你知道强盗在哪里，你可以使用这个情报来大大减少你踢开门的次数。

高效算法的关键在于有用的信息！