一致代价搜索（Uniform Cost Search, UCS）是一种用于寻找最短路径的算法，特别适用于边权重不同的图。它通过优先队列来管理节点的访问顺序，始终选择当前代价最小的节点进行扩展。这种策略确保了算法能够找到从起点到终点的最低成本路径。与其他搜索算法不同的是，UCS并不依赖于启发式函数，而是单纯依据路径的实际累积代价来进行决策。
原理讲解：
- 初始化：设置起始点为当前节点，并将其代价设为零。
- 循环处理：每次选取当前代价最小的节点进行扩展，检查其所有邻接节点，计算到达这些节点的新代价，并将新节点加入优先队列中。
- 终止条件：当优先队列为空或找到目标节点时停止搜索。
代码实现：
```python
import heapq
def ucs(graph, start, goal):
priority_queue = [(0, start)]
visited = set()
cost_so_far = {start: 0}
while priority_queue:
current_cost, current_node = heapq.heappop(priority_queue)
if current_node == goal:
return cost_so_far[current_node]
if current_node not in visited:
visited.add(current_node)
for neighbor, weight in graph[current_node].items():
new_cost = cost_so_far[current_node] + weight
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
heapq.heappush(priority_queue, (new_cost, neighbor))
return "No path found"
示例图
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(ucs(graph, 'A', 'D')) 输出最短路径代价
```
这段代码展示了如何使用优先队列来实现一致代价搜索算法，从而在给定的图结构中找到从起点到终点的最低成本路径。🚀