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

Frank强忍住笑，开始仔细考虑这个问题。为首都的警察部队客串一回顾问，应该能拿到不少钱。他低头瞥了一眼自己的脚，一根脚趾头已经快从鞋子的破洞里露出来了。“如果让我做顾问，”他说，“那就得按我的方式来。”

决定性的关键就在这儿了。五年前他被踢出警队，就是因为他太按自己的方式做事。而Donovan警长是个信奉规则和命令的人。Frank上一次使用了启发式搜索，也是最后的那根稻草——于是就在当天下午，Donovan警长收回了他的警徽。不过，话又说回来，按Frank的方式做事总能得到结果。

“不出我所料。”Donovan警长最终答道。他从披风式风衣下抽出一份薄薄的文件夹，丢在Frank的桌上。

“我会跟你联络的。”Donovan警长说。然后，他毫无任何表示地转身离开了办公室。

在接下来的三个小时内，Frank喝了12杯咖啡，此时他弓身伏坐在桌前，第七次翻阅着这份薄薄的信息文件夹。文字在摇曳的烛光中跳动摇摆，却未能显示任何新的信息。

线索并不多。Donovan警长给他的是丢失文件的清单及事发当晚的值班名册，仅此而已。

最后，Frank夸张地叹了口气，抓起一张羊皮纸，开始做笔记。

任何搜索问题的第一步，都是确定你想找到的东西——目标，他的老教练在警用算法导论课上是这么称呼的。Frank很早就吸取了这个教训：他在成为警官的第一个星期，就被任命去找回公爵的名贵种马，结果那天下午他带了一只42磅重的海龟得意地回到警局。显然，这只抢眼的爬行动物不是目标。如果你找错了东西，那算法再好也毫无意义。

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

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

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

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

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

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

警用算法导论：搜索问题

节选自Drecker教授讲义

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

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

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

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

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

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

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