考虑下图表示搜索空间的图表。
如果我们从并尝试达到目标状态，最低成本优先搜索（LCFS）（又名统一成本搜索）算法无法找到解决方案。这是因为，选择超过扩展为.是节点的成本函数， 和是到达节点的成本从开始状态。进一步，从, LCFS 现在将选择展开，这反过来将选择再次结束. 这会导致无限循环。这表明 LCFS 是不完整的（不保证找到解决方案，如果存在的话）。
对于 A*，我们定义， 在哪里是从节点到达目标状态的预期成本. 如果我们定义曼哈顿距离（规范）为，书籍（如Stuart Russell 和 Peter Norvig 的《人工智能：现代方法》（第 3 版））说 A* 一定会找到解决方案（因为它存在）。但是，我找不到如何。用一个*，仍然会选择自从. 你看，这意味着，当向后扩展,将再次选择, 无限循环随之而来。
我在这里想念什么？
您忘记计算并考虑实际路径的成本。您忘记累积多次前进和后退的边缘成本！
统一成本搜索（UCS）的评估函数是， 在哪里表示从起始节点到路径的成本. A* 的评价函数为， 在哪里是一个可接受的启发式。UCS 是 A* 的一个特例，具有可接受的启发式. 评估函数用于从边缘中选择下一个要访问的节点，即可能被访问的节点集合。每当我们访问一个节点时，我们都会将其从边缘移除。展开节点_意味着添加的孩子到边缘。每当您访问一个节点时，您也会将其展开。
让我们将 UCS 应用于您的具体示例。最初，我们检查是否是否是目标节点。不是，所以我们展开. 我们可以添加访问（或扩展）节点列表（图搜索）或不访问（树搜索）。让我们使用树搜索，这样我们就不会跟踪展开的节点，这意味着我们可以多次展开一个节点。有两个孩子，和，所以我们将它们添加到边缘，. 我们现在应该访问或者? 我们将访问评估函数的最小值，即， 鉴于，所以我们删除从现在的边缘. 是目标节点？不，所以我们扩展它，但它只有一个孩子，，所以我们添加到边缘，所以. 到达路径的成本先去然后到是（假设您在同一条边上来回前进，因此您需要累积这些行程的成本！）和，所以我们访问，所以我们将它从边缘移除，现在是.
您应该能够完成剩余的搜索（我实际上还没有完成）。我建议您观看 John Levine 的视频Uniform Cost Search，他展示了 UCS 和 A* 如何工作的具体示例。