バックトラッキング - データサイエンス関連+αのメモ

バックトラッキング（Backtracking） は、再帰的に候補を構築しながら、制約を満たさないと判明した時点で引き返す（バックトラック）全探索の手法

純粋な全列挙と異なり、枝刈り（pruning） によって探索空間を大幅に削減できる

solve(状態):
    if 完成:
        結果を記録
        return
    for 候補 in 次の選択肢:
        if 候補が制約を満たす:
            状態に候補を追加
            solve(次の状態)      # 再帰
            状態から候補を除去   # バックトラック

例1: 部分和問題¶

整数のリストから、合計が目標値 target になる組み合わせをすべて列挙する

def subset_sum(nums: list[int], target: int) -> list[list[int]]:
    results = []

    def backtrack(start: int, current: list[int], remaining: int):
        if remaining == 0:
            results.append(current[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:  # 枝刈り（ソート済みなら以降も不要）
                break
            current.append(nums[i])
            backtrack(i + 1, current, remaining - nums[i])
            current.pop()  # バックトラック

    backtrack(0, [], target)
    return results


nums = sorted([3, 1, 4, 2, 6, 5])
print(subset_sum(nums, target=7))

例2: N-クイーン問題¶

$N \times N$ のチェスボードに、 $N$ 個のクイーンをお互いに攻撃し合わない配置をすべて列挙する

各行に必ず1つのクイーンを置く
列・斜めが重複しないかをチェックして枝刈り

def n_queens(n: int) -> list[list[int]]:
    """queens[row] = col: row行目のクイーンが置かれた列"""
    results = []
    queens = []
    cols = set()
    diag1 = set()  # row - col が同じ = 右下がり斜め
    diag2 = set()  # row + col が同じ = 右上がり斜め

    def backtrack(row: int):
        if row == n:
            results.append(queens[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # 枝刈り
            queens.append(col)
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            queens.pop()       # バックトラック
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return results


solutions = n_queens(6)
print(f'6-クイーンの解の数: {len(solutions)}')
print(f'最初の解 (列インデックス): {solutions[0]}')

例3: 順列生成（重複なし）¶

itertools.permutations と同じ結果を、バックトラッキングで実装する例

def permutations_bt(nums: list) -> list[list]:
    results = []
    used = [False] * len(nums)

    def backtrack(current: list):
        if len(current) == len(nums):
            results.append(current[:])
            return
        for i, num in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            current.append(num)
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return results


print(permutations_bt([1, 2, 3]))

枝刈りの重要性¶

バックトラッキングの効率は枝刈りの質で決まる

問題	枝刈りなし	枝刈りあり
8-クイーン	$8^8 = 16{,}777{,}216$	92解（探索ノード数は大幅削減）
部分和	$2^N$	目標超過で早期打ち切り

枝刈りのパターン:

実行可能性チェック: 現在の部分解が制約を満たさないなら即リターン
上界チェック: これ以上改善できないなら打ち切り（Branch and Bound）
対称性の除去: 等価な解を同一視して探索数を削減