A*算法

What · 是什么

A*（A-star）搜索是在带权有向图上求起点到终点最短路径的最佳优先搜索算法，是 BFS 的改进。它维护优先队列，每次取出 f(x)=g(x)+h(x) 最小的节点扩展，其中 g(x)=起点到 x 的实际距离，h(x)=x 到终点的距离估计。当启发函数可采纳（0≤h≤h*，即不高估真实距离）时，A* 保证找到最优解；当 h 一致（三角不等式）时每个节点只处理一次。8数码、k短路、机器人路径规划都是典型应用。

Why · 为什么

How · 实现

伪代码

# A* 主循环
open_heap = 优先队列, 按 f = g + h 排序
push (f(start), g=0, start)
came[start] = None

while open_heap 非空:
    u = pop 最小f
    if u == goal: 回溯输出路径
    for v in neighbors(u):
        ng = g[u] + w(u,v)
        if ng < g[v]:
            g[v] = ng
            came[v] = u
            push (ng + h(v), ng, v)

# 可采纳性要求: h(v) <= 真实距离(v->goal)
# 8数码启发: h = 曼哈顿距离和

Python 实现

import heapq

GOAL = "123804765"


def manhattan(state):
    """曼哈顿距离启发: 每个数字到目标位置的距离和
    可采纳且一致(8数码经典启发)
    """
    d = 0
    for i, ch in enumerate(state):
        if ch != '0':
            gi = GOAL.index(ch)
            d += abs(i // 3 - gi // 3) + abs(i % 3 - gi % 3)
    return d


def neighbors(state):
    """空格0与上下左右数字交换"""
    i = state.index('0')
    r, c = i // 3, i % 3
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            j = nr * 3 + nc
            lst = list(state)
            lst[i], lst[j] = lst[j], lst[i]
            yield ''.join(lst)


def inversion_count(state):
    s = [int(c) for c in state if c != '0']
    inv = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[i] > s[j]:
                inv += 1
    return inv


def solvable(state):
    """8数码可解性: 逆序数奇偶性与目标一致(空格移动不改变奇偶)"""
    return (inversion_count(state) - inversion_count(GOAL)) % 2 == 0


def a_star(start):
    """A* 解8数码: 返回(步数, 状态路径); 不可解返回 None
    目标 123804765
    """
    if not solvable(start):
        return None
    open_heap = [(manhattan(start), 0, start)]
    gscore = {start: 0}
    came = {start: None}
    while open_heap:
        _, g, u = heapq.heappop(open_heap)
        if g > gscore.get(u, float('inf')):
            continue  # 跳过过期条目
        if u == GOAL:
            path = []
            while u is not None:
                path.append(u)
                u = came[u]
            return g, path[::-1]
        for v in neighbors(u):
            ng = g + 1
            if ng < gscore.get(v, float('inf')):
                gscore[v] = ng
                came[v] = u
                heapq.heappush(open_heap, (ng + manhattan(v), ng, v))
    return None


if __name__ == "__main__":
    # 已就位: 0 步
    r = a_star(GOAL)
    assert r is not None and r[0] == 0

    # 经典可解实例
    r = a_star("283104765")
    assert r is not None and r[1][-1] == GOAL
    # 验证路径每一步合法且最短
    for a, b in zip(r[1], r[1][1:]):
        assert b in neighbors(a)

    # 不可解实例
    assert a_star("123804756") is None

    # 可解性判定抽查
    assert not solvable("123804756")
    assert solvable("283104765")

    print(f"astar all tests passed (sample path length: {r[0]})")

易错点

• h 必须可采纳(不高估)，否则 A* 失去最优性保证
• h 非一致(不满足三角不等式)时，节点可能重复入队，需按 g 松弛处理
• 弹出时若忘记跳过过期条目，可能用旧 g 值扩展导致错误
• 8数码无解状态(逆序奇偶不同)要先判定，否则 A* 无限搜索
• 状态哈希的编码开销在纯 Python 下可能成为瓶颈

例题

信源

• OI Wiki✓ https://oi-wiki.org/search/astar/
• 书籍✓ CPH ch25 (k shortest paths), 附录 A* 相关