核心概念
一致代价搜索与 Dijkstra
每次扩展累计路径代价最小节点的最低代价路径搜索方法。
UCS Dijkstra 搜索 迪杰斯特拉算法 uniform cost search
简明解释
一致代价搜索（uniform-cost search，UCS）每次从优先队列取累计路径代价最小的节点；发现到同一状态更便宜的路径时要更新记录。Dijkstra 算法采用同一最小暂定距离原则。有限图中，配合非负边权与正确更新可求最低代价路径；负边不适用，目标也应在取出而非首次生成时接受。[1, Ch. 3, §3.4]
别和什么混淆
BFS 比较边数，UCS 比较累计权重；“一致代价”也不是说所有边代价相同。
在本书中
本页参考来源
- Russell S J, Norvig P. Artificial Intelligence: A Modern Approach [M]. Pearson, 2021. 定位：Ch. 3, §3.4. 稳定来源（访问 ）。