9 倒退一步，继续搜索（第2/2页）

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

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

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

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

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

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

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

警用算法导论：倒退一步

节选自Drecker教授讲义

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

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

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

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

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