はじめに
アルゴリズムの基本にして最強の一手が 全探索（brute force / exhaustive search） です。「考えられる候補をすべて調べ上げ、条件を満たすものを見つける」という、もっとも素直な解法です。
派手さはありませんが、
- 確実に正解にたどり着ける（漏れがなければ必ず答えが出る）
- 実装がシンプルでバグりにくい
- 計算量さえ間に合えば、これで十分
という強みがあり、競技プログラミングでも実務でも「まず全探索で解けないか？」を考えるのが定石です。
本記事では、全探索の代表的な5パターンを Pythonのコード付き で整理し、それぞれの計算量と使いどころをまとめます。
対象読者
- 全探索という言葉は聞くが、種類や使い分けが整理できていない方
- 競技プログラミングを始めたばかりの方
- 「総当たり」を体系的に理解したい方
動作環境
| 項目 | バージョン |
|---|---|
| Python | 3.8 以上 |
TL;DR
本記事で扱う全探索のパターンは以下の5つです。
- 線形探索: 配列を先頭から全部見る。最も基本。計算量 $O(N)$
- 多重ループによる全列挙: 2つ・3つの組み合わせを総当たり。$O(N^2)$ など
- bit全探索: $N$ 個の要素の「選ぶ／選ばない」を全列挙。$O(2^N \times N)$
- 順列全探索: $N$ 個の並び順をすべて試す。$O(N! \times N)$
- DFS / BFS: グラフや状態空間を網羅的にたどる全探索。$O(V + E)$
$N$ がどのくらいまでなら間に合うか、という「計算量の感覚」も各セクションで触れます。これが全探索を使いこなす上で一番大事なポイントです。
パターン1: 線形探索（全部見る）
最も基本的な全探索です。配列やリストを先頭から末尾まで順に見て、目的の要素を探します。
def linear_search(arr, target):
"""target が見つかればそのインデックス、なければ -1 を返す"""
for i, value in enumerate(arr):
if value == target:
return i
return -1
numbers = [4, 2, 7, 1, 9, 3]
print(linear_search(numbers, 7)) # => 2
print(linear_search(numbers, 5)) # => -1
ポイント
- 計算量は $O(N)$。要素数 $N$ に比例します。
- データがソート済みなら二分探索（$O(\log N)$）の方が速いですが、ソートされていない・前処理する余裕がない場合は線形探索が素直です。
- 「最大値」「条件を満たす個数」なども、結局はこの全部見るループが基本になります。
scores = [40, 85, 60, 95, 70]
# 80点以上の人数を数える（全探索）
count = sum(1 for s in scores if s >= 80)
print(count) # => 2
# 最大値（全探索）
max_score = max(scores)
print(max_score) # => 95
パターン2: 多重ループによる全列挙
「2つの要素の組み合わせ」「3つの数の和」など、複数の要素の組をすべて調べたいときは多重ループを使います。
例: 2つの数の和が目標値になる組を探す
def has_pair_with_sum(arr, target):
"""2要素の和が target になる組が存在するか（全探索）"""
n = len(arr)
for i in range(n):
for j in range(i + 1, n): # i < j で重複を避ける
if arr[i] + arr[j] == target:
return (i, j)
return None
nums = [2, 7, 11, 15]
print(has_pair_with_sum(nums, 9)) # => (0, 1) (2 + 7)
print(has_pair_with_sum(nums, 100)) # => None
ポイント
- 2重ループは $O(N^2)$、3重ループは $O(N^3)$ になります。
- 内側ループを
range(i + 1, n)にすると、同じ組を2回数えたり同一要素を選んだりするのを防げます。
$O(N^2)$ は $N$ が大きくなると急激に遅くなります。目安として $N \leq 3000$ 程度までが現実的なライン。$N = 10^5$ では $10^{10}$ 回となり、まず間に合いません。その場合はハッシュ（set / dict）やソート＋二分探索で計算量を落とすことを検討します。
計算量を落とす例（参考）
同じ問題も、set を使えば $O(N)$ に改善できます。全探索で発想し、必要なら最適化する、という流れが王道です。
def has_pair_with_sum_fast(arr, target):
seen = set()
for value in arr:
if target - value in seen:
return True
seen.add(value)
return False
パターン3: bit全探索（部分集合の全列挙）
$N$ 個の要素それぞれについて「選ぶ／選ばない」の2択をすべて試したいときに使うのが bit全探索 です。各要素の選択状態を整数のビットに対応させ、$0$ から $2^N - 1$ までループします。
例: 部分集合の中で和が目標値になるものを探す
def subset_sum_exists(arr, target):
"""arr の部分集合のうち、和が target になるものがあるか"""
n = len(arr)
for bit in range(1 << n): # 0 〜 2^n - 1
total = 0
subset = []
for i in range(n):
if bit & (1 << i): # i番目のビットが立っていれば選ぶ
total += arr[i]
subset.append(arr[i])
if total == target:
return subset
return None
items = [3, 5, 7, 9]
print(subset_sum_exists(items, 12)) # => [3, 9]（または [5, 7]）
print(subset_sum_exists(items, 100)) # => None
ビット演算の対応イメージ
| bit（2進） | 選ばれる要素 | 和 |
|---|---|---|
0000 |
{} | 0 |
0001 |
{3} | 3 |
0011 |
{3, 5} | 8 |
1010 |
{5, 9} | 14 |
1111 |
{3, 5, 7, 9} | 24 |
-
1 << nは $2^n$ を意味します。 -
bit & (1 << i)で「$i$ 番目の要素を選んでいるか」を判定します。
計算量は $O(2^N \times N)$ です。$2^N$ は爆発的に増えるため、$N \leq 20$ 程度が実用上限の目安です（$2^{20} \approx 10^6$）。$N = 30$ なら $10^9$ を超え、厳しくなります。
パターン4: 順列全探索（並び順をすべて試す）
「$N$ 個のものを並べる順番」をすべて試したいときは順列全探索を使います。巡回セールスマン問題（最短で全都市を回る順番）などが典型例です。Pythonでは標準ライブラリ itertools.permutations を使うと簡潔に書けます。
例: 全都市を回る最短経路（総当たり）
from itertools import permutations
# 都市間の距離（対称行列）
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0],
]
def shortest_route(dist):
n = len(dist)
cities = range(1, n) # 都市0を出発点に固定
best = float("inf")
best_order = None
for perm in permutations(cities):
route = (0,) + perm + (0,) # 0 から出発して 0 へ戻る
total = sum(dist[route[i]][route[i + 1]] for i in range(len(route) - 1))
if total < best:
best = total
best_order = route
return best, best_order
print(shortest_route(dist)) # => (80, (0, 1, 3, 2, 0)) など
ポイント
-
permutations(cities)はcitiesのすべての並び替えを生成します。 - 出発点を1つ固定すると、$N!$ から $(N-1)!$ に減らせます（円順列の考え方）。
計算量は $O(N! \times N)$。階乗は爆発的に増えるため、$N \leq 10$ 程度が限界の目安です（$10! \approx 3.6 \times 10^6$）。それ以上は動的計画法（bitDP）などの工夫が必要になります。
パターン5: DFS / BFS（グラフ・状態空間の全探索）
グラフや盤面のように「状態がつながって広がっていく」対象を網羅的に調べるのが 深さ優先探索（DFS） と 幅優先探索（BFS） です。迷路の到達判定、連結成分の数え上げ、最短経路など応用が広い全探索です。
深さ優先探索（DFS）
行けるところまで進み、行き止まりになったら戻る（バックトラック）方式です。再帰で書くと自然です。
def dfs(graph, start):
"""start から到達できる頂点をすべて訪問する"""
visited = set()
def visit(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
visit(nxt)
visit(start)
return visited
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2, 4],
4: [3],
}
print(dfs(graph, 0)) # => {0, 1, 2, 3, 4}
幅優先探索（BFS）
近いところから順に層状に探索します。キュー（collections.deque）を使い、辺の重みがすべて等しいグラフの最短距離を求めるのに向いています。
from collections import deque
def bfs_shortest(graph, start):
"""start から各頂点への最短ステップ数を返す"""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
print(bfs_shortest(graph, 0)) # => {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
DFS と BFS の使い分け
| 観点 | DFS | BFS |
|---|---|---|
| データ構造 | スタック（再帰） | キュー |
| 得意なこと | 連結判定・全経路列挙・バックトラック | 最短距離（重みなし） |
| 探索順 | 深く潜る | 近い順に広がる |
| 計算量 | $O(V + E)$ | $O(V + E)$ |
$V$ は頂点数、$E$ は辺数です。
順列全探索やbit全探索も、実は「状態空間に対するDFS（バックトラック）」として書けます。DFSは全探索のもっとも汎用的な枠組みと言えます。
計算量の早見表
全探索を選ぶときは「候補の数」と「制限時間」を見積もるのが重要です。1秒あたり約 $10^8$ 回の計算が目安です。
| パターン | 計算量 | $N$ の目安 |
|---|---|---|
| 線形探索 | $O(N)$ | $10^8$ 程度まで |
| 多重ループ（2重） | $O(N^2)$ | $N \leq 3000$ 程度 |
| bit全探索 | $O(2^N \times N)$ | $N \leq 20$ 程度 |
| 順列全探索 | $O(N! \times N)$ | $N \leq 10$ 程度 |
| DFS / BFS | $O(V + E)$ | 頂点+辺で $10^6$〜$10^7$ 程度 |
全探索は「正しいが遅い」解になりがちです。まず全探索で正しい答えを出せるようにし、計算量が間に合わないと分かってから初めて、二分探索・動的計画法・貪欲法などの高速化を検討する、という順序がおすすめです。いきなり高度なアルゴリズムに飛びつくとバグの温床になります。
まとめ
本記事では、全探索の代表的な5パターンをPythonコードとともに整理しました。
特に重要なのは:
- まず 線形探索・多重ループ で「全部試す」発想を持つこと
- 部分集合は bit全探索、並び順は 順列全探索 という対応を覚えること
- グラフ・盤面は DFS / BFS で網羅すること
- 何より 計算量を見積もって、間に合うかを先に判断する こと
全探索は「確実に正解にたどり着く土台」です。ここを固めてから高速化を学ぶと、アルゴリズムの理解がぐっと進みます。
参考資料