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

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

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

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

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

警用算法导论：穷举搜索

节选自Drecker教授讲义

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

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

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

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

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