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

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

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

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

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

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