IDA*算法

What · 是什么

IDA*（Iterative Deepening A*）是把迭代加深与 A* 结合的搜索算法：每次迭代做一次限阈值的 DFS，阈值是路径成本估计 f=g+h 而非深度。初始阈值取 h(起点)；DFS 中若某分支 f>阈值则剪掉并记录其最小超限值，迭代结束后阈值更新为该最小值继续下一轮。它结合了 A* 的启发剪枝与迭代加深的线性空间，不需要判重和排序，空间需求极小，适合 15数码、埃及分数等状态爆炸但路径不太长的问题。

Why · 为什么

How · 实现

伪代码

def IDA*(start):
    limit = h(start)
    while True:
        t = DFS(start, g=0, limit)
        if t == FOUND: return 解
        if t == INF: return 无解
        limit = t   # 阈值提升到最小超限值

def DFS(u, g, limit):
    f = g + h(u)
    if f > limit: return f        # 返回超限值
    if u == 目标: return FOUND
    nxt_min = INF
    for v in children(u):
        t = DFS(v, g+cost(u,v), limit)
        if t == FOUND: return FOUND
        nxt_min = min(nxt_min, t)
    return nxt_min

Python 实现

GOAL = "123804765"


def manhattan(state):
    """曼哈顿距离(可采纳启发)"""
    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):
    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 solvable(state):
    s = [int(c) for c in state if c != '0']
    inv = sum(1 for i in range(len(s)) for j in range(i + 1, len(s)) if s[i] > s[j])
    return (inv - 7) % 2 == 0  # 目标123804765逆序数为7(奇)


def ida_star(start):
    """IDA* 解8数码: 返回最少步数; 不可解返回 None"""
    if not solvable(start):
        return None
    limit = manhattan(start)
    found = [None]

    def dfs(u, g, prev):
        f = g + manhattan(u)
        if f > limit:
            return f          # 返回超限值用于提升阈值
        if u == GOAL:
            found[0] = g
            return -1         # FOUND 哨兵
        nxt_min = float('inf')
        for v in neighbors(u):
            if v == prev:
                continue      # 不走回头路(8数码中无意义)
            t = dfs(v, g + 1, u)
            if t == -1:
                return -1
            nxt_min = min(nxt_min, t)
        return nxt_min

    while True:
        t = dfs(start, 0, None)
        if t == -1:
            return found[0]
        if t == float('inf'):
            return None
        limit = t


if __name__ == "__main__":
    assert ida_star(GOAL) == 0
    r = ida_star("283104765")
    assert r is not None and r >= 0
    assert ida_star("123804756") is None  # 不可解

    # 与 BFS 对拍随机可解状态
    import collections, random
    def bfs_ans(start, maxd=25):
        if start == GOAL:
            return 0
        q = collections.deque([(start, 0)])
        seen = {start}
        while q:
            u, d = q.popleft()
            if d >= maxd:
                continue
            for v in neighbors(u):
                if v not in seen:
                    if v == GOAL:
                        return d + 1
                    seen.add(v)
                    q.append((v, d + 1))
        return None

    random.seed(7)
    tested = 0
    while tested < 30:
        s = GOAL
        for _ in range(random.randint(1, 10)):
            nb = list(neighbors(s))
            s = random.choice(nb)
        b = bfs_ans(s)
        if b is None:
            continue
        a = ida_star(s)
        assert a == b, (s, a, b)
        tested += 1
    print(f"idastar all tests passed ({tested} BFS-cross-validated)")

易错点

• 阈值更新必须取所有被剪分支的最小超限 f，否则可能漏解
• h 不乐观(高估)会误剪最优解
• DFS 需防环(8数码用不走回头路即可，一般问题需 visited 或路径判重)
• 'FOUND'与'无解'哨兵值要区分，勿混用
• 每轮重搜开销大，阈值增量与启发质量直接决定性能

例题

信源

• OI Wiki✓ https://oi-wiki.org/search/idastar/
• 书籍✓ CPH ch5 p58 (IDA* 相关: 迭代加深+剪枝)