没听见敲门声，门竟然开了——只有大门铰链的嘎吱嘎吱声宣告了有人到访。Frank立马起身欲取来十字弓，却又骤然停住，他想若是Vinettee集团的人登门造访，一定会敲门——不过是用斧头。进门者无论是谁，想必都有话要说。于是，Frank伸手拿起马克杯，将杯底仅剩的那点冷掉的咖啡一饮而尽。
“Donovan警长，”Frank看到来访者说道，“是什么风把您吹到这片和谐的街坊来了？我还以为您再也不敢越过第15号街了呢。”
“好久不见，”Donovan警长简短地说道，“Frank，别来无恙？”
“好极了。”Frank干巴巴地答道，同时盯着在屋里缓缓踱步的Donovan警长。
Donovan警长扫视着Frank寒酸的办公室，他红色的警官披风在身后沙沙作响。“私家侦探的游戏玩得可好？”
“够还债。”Frank在说谎。
Donovan警长点了点头。他稍作停顿，然后转向书柜，看了看书柜上的书。
“您这次来算是探访故人了？”Frank说道，“那我应该问候一下Marlene和孩子们的近况吧？”
“他们好得很，”Donovan警长头也不回地答道，“Marlene的海龟美容生意这些日子做得不错。Bill去年加入警队了。Veronica在做会计，我们最后本该……”
“我只是随便问问。”Frank打断了Donovan警长的话。
Donovan警长耸耸肩。他从书架上抽出一本书，随意翻了起来。Frank伸长脖子瞧了瞧封面——《警察学院年鉴：第21班》。
“你想要什么，Donovan警长？”Frank问道。
Donovan警长与Frank对视了一下，“我需要你的帮助，Frank。”他说。
Frank直起了身子。在Frank离开警队后的五年间，Donovan警长一共上门见了他两次，两次都是来警告他别再插手案件。这次Frank也已经做好了被威胁的准备，但现在，Donovan警长似乎遇到了特殊的问题——帮助解决这种程度的问题，或许可以用报酬还清Frank拖欠的房租。
“我早就不是警队的人了，”Frank漫不经心地说道，“你怎么不派个你信得过的侦探去接手？”
“我需要警队之外的人，”Donovan警长说道，“别装了，Frank。如果你不清楚我上这儿来意味着什么，那你也不是我需要的人。”
Frank笑了：“出内鬼了？在你的队里？”
“更糟。昨晚有人闯进局里的档案室，偷走了五百多份卷宗。”
“他们想找什么呢？”Frank问道。坐在椅子上的他，不假思索地往前探身，并迅速地抄起一卷新羊皮纸和一杆羽毛笔。Frank对这一系列的动作已驾轻就熟，就如同喝咖啡和爬楼梯一般。
“我不知道，”Donovan警长说道，“无迹可循！他们偷了整架整架的文件，从财产纠纷的文件到费用报表。我们记录的有关杀手、名流、私家侦探、司法人员的分类文件，统统被他们拿走了……甚至连农夫Swinson的两筐噪声投诉信也被他们拿去了。但奇怪的是，其余架子他们连碰都没碰。据我们统计，至少丢失了512份文件。”
“没准是农夫Swinson的某位邻居干的，”Frank打趣道，“他们一定是听说了，但凡超过100封投诉信，就会有实习生到你家给你严厉地上上课。”
Donovan警长懒得理他，他只是可怜地瞪着眼，直到Frank清了清嗓子，才打破沉默：“所以，你想让我去找回这些文件？”
Donovan警长摇摇头说：“我想让你找出那些贼。我们有文件的备份。我想知道，他们想要什么信息，打算用来做什么。”
“是一个搜索问题啊。”Frank若有所思地说。当年在警队时，Frank的两大特长就是解决搜索问题，以及惹怒Donovan警长。
“国王知道了吗？”Frank问道。
“我昨天已向国王简要禀报过了，”Donovan警长说道，声音中透出一丝不悦，“自打那个疯癫癫的巫师闹过之后，国王坚决要求对诸事进行每日简报。”两年前，一个名为Exponentious的狂妄巫师曾企图摧毁整个王国。此后，Fredrick国王亲自制定了全面的措施，以提升王国的安全。他为此颁布了三百多条新的安全法规，其中至少有五条是关于十层以下政府大楼内的公文保管的。
“这也不能怪他，”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教授讲义
在本课程中，我们将讨论几种不同的算法（以及相关的数据结构），来解决搜索问题。搜索问题的定义为：任何需要我们在可能的空间范围（搜索空间）内，找到一个特定值（即目标）的问题。
等你们将来毕业成为警察后，每天都会遇到可被归为搜索问题的问题。搜索问题的广义定义涵盖了很多不同的计算问题，例如“在警察日志上搜索某一特定条目”这样的简单搜索，以及“从窝点中找到房间”，乃至“找出符合某些条件的所有逮捕记录”这样的复杂搜索。这个类别是无法穷举的，但是在后面，我会给你们讲解一些基本和重要算法的简单例子。
该类别中所描述的算法拥有下面三个共同元素。
目标：你所寻找的那条数据。目标可以是一个特定的值，或是一条表示搜索成功完成的标准。
搜索空间：用于探测目标的所有可能性的组。例如，搜索空间可以是一份数值列表，或是图中的所有节点。搜索空间内的单个可能性被称为状态。
搜索算法：用于进行搜索的一组具体步骤或指令。
部分搜索问题会有额外的要求或复杂性，在我们学习不同的算法时将会逐一谈到。