23 最佳优先搜索：侦探最值得信赖的工具（第3/3页）

“谢谢你。”Frank说道。

“还有没有其他新调来的人需要去特别关注的？”

Frank摇摇头：“新调来的警察们分布在不同的犯罪现场，但是没有规律，没有任何一人与两个以上的盗窃案相关，除非一整个班都是叛徒才有可能，所以我认为这行不通。”

“你调查得很好，Frank。”警长说道，“这是我这么多年来见过的能把最佳优先搜索用到极致的案例之一。”

Frank笑了，即使在警队，也很少有人会知道这种类型的调查需要使用最佳优先搜索。多数人只会说“我正在调查”或是“这些线索我正在跟进”。

尽管对其认知不足，最佳优先搜索仍是警官们办案必备法宝之一，它就像记事本或者是一双舒服的鞋子一样重要。在最佳优先搜索中，你需要时刻维护一个线索列表，每次从中选择最可靠的一个线索去调查，调查完毕后，再从列表中选出下一个最可靠的线索继续调查。当然如果在调查的过程中发现了新的线索，就将其及时加入到列表中。这种方法对于查案很有帮助。

Frank摇摇头。

“那好，”警长说，“继续调查。如果Unnecessary Complexity联盟真的存在，而且一直在背后操纵这个案子，那么我们已经深陷危机之中了。注意安全，Frank。”

“我一向很谨慎。”Frank回答，他站了起来，又停住了，“最后一个问题，你知道Notation是如何知道Array Cart的吗？”

“我不知道，”警长回答道，“为什么不直接问问她呢，她现在似乎正站在我的办公室门口。”

警用算法导论：最佳优先搜索

节选自Drecker教授讲义

假如你在这门课程中只记住了一个算法，那么你一定要记住最佳优先搜索这个算法，它将是你警队生涯中最有用的工具。也许所有的案件到最后你都需要使用这个算法。

最佳优先搜索是基于某种估值分数或者评价函数来选择接下来探索哪个状态的算法。每一个新发现的状态也都将被赋予一个分数，这个分数就是算法对这个新发现状态的估值。例如，我们可以为每一个状态标记上一个值，可能是目标状态的概率（如果这个概率可以被估计的话）或者是在调查中线索的重要程度。其实最佳优先搜索就是在每时每刻维护着一个带有估值分数的状态列表，每次从这个有序列表取出下一个估值分数最高的状态去探索。

当然，最佳优先搜索也可以按照代价最小的规则来选取下一个要探索的状态，这个代价可以是当前状态到目标状态的估算距离。在这种情况下，每一步都要选择列表中估值最小的一个状态进行探索。

我们来看一个迷宫问题。现在我们已知起点和终点的坐标，可以在搜索空间中为每个点（状态）都设置一个值，这个值就可以是从该点到终点的距离，例如，可以使用曼哈顿距离——两点之间的垂直距离加上水平距离之和。虽然这个值不一定意味着当前点到目标点的实际步数，但它可以为最佳优先搜索算法提供更有效的选择依据。

随着搜索的进行，算法开始尝试探索不同的点（即下图中带阴影的圆圈），每当遇到一个新点，都要将其添加到一个列表中等待之后进一步探索（即下图中带有虚线的圆圈）。在每次迭代中，算法将根据每个点的估值分数来选择最佳的那个点去探索。在这个例子中，每次将选择估值最小的那个点去探索。

一旦找到目标点，我们就可以终止搜索。在这个例子中，我们只需要探索一半多一点的点。例如，我们不会选择探索第二个距离为4的点，因为我们总是有一个更好的选择可以优先尝试。

在搜索中，我们必须先确定线索的优先顺序。根据具体情况，你可以从最新的线索或可信度最高的线索开始。无论如何，最佳优先搜索都需要按照某个优先顺序进行。