1 搜索问题（第2/2页）

这一次的案件中，问题不在于是什么，而在于是谁。Donovan警长在这一点上说对了。一旦贼拿到了文件，警方就算找回来也于事无济。因为贼已经获得了他们想要的任何信息。

所以，他的目标很简单：弄清楚是哪个人或哪些人偷走了文件。

任何搜索问题的第二步，都是确定搜索空间。你要搜哪里？Frank每天找自己的钥匙时，搜索空间是办公室里的所有平坦表面。而当Frank想找出一个犯罪分子时，他的搜索空间则是首都附近的每一个人。

Frank坐了回去，揉了揉眼睛。这是一个很大的搜索问题——要在犯罪之都找到一个特定的罪犯。不过他遇过更糟的情况。

既然他已经明确了问题，那么现在他可以开始选择算法了。线性搜索首先出局，因为他可没能耐去审问城里的每一个人。他还可以排除掉过去在学院里学来的很多其他的花哨算法。对于这样的问题，他必须回到自己的基本搜索算法工具包，这是私家侦探最值得信赖的朋友。

Frank在羊皮纸上写下一条笔记。他有了寻找的目标，知道了搜索空间，现在也确定了算法，是时候开工了。

警用算法导论：搜索问题

节选自Drecker教授讲义

在本课程中，我们将讨论几种不同的算法（以及相关的数据结构），来解决搜索问题。搜索问题的定义为：任何需要我们在可能的空间范围（搜索空间）内，找到一个特定值（即目标）的问题。

等你们将来毕业成为警察后，每天都会遇到可被归为搜索问题的问题。搜索问题的广义定义涵盖了很多不同的计算问题，例如“在警察日志上搜索某一特定条目”这样的简单搜索，以及“从窝点中找到房间”，乃至“找出符合某些条件的所有逮捕记录”这样的复杂搜索。这个类别是无法穷举的，但是在后面，我会给你们讲解一些基本和重要算法的简单例子。

该类别中所描述的算法拥有下面三个共同元素。

目标：你所寻找的那条数据。目标可以是一个特定的值，或是一条表示搜索成功完成的标准。

搜索空间：用于探测目标的所有可能性的组。例如，搜索空间可以是一份数值列表，或是图中的所有节点。搜索空间内的单个可能性被称为状态。

搜索算法：用于进行搜索的一组具体步骤或指令。

部分搜索问题会有额外的要求或复杂性，在我们学习不同的算法时将会逐一谈到。