全探索 / 総当り法

全探索とは¶

全探索（Brute Force Search / 総当り法） は、解の候補をすべて列挙して答えを求める手法

シンプルで実装しやすく、バグが混入しにくい
$N$ が小さい問題や、まず正しい答えを確認したいときに使う
計算量が大きいため、 $N$ が大きい問題には向かない

計算量の目安¶

パターン	計算量	$N$ の上限の目安
線形探索	$O(N)$	10⁸ 程度
bit全探索（部分集合）	$O(2^N)$	$N \le 25$ 程度
組み合わせ $\binom{N}{k}$	$O\!\left(\binom{N}{k}\right)$	$N \le 30$ 程度（ $k$ 次第）
順列全列挙	$O(N!)$	$N \le 10$ 程度
再帰・バックトラック	$O(N!)$ 以下（枝刈り次第）	問題による

bit全探索¶

bit全探索（bit exhaustive search） は $2^N$ の組み合わせを探索する。 $N$ が小さければ実用可能

例えば「選ぶ」「選ばない」の2通りを $N$ 回判断するようなものを全パターン探索したいとする。
2通りは0 と 1 のbit (binary digit)で表すことができる。
$N=3$ として、全部「選ぶ」は111、全部「選ばない」は000、2回めだけ「選ぶ」なら010…のように表現していくことができる。
二進数を使うことで、これをすっきり表すことができる。

1 << N で、 $2^N$ を計算できる。例えば 1 << 3 で $2^3=8$ となる。

そこで、for i in range(1 << N) とすれば $2^N$ をループできる

N = 3
for mask in range(1 << N):
    print(f"10進数={mask}, 2進数={bin(mask)[2:].zfill(3)}")

10進数=0, 2進数=000
10進数=1, 2進数=001
10進数=2, 2進数=010
10進数=3, 2進数=011
10進数=4, 2進数=100
10進数=5, 2進数=101
10進数=6, 2進数=110
10進数=7, 2進数=111

N = 3
for mask in range(1 << N): # 2**Nのループ
    selected_indexes = []
    for i in range(N): # ビット列の各要素に対するループ
        if mask & (1 << i): # maskのi番目のbitが1なら、その要素を選ぶ
            selected_indexes.append(i)
    print(selected_indexes)

[]
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]

例：組み合わせ探索¶

値の集合valuesの要素を足し合わせた時、ある値 target と等しくなるかどうかを判定したいとする。

values = [1, 3, 5, 7, 9]
target = 16 # 目標の値

N = len(values)
for mask in range(1 << N): # 2**Nのループ
    result = 0
    for i in range(N): # ビット列の各要素に対するループ
        if mask & (1 << i): # maskのi番目のbitが1なら、その要素を選ぶ
            result += values[i]
    if result == target:
        print("Yes")
        break
else:
    print("No")

Yes

順列全列挙 $O(N!)$ ¶

N個の要素の並び方をすべて列挙する。itertools.permutations を使うと簡潔に書ける

典型的な用途：

訪問順序の最適化（小規模 TSP）
文字列の全アナグラム列挙
割り当て問題の全候補探索

from itertools import permutations

items = ['A', 'B', 'C']
for perm in permutations(items):
    print(perm)

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

from itertools import permutations

# 例: 4都市を最小コストで巡回する順序を求める（小規模 TSP）
# cost[i][j] = 都市i から都市j へのコスト
cost = [
    [0, 2, 9, 10],
    [1, 0, 6,  4],
    [15, 7, 0, 8],
    [6, 3, 12, 0],
]
n = len(cost)
cities = list(range(1, n))  # 都市0を起点として固定

min_cost = float('inf')
best_route = None

for perm in permutations(cities):
    route = (0,) + perm + (0,)  # 都市0 → ... → 都市0
    total = sum(cost[route[i]][route[i+1]] for i in range(len(route)-1))
    if total < min_cost:
        min_cost = total
        best_route = route

print(f'最小コスト: {min_cost}')
print(f'最適ルート: {best_route}')

最小コスト: 21
最適ルート: (0, 2, 3, 1, 0)

permutations の引数

permutations(iterable, r=None)

r を指定すると、 $r$ 個を選んで並べる順列（ $_N P_r$ ）を列挙できる
r=None（デフォルト）はすべての要素を並べる（ $N!$ 通り）

list(permutations([1, 2, 3], 2))
# → [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]  = 3P2 = 6通り

全探索とは¶

計算量の目安¶

bit全探索¶

例：組み合わせ探索¶

順列全列挙 O(N!)O(N!)O(N!)¶

順列全列挙 $O(N!)$ ¶