25 用优先队列来解锁（第2/2页）

接下来，他通过负责安全屋警察的生日增加了六个可能的密码组，并赋予优先级8。他还添加了此时能记起的其他警察生日的密码组，并赋予优先级2。

最后，他添加了单词RUN并赋予优先级1。他知道，如果试到该项，就是时候放弃了，他必须找到另一个地方藏身。

现在优先队列中有32个密码组。需要把每个密码组都尝试一遍。在顶部是最高优先级的密码组：1-2-3。Frank试了一下，锁并没有开。

他大骂一声并把刚才尝试过的密码组从优先队列中删除，此时新的最高优先级的密码组便会自动出现在优先队列的顶部。

在尝试下一个密码组之前，Frank突然有个想法。他们会把旧密码做一些变化后再使用吗？他知道很多警察使用一个组合作为他们的储物柜的密码，并把这个密码颠倒一下作为行李箱的密码。负责安全屋的警察是否也会这样做？Frank把3-2-1这个密码组添加到他的优先队列的底部，并赋予优先级9。

1-1-2和1-3-5都不正确，所有优先级为10的密码组都尝试过了。Frank把它们颠倒后的密码组2-1-1和5-3-1也添加到优先队列的底部，并赋予优先级9。

Frank从优先队列顶部取出下一个优先级最高的密码组3-2-1。这是他刚刚添加的颠倒后的密码组之一。这正是优先队列的魔力，无论你以什么样的先后顺序去添加密码组，你总能得到队列当中优先级最高的那个。

锁开了，密码是5-3-1，密码组中优先级为9的一个。Frank缓缓地叹了一口气，瞥了一眼，没有Vinettee集团的迹象。他现在安全了。

警用算法导论：数据结构和搜索

节选自Drecker教授讲义

正如我们在整个学期的讲座中所讨论的，我们使用的数据结构可以影响算法的实现方式和效率。在深度优先搜索和广度优先搜索的讲义中，我们研究了栈和队列之间的差异，以及它们是如何影响搜索顺序的。在最佳优先搜索中，使用优先队列是数据结构影响算法效率的另一个很好的例子。

从概念上说，最佳优先搜索类似于广度优先搜索和深度优先搜索——在算法的每一步，都会选择一个新状态来进行探索。它们之间最关键的区别在于如何安排新产生的状态的探索次序。使用优先队列可以让我们每次都更有效地挑选出最接近目标解的状态。最佳优先搜索与优先队列是一对完美的组合，是一组极其高效的“数据结构+算法”的范例。