全探索（完全探索）を極める：基礎から実践的最適化まで
エバープレイ編集部全探索とは何か
全探索（ぜんたんさく）、別名「完全探索」や英語の“brute-force search”は、問題の解候補を可能な限り全て調べて正解を見つけるアルゴリズム設計の基本手法です。小規模な入力や条件が厳密に定義されている場合には確実で実装が簡単なため有用ですが、組合せ爆発により入力サイズが増えると計算量が急増します。全探索は単純な線形探索から、全順列・全部分集合の列挙、状態空間の深さ優先・幅優先探索、再帰的バックトラックまで多様な形態を含みます。
基本的な分類と具体例
線形探索（Linear search）: 配列の各要素を順番に見る最も基本的な全探索。時間計算量はO(n)。
全順列列挙: n要素の全順列はn!通り。例えばnext_permutationを使う手法は実装が簡便だが、nが大きいと現実的でない。
全部分集合列挙（ビットマスク列挙）: n要素の部分集合は2^n通り。ビット演算を使うと効率的に実装できる。
全マッチング・全色彩・全配置問題: グラフや盤面上の配置を全通り試す。チェスのナイト巡回やナップサックの全選択など。
計算量の見積もりと現実的な扱い
全探索のキーは解空間の大きさを事前に見積もることです。例えば順列はn!、部分集合は2^n、各要素にk通りの値を割り当てる問題はk^nの候補数になります。現代のCPUや実装最適化を加味しても、2^40や40!のような規模は現実的ではありません。したがって実用ではn≤20〜30あたりを境に工夫が必要になります。
全探索を現実的にするテクニック
枝刈り（Pruning）: 部分解が最終解に到達し得ないと判明した時点で探索を打ち切る。バックトラックと組み合わせて強力です。制約充足問題（CSP）でよく用いられます。
分枝限定法（Branch and bound）: 最適化問題で、現在の部分解の下界・上界を計算し、最良解へ到達しない枝を切る。組合せ最適化で有効。
メモ化／動的計画法（Memoization/DP）: 同じ部分問題を何度も解く場合に結果を保存して再利用する。サブセットDPやビットマスクDP が代表例で、時間を指数関数的から多項式×2^nなどへ改善できます。例えばTSPのHeld–Karp法はO(n^2 2^n)時間・O(n 2^n)空間です。
ミート・イン・ザ・ミドル（Meet-in-the-middle）: 探索空間を半分に分割し、両側の中間結果を組み合わせる。2^nを2×2^{n/2}に変えることで計算コストを大幅に下げられる場合があります。典型例は部分和問題や某種の列挙問題です。
対称性の利用: 対称性により解空間の同値クラスをまとめることで無駄な探索を減らします。例えば盤面の回転・反転を同一視するなど。
ビット演算の活用: 部分集合列挙や集合演算をビットで表すと演算が高速になり、メモリ効率も改善します。Gosperのハックで同じビット数の組み合わせを次へ進める方法などがあります。
早期終了と上限の活用: 最良解の上限値や閾値があれば、閾値以下になると判定できる枝は切れるため効率化できます。
実践的なアルゴリズム応用
全探索は競技プログラミングや小規模な最適化問題、暗号の総当たり攻撃など幅広く使われます。例を挙げると：
ナップサック問題: 重さの上限Wが小さい場合はDPが有効だが、nが小さい場合は全選択（2^n）を試して解くことが簡潔で確実です。
巡回セールスマン（TSP）: 小規模nであれば全順列（O(n!)）で解けるが、一般にはHeld–Karp法などのDPを使うのが現実的。
SAT ソルバー: DPLLやCDCLは論理式に対する「賢い全探索」とも言えます。分岐や学習（クラウズ学習）で大幅に探索を削減します。
暗号解析: 鍵長が短ければブルートフォースで試行され、強度評価の指標となります。現代の暗号はブルートフォースが非現実的になるよう設計されています。
並列化とハードウェア活用
全探索は独立した候補の評価が多く、並列化が容易です。マルチコアCPU、クラスタ、GPUで分散して試行することで実行時間を線形近く短縮できます。ただし、同期や結果集約、メモリ共有、ロードバランスの設計が重要になります。GPUではブランチの多い探索はスレッド効率が悪くなるため、ビット演算や大量の同一処理を要する場面で効果的です。
限界と代替手法
全探索は最悪ケースで指数時間かそれ以上になるため、入力が大きい問題やNP完全問題では現実的でない場合が多いです。代替としては近似アルゴリズム、メタヒューリスティクス（遺伝的アルゴリズム、シミュレーテッドアニーリング、局所探索）、確率的手法、分散最適化などが使われます。これらは厳密解を保証しない代わりに大規模問題に対して実用的な解を短時間で提供します。
実装上の注意点とベストプラクティス
入力の前処理で明らかな不適合を排除する。これだけで探索空間が劇的に減ることが多い。
探索順序を工夫する。より有望な枝を先に探索することで早期に良い上界を得られ、枝刈りが効きやすくなります。
メモリと計算のトレードオフを評価する。メモ化により時間を稼げるがメモリ消費が増える場合がある。
再帰の深さやスタック使用に注意する。深い再帰はスタックオーバーフローの原因になるため、必要なら反復実装へ切り替える。
言語選択: C/C++は速度面で有利。Pythonなど高級言語はプロトタイピングに向くが、ホットスポットはC拡張やビット演算で最適化が必要。
全探索と計算理論
全探索は計算複雑性理論でも重要な位置を占めます。NP問題の定義は「与えられた解が多項式時間で検証できる問題」であり、全探索はこれらの問題に対する最も単純な解法を示します。NP完全問題に対しては、現時点で一般的に多項式時間の決定的アルゴリズムは知られていないため、全探索や改良版を用いるか、近似・ランダム化手法を選ぶことになります。
まとめ：全探索を使うべきかどうか
全探索は理解しやすく実装が簡潔であるため最初に検討すべき手法です。しかし、問題サイズや要求される性能に応じて枝刈り、DP、ミート・イン・ザ・ミドル、並列化、あるいは近似アルゴリズムへの移行を考える必要があります。設計時には解空間の大きさを見積もり、対称性や制約を活用して探索を可能な限り小さくすることが重要です。
参考文献
投稿者プロフィール
最新の投稿
カメラ2025.12.23単焦点レンズ徹底ガイド：特徴・選び方・撮影テクニックとおすすめ- カメラ2025.12.23写真機材ガイド：カメラ・レンズ選びから運用・メンテナンスまでの完全解説
- カメラ2025.12.23交換レンズ完全ガイド：種類・選び方・性能解説と実践テクニック
- カメラ2025.12.23モノクロ写真の魅力と技術──歴史・機材・表現・現像まで深堀りガイド
