バックトラッキング

バックトラッキング#

バックトラッキング（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))

[[1, 2, 4], [1, 6], [2, 5], [3, 4]]

例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]}')

6-クイーンの解の数: 4
最初の解 (列インデックス): [1, 3, 5, 0, 2, 4]

例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]))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

枝刈りの重要性#

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

問題

枝刈りなし

枝刈りあり

8-クイーン

\(8^8 = 16{,}777{,}216\)

92解（探索ノード数は大幅削減）

部分和

\(2^N\)

目標超過で早期打ち切り

枝刈りのパターン:

  • 実行可能性チェック: 現在の部分解が制約を満たさないなら即リターン

  • 上界チェック: これ以上改善できないなら打ち切り（Branch and Bound）

  • 対称性の除去: 等価な解を同一視して探索数を削減

Contents