Day 152-Q1 | 反復深化A*探索（IDA*）

問題

$2$ 行 $3$ 列のスライドパズル（15パズルの縮小版、タイルは $1$〜$5$ と空白 $0$）が与えられる。空白は上下左右に隣接するタイルと1手で交換できる。目標盤面は次の通り（0が右下）:

1 2 3
4 5 0

与えられた初期盤面から目標盤面に到達するまでの最小手数を、IDA*（反復深化A*探索） で求めよ。ヒューリスティック関数にはマンハッタン距離（各タイルの現在位置と目標位置の行差・列差の絶対値の和、空白は除く）を用いること。入力は必ず解ける盤面のみが与えられる。

入力形式

a11 a12 a13
a21 a22 a23

制約

盤面は $0$〜$5$ の順列（$0$ が空白）

目標盤面に到達可能な盤面のみが与えられる

入出力例

入力例1

1 2 3
0 4 5

出力例1

入力例2

1 2 3
4 5 0

出力例2

概念図：閾値によるDFSの打ち切りと再挑戦

ヒント（段階的開示）

ヒント1（方向性）

A* はオープンリストに未展開ノードを全部持ち続けるからメモリを食う。IDA* は「$f=g+h$ がある閾値を超えたら打ち切る」という条件だけで深さ優先探索(DFS)を行い、見つからなければ閾値を上げてもう一度最初からやり直す。オープンリストという概念自体が要らない。

ヒント2（アプローチ）

初期閾値はスタート状態のヒューリスティック値 $h(\mathrm{start})$。1回のDFSの中で $f=g+h > \text{threshold}$ になった時点でそのノードを打ち切り、打ち切られた $f$ 値の最小値を記録する。DFSが解を見つけずに終わったら、その最小値を次の閾値にしてもう一度最初からDFSをやり直す。

ヒント3（誘導）

def search(g, threshold, avoid):
    state = path[-1]
    h = heuristic(state)
    f = g + h
    if f > threshold:
        return f          # 打ち切り。この f 値が次回閾値の候補
    if h == 0:
        return "FOUND"    # ゴール到達
    zero = state.index(0)
    min_next = float('inf')
    for new_state, dest in neighbors(state):
        if dest == avoid:  # 直前に来た場所へ戻る手は無駄なので飛ばす
            continue
        path.append(new_state)
        result = search(g + 1, threshold, zero)
        if result == "FOUND":
            return "FOUND"
        min_next = min(min_next, result)
        path.pop()
    return min_next

模範解答 (Python)

import sys

ROWS, COLS = 2, 3
GOAL = (1, 2, 3, 4, 5, 0)


def heuristic(state):
    h = 0
    for i, tile in enumerate(state):
        if tile == 0:
            continue
        goal_idx = tile - 1  # GOAL では tile の値がそのまま (idx+1)
        r1, c1 = divmod(i, COLS)
        r2, c2 = divmod(goal_idx, COLS)
        h += abs(r1 - r2) + abs(c1 - c2)
    return h


def neighbors(state):
    zero = state.index(0)
    r, c = divmod(zero, COLS)
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS:
            dest = nr * COLS + nc
            new_state = list(state)
            new_state[zero], new_state[dest] = new_state[dest], new_state[zero]
            yield tuple(new_state), dest


def ida_star(start):
    threshold = heuristic(start)
    path = [start]

    def search(g, threshold, avoid):
        state = path[-1]
        h = heuristic(state)
        f = g + h
        if f > threshold:
            return f
        if h == 0:
            return "FOUND"
        zero = state.index(0)
        min_next = float('inf')
        for new_state, dest in neighbors(state):
            if dest == avoid:
                continue
            path.append(new_state)
            result = search(g + 1, threshold, zero)
            if result == "FOUND":
                return "FOUND"
            if result < min_next:
                min_next = result
            path.pop()
        return min_next

    while True:
        result = search(0, threshold, -1)
        if result == "FOUND":
            return len(path) - 1
        if result == float('inf'):
            return -1
        threshold = result


def main():
    data = sys.stdin.read().split()
    grid = list(map(int, data[:6]))
    print(ida_star(tuple(grid)))


main()

Step-by-Step 解説

1入力例1をヒューリスティック値から追う
盤面 (1,2,3,0,4,5) は $h=2$（タイル4,5がそれぞれ1マスずれ）。閾値は最初2から始まる。

21回目のDFSで即座に見つかる
空白と4を交換 → $f=2\le2$。続けて5と交換でゴール到達、$h=0$。合計2手で"FOUND"。閾値の再設定は発生しない。

3閾値が上がるケースを実験
盤面 (2,4,3,1,5,0)（最短手数6）では $h(\mathrm{start})=4$ から始めるが1回目の閾値4では見つからず、2回目の閾値6でゴールが見つかる。実測では反復1で3ノード、反復2で10ノード、合計13ノードのみ展開（状態空間全体は $6!=720$）。

4閾値が4→6と2飛びで更新される理由（パリティ）
空白の位置を市松模様で塗り分けると状態遷移グラフは二部グラフになり、$f$値は常に2刻みでしか増えない。閾値が5を飛ばすのは実装ミスではなく必然。

よくあるミス

ミス	原因	正しい書き方
直前に来た場所へ戻る手を許してしまう	`avoid`を実装しない	空白の移動元を親から子へ渡し、次の一手で戻る手をスキップ
A*のようにグローバルな訪問済み集合を持つ	AとIDAの実装を混同	IDA*はDFSなので基本的にグローバルなvisitedは不要（`avoid`だけで十分）
閾値の更新に打ち切り値の最小ではなく最大や最後の値を使う	「次の閾値」の定義を誤解	今回届かなかった中で一番小さい$f$値を次の閾値にする
過大評価するヒューリスティックを使う	距離を大きめに見積もる関数を自作	マンハッタン距離は実際の最短手数以下が保証されたadmissibleな関数
打ち切り条件を`f >= threshold`にする	等号の向きの誤り	ちょうど$f=$thresholdは正当な探索対象なので`f > threshold`で打ち切る

次のステップ

発展: $3\times3$（8パズル、状態数 $9!/2=181440$）に拡張し、ノード展開数の増え方を実測してみる。
次回予告: アルファベータ枝刈り（Alpha-Beta Pruning）

自己評価

完全理解おおむね理解要復習

Day 152-Q1 — 反復深化A探索（IDA）

問題