一、定义与核心思想

一致代价搜索（Uniform Cost Search, UCS） 是一种基于路径代价优化的图搜索算法，其核心思想是 "优先扩展当前累积代价最小的节点"。它在广度优先搜索（BFS）的基础上引入优先级队列，通过动态计算路径累积代价，确保每次选择最优路径分支。UCS常用于解决带权图的最短路径问题，尤其适用于边权重非负的场景。

二、算法流程

1. 初始化

   • 使用优先级队列（通常是最小堆）存储节点，初始时将起点加入队列（累积代价为0）。
   • 维护一个已访问节点集合，记录节点及其当前已知的最小累积代价。

2. 迭代扩展

   • 从队列中取出累积代价最小的节点作为当前节点。
   • 终止条件：若当前节点是目标，返回路径及总代价。
   • 否则，遍历当前节点的所有邻接节点：
     • 计算从起点到邻接节点的新累积代价（当前节点代价 + 边权重）。
     • 若邻接节点未访问过，直接加入队列。
     • 若邻接节点已在队列中且新代价更低，则更新队列中的节点代价。
     • 若邻接节点已访问且新代价更高，则忽略该路径。

3. 终止条件

   • 队列为空时表示无可行解。

示例（以城市路径搜索为例）：
从成都到石家庄的搜索中，UCS优先选择代价最低的路径分支（如成都→重庆→西安→郑州→石家庄，总代价201），通过优先级队列动态调整扩展顺序。

三、核心特性

特性	说明
数据结构	优先级队列（最小堆）管理节点，按累积代价排序
完备性	在有限状态空间且边权非负时总能找到解（若存在）
最优性	保证找到最小累积代价的路径（类似Dijkstra算法）
时间复杂度	O(b^(1+C/ε))，C为最优解代价，ε为最小边权
空间复杂度	O(b^(1+C/ε))，需存储所有可能路径分支

对比BFS：

• BFS按层扩展，UCS按代价扩展；BFS是UCS在边权相等时的特例。
• UCS可处理带权图，BFS仅适用于无权图。

四、应用场景

1. 带权最短路径问题
   • 交通导航（如最小时间/距离路径规划）
   • 物流运输中的成本最优路线计算
2. 资源优化分配
   • 通信网络中的最小带宽消耗路由
   • 电力系统的最经济输电路径
3. 游戏AI与机器人
   • NPC的智能寻路（避开高代价区域）
   • 机械臂运动规划中的能耗最小化

五、优缺点分析

优势：

• 严格最优性：在非负权重图中保证找到最小代价路径
• 动态适应性：通过优先级队列实时调整搜索方向
• 扩展性强：可作为A*算法的基础（加入启发式函数）

局限性：

• 效率问题：分支因子大或代价差异小时，时间复杂度接近BFS
• 负权重失效：存在负边权时可能无法终止或得到错误解
• 内存消耗：需存储所有已探索路径的代价信息

六、算法变体与改进

1. 启发式UCS：结合启发式函数h(n)引导搜索方向，演变为A*算法
2. 双向UCS：从起点和终点同时展开搜索，减少扩展节点数量
3. 增量式UCS：在动态变化图中局部更新路径代价（如实时交通调整）

七、总结

在人工智能领域，UCS是路径成本敏感型问题的核心算法之一，常与状态剪枝、启发式评估等技术结合，应用于自动驾驶、供应链管理等复杂系统的优化决策中。

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)