a星算法 python

A*算法（A-Star Algorithm）是一种启发式搜索算法，常用于寻找两点之间的最短路径，特别是在图或网格环境中。它结合了迪杰斯特拉算法（Dijkstra）的基本思想（优先处理距离起点近的节点）和宽度优先搜索（BFS）的广度优先策略，同时引入了一个估价函数来估算每个节点到目标点的期望最短路径。

在Python中，你可以通过以下几个步骤来实现A*算法：

1. 定义数据结构：通常包括节点类，表示地图中的某个位置，包含当前位置、cost（已走的距离）、g_cost（从起点到当前节点的实际代价）、h_cost（从当前节点到目标的估计代价）等属性。

class Node:
    def __init__(self, position, g_cost=0, h_cost=0, parent=None):
        self.position = position
        self.g_cost = g_cost
        self.h_cost = h_cost
        self.parent = parent

2. 创建open_list（开放列表）和closed_list（关闭列表），分别存储待访问和已访问的节点。

3. 实现搜索函数，其中关键部分包括计算f_cost（总成本），选择下一个最优节点，并更新节点的状态。

def a_star_search(graph, start, end):
    open_list = [(start.f_cost, start)]
    closed_list = set()

    while open_list:
        current = min(open_list)[1]  # 选择f_cost最小的节点
        if current == end:
            return reconstruct_path(current)
        open_list.remove((current.f_cost, current))
        closed_list.add(current)

        for neighbor in graph.neighbors(current.position):
            if neighbor in closed_list:
                continue

            tentative_g_cost = current.g_cost + graph.cost(current.position, neighbor.position)
            if neighbor not in open_list or tentative_g_cost < neighbor.g_cost:
                neighbor.g_cost = tentative_g_cost
                neighbor.h_cost = heuristic(neighbor, end)  # 更新邻居的h_cost
                neighbor.parent = current
                open_list.append((neighbor.f_cost, neighbor))  # 将邻居加入开放列表

    return None  # 没有找到路径的情况

# heurisitic 函数，比如曼哈顿距离或欧几里得距离
def heuristic(a, b):
    return abs(a.position[0] - b.position[0]) + abs(a.position[1] - b.position[1])