基于python的A星算法

A星算法是一种常用于寻路问题的启发式搜索算法，下面是基于Python实现的A星算法的代码示例：

import heapq

class AStar:
    def __init__(self, graph):
        self.graph = graph

    def heuristic(self, node, goal):
        # 计算启发函数值，这里使用曼哈顿距离
        return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

    def search(self, start, goal):
        # 初始化起点和终点的节点
        start_node = (start, 0)
        goal_node = (goal, float('inf'))

        # 初始化open集合和closed集合
        open_set = []
        closed_set = set()

        # 将起点加入open集合
        heapq.heappush(open_set, start_node)

        while open_set:
            # 取出open集合中f值最小的节点
            cur_node = heapq.heappop(open_set)

            # 如果当前节点是终点，直接返回结果
            if cur_node[0] == goal_node[0]:
                return cur_node[1]

            # 将当前节点加入closed集合
            closed_set.add(cur_node[0])

            # 遍历当前节点的所有邻居节点
            for neighbor in self.graph[cur_node[0]]:
                # 如果邻居节点已经在closed集合中，跳过
                if neighbor in closed_set:
                    continue

                # 计算邻居节点的g值和f值
                g = cur_node[1] + self.graph[cur_node[0]][neighbor]
                h = self.heuristic(neighbor, goal)

                # 如果邻居节点不在open集合中，将其加入open集合
                # 否则，如果邻居节点已经在open集合中，且新的g值更小，更新其g值和f值
                neighbor_node = (neighbor, g)
                if neighbor_node not in open_set:
                    heapq.heappush(open_set, neighbor_node)
                elif g < neighbor_node[1]:
                    open_set.remove(neighbor_node)
                    heapq.heappush(open_set, neighbor_node)

        # 如果open集合为空，表示没有找到合适的路径，返回None
        return None

该代码中的graph是一个字典类型的邻接表，表示图中每个节点的邻居节点和对应的边权重。例如，一个包含4个节点的图可以表示为：

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}
}

在调用AStar类的search方法时，需要传入起点和终点的坐标。例如，对于上述图中的起点A和终点D，可以调用：

a_star = AStar(graph)
path_length = a_star.search('A', 'D')

该方法会返回起点到终点的最短路径长度，如果没有找到合适的路径，则返回None。