Uniform Cost Search (UCS)

BFS用于找到每个边的权值是一样的图的最短路径，如果图中每个边的权值不一样了，就用到了UCS。 参考了https://blog.csdn.net/jdh99/article/details/80872364 算法思路： 1.数据结构 frontier: 优先队列，用来存储到达当前顶点花费的代价，这里的代价是目前最小的代价，后面如果有到达该点的更短路径，则更新这个代价。探索点的时候，每次都从这个优先队列里面挑出那个代价最小的点，然后扩展该点。 explored：用一个数组来存储就行，存放的是已经探索过的点。 father：数组，用来存储当前点的父节点是谁，以便用于找到这个路径，如果不需要求路径， **Uniform Cost Search (UCS)** 是一种在有向或无向图中寻找最短路径的搜索算法，尤其适用于边的权值不均等的情况。它基于广度优先搜索（BFS）策略，但通过优先队列（通常是二叉堆）来优化路径选择，确保始终沿着最低成本的路径前进。 **算法思想：** 1. **数据结构：** - **Frontier（前沿）**：使用优先队列（如二叉堆）存储待探索的节点，其中每个节点包含其到起点的累计代价。每次从前沿中取出代价最小的节点进行扩展。 - **Explored（已探索）**：数组记录已经访问过的节点，避免重复访问。 - **Father（父节点）**：数组记录每个节点的父节点，用于回溯找到最短路径。如果仅关心最短路径长度，可以省略此数组。 **算法流程：** 1. **初始化**：将起点加入前沿，代价设为0。将起点标记为已探索。 2. **循环**： - **选择节点**：从前沿中取出代价最小的节点A。 - **检查目标**：如果节点A是目标节点，算法结束，返回最短路径（根据father数组）或最短路径长度。 - **扩展节点**：对于节点A的每个未探索邻居B，计算从起点到B的新代价（A的代价加上A到B的边的权重）。如果B已在前沿中，比较新代价和旧代价，取较小者并更新B的代价和父节点。然后将B加入前沿。 - **终止条件**：若前沿为空，表示没有到达目标的路径；否则，继续下一轮循环。 **示例**： 假设我们有一个图，起点A，终点C，边的权重如下： - A -> D：2 - A -> B：3 - D -> C：5 - D -> E：1 - B -> E：2 - E -> C：4 初始状态：A加入前沿，cost为0。 1. 拿出A，放到已探索，探索A的邻居D和B，D的cost为2，B的cost为3，都加入前沿。 2. D是cost最小的点，放到已探索，探索D的邻居C和E，C的cost为7，E的cost为3，C加入前沿，E替换D的位置。 3. E是cost最小的点，放到已探索，发现C的cost可以更新为7（E + 4 < D + 5），更新C的cost和父节点。 4. C是cost最小的点，且是目标节点，最短路径为7。 **ucs总结：** UCS 是一个有效寻找图中最小代价路径的算法，尤其在边的权值不均匀时。通过优先队列管理待探索节点，它保证了优先扩展代价最低的路径，从而找到全局最优解。与BFS相比，UCS在非均匀代价图中提供了更好的性能。在实际应用中，如机器人路径规划、网络路由等问题中，UCS都能发挥重要作用。