A*算法的python实现

A*算法是一种常用的启发式搜索算法，用于在图形结构中找到最短路径。下面是A*算法的Python实现：

import heapq

def heuristic(node, goal):
    # 计算启发式函数（估计从当前节点到目标节点的代价）
    return abs(node - goal) + abs(node - goal)

def astar(graph, start, goal):
    # 初始化起始节点和开放列表
    open_list = []
    heapq.heappush(open_list, (0, start))
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while open_list:
        # 从开放列表中选择代价最小的节点
        current = heapq.heappop(open_list)

        if current == goal:
            break

        for neighbor in graph[current]:
            # 计算到邻居节点的新代价
 new_cost = cost_so_far[current] + graph[current][neighbor]
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                # 更新邻居节点的代价和父节点
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic(neighbor, goal)
                heapq.heappush(open_list, (priority, neighbor))
                came_from[neighbor] = current

    # 重构路径
    path = []
    current = goal
    while current != start:
        path.append(current)
        current = came_from[current]
    path.append(start)
    path.reverse()

    return path

# 示例图形结构
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

start = 'A'
goal = 'F'

path = astar(graph, start, goal)
print("最短路径:", path)