首页UCS代码

UCS代码

时间: 2025-05-01 14:33:09 浏览: 17

均匀代价搜索（Uniform Cost Search, UCS）的代码实现通常依赖于优先级队列（Priority Queue），因为我们需要总是选取目前发现的成本最低的节点进行扩展。下面是一个简单的 Python 版本示例，假设我们有一个带权重的无向图表示为字典形式： ```python import heapq def ucs(graph, start, goal): visited = set() # 创建集合存储已访问过的节点 queue = [(0, start)] # 初始化优先队列，元组的第一个元素代表当前路径消耗 while queue: (cost, node) = heapq.heappop(queue) if node not in visited: # 检查结点是否已经被访问过了 visited.add(node) if node == goal: # 判断如果达到了目标就直接输出结果然后结束函数运行 return cost for neighbor, edge_cost in graph[node].items(): # 遍历相邻节点 if neighbor not in visited: # 如果没被访问过就把对应信息加进堆里面等待下次迭代计算使用 total_cost = cost + edge_cost # 更新总的开销 heapq.heappush(queue,(total_cost,neighbor)) return float('inf') # 若没有找到，则返回无穷大作为标记 # 示例图结构 {node:{adjacent_node:edge_weight}} example_graph ={ 'A': {'B':1,'C':5}, 'B': {'A':1,'D':2,'E':6}, 'C': {'A':5,'F':4}, 'D': {'B':2}, 'E': {'B':6,'F':3,'G':7}, 'F': {'C':4,'E':3,'H':8}, 'G': {'E':7}, 'H': {'F':8} } print(ucs(example_graph,'A','H')) ``` 以上就是一个基本框架下的UCS伪码翻译成真实语言后的样子啦！

阅读全文