bit全探索まとめ

この記事は何

今回の記事では復習兼見返す用にbit全探索をまとめていきます。実装言語はpythonとなっています。なにか気づきや指摘等ございましたらコメントください！

bit全探索とは

bit全探索ってなんでしょう。この項では主に三つの観点からまとめていければと思います。

1. 使用場面
2. 実装方法
3. 他のアルゴリズムとの比較

1.使用場面

結論から述べると以下の条件を満たす際bit全探索の恩恵が得られると思います。

• 「N個の要素からなる集合の部分集合全体を判定する問題」
• 「大体$N\le{20}$の範囲」

例をあげると『使う・使わないを全探索』『選ぶ・選ばないを全探索』する問題などがあげられます。

2.実装方法

大きく分けるとbit全探索の実装は二つのステップからなります。

1. 全ての部分集合を列挙する。（pythonでは二つの列挙方法があります。）
   itertoolsのproductを用いてタプルで列挙する場合

   from itertools import product
   for pro in product((0, 1), repeat=N):
   

   range()を用いて整数で列挙する場合

   for bit in range(1 << N ):
   

2. その部分集合が条件を満たしているか判定する。
   itertoolsのproductを用いてタプルで列挙する場合

   def judge(pro):
   S = __ # その集合の状態を表現する。
   for i in range(N):
       if pro[i]: 
           # フラグがたっていればその要素が含まれていることを集合の状態に反映する。
   
   if S == W:  #　その集合の状態が条件をみたすなら１を返す。
       return 1
   else:
       return 0
   

   range()を用いて整数で列挙する場合

   def judge(bit):
   S = 0
   for i in range(N):
       if bit & (1 << i):  #整数bitを2進法とみなしたときの、下からi桁目が1か判定
   
   if S == W:  # S == W なら +1
       return 1
   else:
       return 0
   

3.他のアルゴリズムとの比較

のちに記載します。

この記事は以下を参考に執筆しています。

• こわくないbit全探索2 基本編1: 簡単な例題でbit全探索をやってみよう！【競プロ解説】
• けんちょんの競プロ精進記録