Python 搜索算法：A* 启发式搜索（A* Search）

# /*
# Python 搜索算法：A* 启发式搜索（A* Search）
# --------------------------------------------------------
# 原理：
# A* 是一种结合了 “代价” 与 “启发式估计” 的最优搜索算法，
# 常用于地图寻路、路径规划、AI 决策等场景。
#
# 核心评分公式：
#     f(n) = g(n) + h(n)
#
# 其中：
# - g(n)：从起点到当前节点 n 的真实代价
# - h(n)：从 n 到目标节点的估计代价（启发函数）
# - f(n)：综合评分，决定搜索顺序
#
# A* 特点：
# - 若启发函数 h(n) 满足一致性（或可接受性），A* 能保证找到最优解
# - 启发函数越贴近真实距离，搜索越高效
# - 常用启发函数：
#       曼哈顿距离、欧几里得距离、切比雪夫距离等
#
# 本示例实现 A* 在网格地图中的寻路操作。
# 支持（上、下、左、右）四方向移动。
# --------------------------------------------------------
# */

import heapq

# --------------------------------------------------------
# 启发函数：曼哈顿距离（适用于四方向网格）
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# --------------------------------------------------------
# A* 主算法
def a_star_search(grid, start, goal):
    rows, cols = len(grid), len(grid[0])

    # open_list 使用最小堆：保存 (f, g, 当前节点)
    open_list = []
    heapq.heappush(open_list, (0, 0, start))

    # 记录代价、父节点
    g_cost = {start: 0}
    came_from = {start: None}

    # 四方向移动
    directions = [(0,1),(0,-1),(1,0),(-1,0)]

    while open_list:
        _, current_g, current = heapq.heappop(open_list)

        # 到达目标
        if current == goal:
            break

        for dx, dy in directions:
            nx, ny = current[0] + dx, current[1] + dy

            # 越界或障碍物跳过
            if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
                continue
            if grid[nx][ny] == 1:  # 1 表示障碍
                continue

            new_cost = current_g + 1  # 单步代价固定为 1

            if (nx, ny) not in g_cost or new_cost < g_cost[(nx, ny)]:
                g_cost[(nx, ny)] = new_cost
                f = new_cost + heuristic((nx, ny), goal)
                heapq.heappush(open_list, (f, new_cost, (nx, ny)))
                came_from[(nx, ny)] = current

    return came_from, g_cost

# --------------------------------------------------------
# 路径恢复
def reconstruct_path(came_from, start, goal):
    if goal not in came_from:
        return None
    path = []
    cur = goal
    while cur != start:
        path.append(cur)
        cur = came_from[cur]
    path.append(start)
    return path[::-1]

# --------------------------------------------------------
# 示例：0 表示可走，1 表示障碍物
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0]
]

start = (0, 0)
goal = (3, 4)

came_from, g_cost = a_star_search(grid, start, goal)
path = reconstruct_path(came_from, start, goal)

print("最短路径：", path)
print("总代价：", g_cost.get(goal))

# --------------------------------------------------------
# 输出示例：
# 最短路径： [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (3, 4)]
# 总代价： 7
#
# 要点总结：
# 1) A* = Dijkstra + 启发式函数；
# 2) g(n) 表示真实代价，h(n) 给出估计，f(n) 决定扩展顺序；
# 3) 曼哈顿距离适合四方向网格，欧几里得适合斜向；
# 4) 启发函数要“可接受”以保证最优解；
# 5) A* 搜索效率比 BFS、Dijkstra 更高（在合理启发下）。
# */