ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > python中如何实现 A* 算法求最短路径？

python中如何实现 A* 算法求最短路径？

原创 Python 作者：mingtian66 时间：2024-11-12 12:21:51 0 删除 编辑

在 Python 中实现 A* 算法，可以使用优先队列（通常是 heapq 模块）来帮助管理候选节点的扩展顺序。下面是一个示例代码，计算从起点到终点的最短路径。

假设我们在一个 2D 网格上实现 A* 算法，其中 0 表示可以通行的节点，1 表示障碍。
代码示例

import heapq

def astar(grid, start, goal):
    # 定义一个计算曼哈顿距离的启发式函数
    def heuristic(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
    
    # 初始化起始节点的 `g` 值
    open_set = []
    heapq.heappush(open_set, (0, start))
    
    # 用于存储每个节点的 g 值和路径
    g_costs = {start: 0}
    came_from = {start: None}
    
    while open_set:
        # 从优先队列中取出 `f` 值最小的节点
        _, current = heapq.heappop(open_set)
        
        # 如果到达终点，重建路径并返回
        if current == goal:
            path = []
            while current:
                path.append(current)
                current = came_from[current]
            return path[::-1]  # 返回从起点到终点的路径
        
        # 遍历当前节点的邻居
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            neighbor = (current[0] + dx, current[1] + dy)
            
            # 检查邻居是否在网格范围内且没有障碍
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == 0:
                # 计算邻居节点的 g 值
                tentative_g_cost = g_costs[current] + 1
                
                # 如果这是一个更优的路径
                if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
                    g_costs[neighbor] = tentative_g_cost
                    f_cost = tentative_g_cost + heuristic(neighbor, goal)
                    heapq.heappush(open_set, (f_cost, neighbor))
                    came_from[neighbor] = current
    
    # 如果没有找到路径，返回空列表
    return []

# 测试网格（0 表示可通行，1 表示障碍）
grid = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

# 起点和终点
start = (0, 0)
goal = (4, 4)

# 运行 A* 算法
path = astar(grid, start, goal)
print("最短路径:", path)

代码说明

    启发式函数 heuristic(a, b)：计算曼哈顿距离，用于估计当前节点到目标节点的距离。
    Open Set open_set：使用 heapq 优先队列存储候选节点，根据 f = g + h 值排序。
    g_costs：记录每个节点从起点到该节点的最小代价 g 值。
    came_from：记录路径信息，用于回溯找到完整路径。
    邻居检查：每次从当前节点扩展到周围的邻居节点。

结果

代码输出从 start 到 goal 的最短路径，路径以节点坐标列表的形式返回。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048461/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： try-with-resources 语句是如何工作的？
下一篇： Python 中如何实现动态规划？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603012

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593