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

节选自Drecker教授讲义

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

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

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

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

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