- bit全探索は、N個のものからいくつか選ぶ全パターンを、0から2^N-1までの整数に1対1対応させて列挙する手法です。
- 整数のインクリメントがそのまま「次の選び方への移動」になるので、パターンを実体として保存せずに全列挙できます。
- N=20前後までの制約に限られますが、その範囲では実装がシンプルで、メモリを節約しながら全パターンを走査できます。
1. bit全探索で解く
N個のものからいくつかを選ぶ、という設定の問題を全探索で解きたい場面があります。
たとえば次のような問題です。
部分和問題
N個の正の整数 A と、正の整数 W が与えられます。
A の中から何個か選んで総和を W にできるかどうかを判定してください1。
制約: N ≤ 20
1.1. Common Lisp 実装
「まったく選ばない」から「全部選ぶ」まで、取りうる選び方は 2^N 通りあります。
これをすべて調べ上げるのがbit全探索で、N=3 なら 8通り、N=20 なら約100万通りをビットパターンで表します2。
(defun bit-to-list (bit)
(declare (type fixnum bit))
(loop for i below (integer-length bit)
when (logbitp i bit)
collect i))
(defun subset-sum (a bit)
(declare (type vector a)
(type fixnum bit))
(loop for n in (bit-to-list bit)
sum (aref a n)))
(defun subset-sum-p (a w)
"A の部分集合の総和が W になるか判定する。"
(declare (type vector a)
(type fixnum w))
(let ((n (length a)))
(loop for bit from 0 below (ash 1 n)
thereis (= w (subset-sum a bit)))))Code language: Lisp (lisp)bit-to-listのループは、bit が表す選び方で、整数値から何番目の要素を取るかのリストを作ります。subset-sum-p のループは、2^N通りのパターンを走査し、thereis で条件を満たす要素が見つかった時点でループを抜けて t を返します3。
(subset-sum-p #(3 1 4 8 5) 2) ;=> NIL
(subset-sum-p #(3 1 4 8 5) 9) ;=> T （4+5 または 3+1+5 など）Code language: Lisp (lisp)ただし、bit-to-listでリストを生成するのは、いまいち計算効率が悪いです。
デバッグや、「どのアイテムを選んだか」を後続の処理に渡したい場合には有効ですが、実際の問題では、この変換を挟まずに logbitp でその場で判定しながら計算する実装のほうがシンプルです。
(defun subset-sum/real (a bit)
(declare (type fixnum bit)
(type vector a))
(loop for i below (length a)
when (logbitp i bit)
sum (aref a i)))Code language: Lisp (lisp)2. なぜ整数でパターンを表せるか
bit全探索の考え方は、要素の選び方の整数に対応させることです。
たとえば、N=3（アイテムが {0, 1, 2} の3個）の場合、選び方と整数の対応は次のようになります。
選び方 ビット列 整数
{} 000 0
{0} 001 1
{1} 010 2
{0,1} 011 3
{2} 100 4
{0,2} 101 5
{1,2} 110 6
{0,1,2} 111 7「アイテム i を選ぶ」を i ビット目が 1、「選ばない」を 0 として、ビット列を10進数に直した値が対応する整数です。
この方法のメリットは、0から2^N-1まで整数をインクリメントするだけで、全2^N通りの選び方を過不足なく走査できることです。
(loop for bit below (ash 1 n) do
...)Code language: Lisp (lisp)ash は算術シフト演算子で、(ash 1 n) は 1 を n ビット左にシフトして 2^N を計算します4。
パターンをリストとして生成してからループに渡す必要がなく、整数のインクリメントが直接「次の選び方への移動」になっています。
2.1. 整数からパターンへの読み取り
整数 bit が「どの選び方を表しているか」を読み取るには、i ビット目が立っているかどうかを確認します。
Common Lispでは logbitp が使えます5。
(logbitp i bit) ; i ビット目が 1 なら t、0 なら nilCode language: Lisp (lisp)たとえば、bit = 13（2進数で 01101） の場合で確認します。
i (logbitp i 13) 意味
0 t アイテム0を選ぶ
1 nil アイテム1を選ばない
2 t アイテム2を選ぶ
3 t アイテム3を選ぶ
4 nil アイテム4を選ばないつまり、A0+A2+A3を計算すればよいことになります。
3. 計算量と使いどころ
bit全探索はパターンを実体として保存しないので、整数1つ分しか追加のメモリを使いません。
仮に全2^Nパターンをリストで保存しようとすると、N=30で10億エントリになり現実的ではありません。
整数のインクリメントで列挙することが、ここでは必要条件になっています。
しかし、計算量は O(2^N × N) です。
2^N通りのパターンそれぞれに対して、N個のアイテムを確認するコストがかかります。
N=20 で約2000万回の操作になります6。
これが現実的な上限で、N=30 を超えると時間的に厳しくなります。
Nが大きい場合に計算量を下げたいなら、動的計画法が候補になります。
部分和問題であれば、DP で O(N × W) に抑えられます7。
4. まとめ：なぜ整数で表すのか
bit全探索の核心は、「N個からいくつか選ぶ2^N通りの選び方」と「0から2^N-1の整数」を1対1対応させる点にあります。
この対応があると、整数のインクリメントが全パターンの走査になり、logbitp で各アイテムの選択状態をその場で読み取れます。
パターン生成と列挙が一体化するので、実装が短くなりバグも減ります。
手法として特別なことはしていませんが、「どこを決めれば全体が決まるか」という視点は、制約が大きい問題でも探索範囲を絞るための出発点になります。
- 部分和問題はNP完全であることが知られており、入力数値が十分大きい場合に多項式時間で解くアルゴリズムは存在しないとされています。ただし入力が小さい場合には動的計画法で擬多項式時間（O(N×W)）での解が可能です。 – 部分和問題 – Wikipedia
- 2^20 の正確な値は 1,048,576 です。N=25 では約3,355万、N=30 では約10億7,374万となり、N=30前後でメモリと時間の両方で現実的な限界を超えます。
thereisはCommon Lispのloopマクロが持つ終了テスト節のひとつです。指定した式が非 nil を返した時点でループを打ち切り、その値を返します。対応する節としてalways（すべてが真ならt）とnever（すべてが偽ならt）があります。 – CLHS: Macro LOOPash（Arithmetic Shift）はCommon Lispの組み込み関数です。正の数を指定すると左シフト（乗算方向）、負の数を指定すると右シフト（除算方向）になります。(ash 1 n)は2^nを整数として返します。 – CLHS: Function ASHlogbitpはCommon Lispの組み込み関数で、第1引数にビット位置（0が最下位）、第2引数に整数を取ります。負の整数は2の補数表現として扱われます。C++の(bit >> i) & 1に相当します。 – CLHS: Function LOGBITP- 正確には 2^20 × 20 = 20,971,520 回です。AtCoderの多くの問題では 1秒あたり 10^8 回程度の演算が目安とされており、N=20 は余裕を持って収まります。N=25 では約6.7億回となり、時間的に厳しくなります。
- DP以外に「半分全列挙（Meet in the middle）」という手法もあります。N個の要素をN/2ずつ2グループに分けてそれぞれbit全探索し、結果を二分探索で突き合わせることで、O(2^N) を O(N × 2^(N/2)) に削減できます。N=40程度まで対応できます。 – 半分全列挙による全探索の高速化 | アルゴリズムロジック