伯克利帕克曼项目1中的“UniformCostSearch”

以下是一个使用Python实现Uniform Cost Search算法的示例代码：

from queue import PriorityQueue

class Node:
    def __init__(self, state, cost, parent=None):
        self.state = state
        self.cost = cost
        self.parent = parent

    def __lt__(self, other):
        return self.cost < other.cost

def uniform_cost_search(start_state, goal_state, graph):
    visited = set()
    queue = PriorityQueue()
    queue.put(Node(start_state, 0))

    while not queue.empty():
        current_node = queue.get()
        current_state = current_node.state

        if current_state == goal_state:
            path = []
            while current_node.parent:
                path.append(current_node.state)
                current_node = current_node.parent
            path.append(start_state)
            path.reverse()
            return path

        visited.add(current_state)

        for neighbor, cost in graph[current_state]:
            if neighbor not in visited:
                queue.put(Node(neighbor, current_node.cost + cost, current_node))

    return None

# 示例使用
graph = {
    'A': [('B', 1), ('C', 3)],
    'B': [('D', 5), ('E', 2)],
    'C': [('F', 4)],
    'D': [('G', 6)],
    'E': [('G', 1)],
    'F': [('G', 3)],
    'G': []
}

start_state = 'A'
goal_state = 'G'

path = uniform_cost_search(start_state, goal_state, graph)
print(path)

上述代码使用了优先队列来实现Uniform Cost Search算法。Node类表示图中的节点，其中包含状态、成本和父节点。算法维护了一个访问过的节点集合visited和一个优先队列queue，队列中的元素按照成本的优先级排序。

在算法的主循环中，每次从队列中取出成本最小的节点，如果该节点的状态与目标状态相等，则说明找到了一条路径，将路径返回。否则，将该节点标记为已访问，并遍历与该节点相邻的未访问节点，将它们加入队列中。

最后，如果队列为空而没有找到目标状态，则说明无法到达目标状态，返回None。

示例中的graph是一个字典，表示图的邻接表。每个节点用字母表示，与它相邻的节点及其对应的边的成本以列表的形式存储。在示例中，A、B、C、D、E、F、G分别表示图中的节点，它们之间的连接关系及边的成本如注释所示。

运行上述代码将会输出从起始状态A到目标状态G的最短路径，即['A', 'B', 'E', 'G']。