首页 » 算法神探:一部谷歌首席工程师写的CS小说 » 算法神探:一部谷歌首席工程师写的CS小说全文在线阅读

《算法神探:一部谷歌首席工程师写的CS小说》9 倒退一步,继续搜索

关灯直达底部

Mudwall这个港口的名字听起来相当不起眼。然而实地看到的甚至比它的名字还要让人失望。其实它根本算不上是一个港口。摇摇晃晃的船坞只能勉强容得下两艘中等尺寸的船。而Mudwall原本准备建成的一堵两英尺高的城墙,更是从来就没有建成过。整座城的周围只有小半段散落着星星点点的两英尺高的土堆。

Frank踏过土堆,来到了城里的商店。Notation和Socks紧跟在他身后。

店主看到他们的到来,惊喜万分,急切地走向他们。经过柜台的时候,却不慎将一摞画着胡萝卜的游客手册撞到了地上。

“你好!”店主以几乎要叫出来的语气说道,“欢迎来到Mudwall,著名的土萝卜农场之乡。你们需要点什么?食物?补给品?萝卜?萝卜味蛋糕?我们有一个特别好吃的胡萝卜派。”

“信息。”Frank说道。

店主的脸沉了下去。“哦,”他说,“那看来你们不是来参加萝卜节的了?”

“萝卜节?”Notation问道。

店主点了点头:“再过两天就是第50届萝卜节了。”

“会有很多人来看吗?”Notation问道。

“最近没那么多,”店主承认道,“Mudwall不像过去那样对游客有吸引力了。自从G’Raph开始办他们自己的土萝卜节后,人们就都去那里看了。”

Notation和Socks对望了一眼。Socks用唇语说道:“土萝卜是什么?”Notation耸了耸肩。

“你知道关于前两天经过这里的一艘船的信息吗?”Frank问道。

“什么船?”店主问道,“这里几个月都没有船经过了。倒是有几个驴车从公路上经过,但从没有过船。”

“你确定吗?”Notation说道,“我们在调查公务,你最好告诉我们关于最近从这经过的船的所有消息。”

“如果有船经过的话,我想我会知道的,”店主说道,“我的窗外正好可以看到船坞。就算我没有亲眼看到,也会听别人说过。现在这里都没什么船经过了。要是有船经过的话,萝卜之声——我们这的一个三人乐团——会去演奏迎接他们的。所以要是有过船经过的话我肯定会听说。”

Notation似乎准备开始新一轮的提问。但Frank插话道:“谢谢了,先生。麻烦了。”

紧接着,Frank带着Notation和Socks走出了商店,回到了泥泞的街上。

“你觉得他在说真话吗?”Notation问道。

Frank点了点头,来回巡视着这条街。“我们提到船的时候,他看起来是真心惊讶。”他说,“但再多打听一下总没有坏处。”

他们又问了十几个小镇上的居民同样的问题。这几乎是小镇上一半的人口了。结果让他们彻底死心了。没有人看到过任何船经过,也没有人听说过有任何船经过,甚至都没有人想过会有船经过。很明显,这座港口城市已经很久没有被船造访过了。

“也许那艘船是晚上来的。”当他们走回TCP Flyer号的时候,Notation说道,“也许他们派了一小队人划小船上岸,把文件交给了在这里等着的人,然后就离开了。”Notation边说边指向船坞上一块毫不起眼的木板。

“有可能,”Frank说道,“不过这都没用。没有证人,就没有线索。”

“你是什么意思?我们就找不到他们了?调查就到此为止了?”Socks问道。

Frank笑了笑说:“当然不是,年轻人。调查案子总会遇到走不通的死路。所以我们才会用一种可以支持倒退的搜索算法。”

Socks眼神空洞地看着Frank。看到Socks并没有理解自己在说什么,Frank补充道:“我们沿着最有可能找到答案的路一直往下走。但如果遇到了死路,就倒退一步,换一条之前没有走过的路继续调查。”

“所以你还有其他线索?”Socks问道。

“有一些吧。”Frank承认道。

“那我们倒退一步,考虑一下以前没有走过的路。”Notation沉思道,“之前我们找到的航海日志上,还列了另一个地方:Frayed Cable岛。”

Frank点了点头,开始回忆他们还有哪些线索没有用过。之前那个资格最老的恶棍提到过一个叫什么联盟的地名。这样看来,Frank现在还没用过的线索有:

Frayed Cable岛

Array Cart上的线头?

Vinettes

联盟?

倒退一步的话,便是回到了那本航海日志,和上面写着的他们还没有去过的Frayed Cable岛。要是他们在那个岛上也找不到任何线索的话,就只能去追查Array Cart上的线头,或者那些希望更渺茫的线索了。

“所以案子还没有结束,你还有其他线索对吧?”在TCP Flyer号开往Frayed Cable岛的一路上,Socks至少问了十次。

“在调查中遇到死路后倒退一步是家常便饭。”Notation再一次告诉Socks不必担心,“难道你们这行在做事儿的时候就从来不需要倒退一步吗?比如做药水的时候?”

Socks看起来十分惊讶:“做药水的时候怎么倒退一步啊?你又不能把加进去的蜘蛛腿给去除掉,也不能让药水回到搅拌前的样子。”

“我是说在你研究药水配方的时候,就像你加入蜘蛛腿后,如果发现它破坏了药水的魔性或者什么其他问题,你可以在配方上去掉蜘蛛腿,再尝试一种新的配方,对吧?每一个药水配方才是你搜索空间中的一个状态,而对你来说,倒退一步,便是退回之前成功过的其他配方。”

“哦,”Socks说道,“你是说改良配方的过程啊。当你研究药水配方的时候,总会需要不断地改进它。就像走一条弯弯曲曲的路才能找到你要的配方。没有人可以第一次就把所有东西给弄对。”

“就是这样。我们在说的是一回事。”Notation说道。

Mavis也加入到他们的谈话中,说道:“就好比你在一个洞穴里面找一堆丢了的东西。你会沿着一条路找,直到发现那条路上没有任何有价值的东西时,就会倒退一步,换其他的路继续找。”

“是的,”Notation犹豫地点了点头,“搜索中的倒退就像在洞穴里找东西一样。不过……”

“说到搜索,我们已经到了你们要去的地方了,”Mavis插话道,“Frayed Cable岛没有船坞。我们只能把TCP Flyer号停在这里,让你们划船走剩下的路了。”

警用算法导论:倒退一步

节选自Drecker教授讲义

几乎调查所有案子的过程中,都会需要倒退。即使是最厉害的警察也没有办法从头到尾一步到位。办案的过程中会遇到很多没用的误导人的信息,以及有歧义的线索。不仅如此,人自己也会犯错。所以在遇到死路时一定要学会如何倒退。简单地说,就是倒退一步,退回到之前一步的状态,然后选择另一条不同的路继续搜索下去。

对于目前所看到的算法,我们都可以高效地从任意一个状态跳到另一个状态。比如说在一个数组里面,我们可以很容易地通过序号来查看任何一个地方存放的数字。而在宾馆的走廊里,我们也可以在各个房间之间任意跑动。这种灵活性让我们的算法可以很高效。

但是也有很多搜索问题会限制你只能以特定的方式从一个状态跳到另一个状态。比如,在现实生活中的一个城堡里进行搜索时,你不能从一个房间直接跳到另一个房间。要想到另一个房间,你得先经过走廊和一些其他的房间。而在计算机领域中,一些数据结构(比如图和链表)也会做一些类似的限制。

即使可以在状态中自由跳转时,你也可以把倒退这个操作想象成是在你之前走过的路上去寻找新的没有走过的状态。在算法世界中,退回之前的状态比在现实生活中走回之前来的地方要省力得多。但是这两者在本质上是类似的:你退回一步,然后选一条新的路继续搜索下去。

在接下来的讲座中,我们会看到很多搜索算法遇到死路时倒退的例子。而一旦你正式成为了一名警察,你在工作中会遇到的死路将比你想象的要多得多。