全探索 / 総当り法

全探索 / 総当り法#

全探索とは#

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

  • シンプルで実装しやすく、バグが混入しにくい

  • \(N\) が小さい問題や、まず正しい答えを確認したいときに使う

  • 計算量が大きいため、\(N\) が大きい問題には向かない

計算量の目安#

パターン

計算量

\(N\) の上限の目安

線形探索

\(O(N)\)

\(10^8\) 程度

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!)\) 以下（枝刈り次第）

問題による

Note

競技プログラミングでは \(10^8\) 操作/秒が目安。制約を見て計算量を見積もってから手法を選ぶ

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通り
Contents