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

“这也不能怪他，”Donovan警长嘟囔道，“当时真是挺险的。多亏有Ann公主，否则谁知道王国今天是何种境地。”

Frank默默点头。当年Exponentious巫师对研究算法的学者们施下诅咒，从而袭击了王国的算法基础。短短几个月的时间，就连简单的操作都被他搞得低效不堪，王国逐渐濒临停转。损坏的迹象随处可见，甚至在当地的面包店里，Frank都亲身目睹了恐慌爆发，因为顾客们发现，他们都想不起来如何排成一个队列了。

“当然了，国王对此问题也抱有个人兴趣，”Donovan警长生气并急躁地说道，“他想知道所有的细节：谁在负责此案？我们在用哪些搜索算法？我们是否搜遍了所有相邻的建筑物？”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

警用算法导论：搜索问题

节选自Drecker教授讲义

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