再帰関数・bit演算を用いた指数通りの全探索

探索再帰関数, bit演算

再帰関数・bit演算を用いた全探索とは

再帰関数やbitを上手く用いると、それぞれに対して「使うか」「使わないか」の2通りがあるような、\(2^n\)通りの場合を全探索することができます。
つまり、集合\(\{0,1,2,3,…,n-1\}\)の部分集合を全て調べ上げることができるのです。

ループ文を用いた全探索では、2重ループのときは\(n^2\)通りの場合、3重ループのときは\(n^3\)通りの場合を全て調べましたが、これでは指数通りの全探索は行うことができません。)

ループ文を用いた全探索に比べると計算時間が爆発的に増えてしまうので、あまり大きな入力に対して行うとかなりの時間がかかってしまいます。余裕があれば実際にためして見ると良いでしょう。
(参考:計算量同士の比較と入力サイズによる比較)

アルゴリズム

再帰関数を使ったアルゴリズム

再帰関数というのは、「自身を呼び出す関数」のことです。この再帰関数を使って「選ぶ」「選ばない」を決定し、それぞれで自身を分岐させて呼び出します。
つまり、関数内で、「選ぶ」と決めた時の再帰関数と、「選ばない」と決めた時の再帰関数を、それぞれ呼び出せばよいのです。

イメージとしては下の図のように、分岐させるたびに「選ぶ」・「選ばない」を決定させていくような形です。(下の図では1で「選ぶ」、0で「選ばない」を表しています。)

再帰関数による分岐の様子

次に説明するbit演算を用いたアルゴリズムは、\(2^n\)通りの状態しか列挙できませんが、再帰関数の呼出しを増やせば、\(3^n\)通りや\(5^n\)通りの全探索も行うことができます。

bit演算を用いたアルゴリズム

再帰関数を用いなくても、bit演算とループを用いることで\(2^n\)通りの場合を確かめることができます。

例えば、\(b=5\)であれば、これを2進数(bit)で表すと\(101\)になります。これを\({1,0,1}\)だと思い、1なら「選ぶ」, 0なら「選ばない」に対応させます。この場合では、\( {4, 10, 1}\)のうち\( 4, 1\)を選んだことになります。

  1. \(b=0\)とする
  2. \(b\)の値から、ビットが立っている場所を確認する。ビットと対応する場合について、探索の条件を満たすか判定する
  3. \(b\)が\(2^n\)以上なら終了。そうでないなら、1増やして2に戻る

ビットが立っている場所を確認するのに、ANDやORなどのビット演算に関する知識が必要です。慣れないうちは難しいかもしれません。

問題例: すべての場合の和を計算する

使い所がわかりにくいので具体例を使って考えてみましょう。

問題

値が違う\(n\)個の数字が与えられます。選び方をすべての場合について考えます。それぞれの場合で選んだ数値の和を、さらにすべて足して和を求めて下さい。

入力と出力の例

\( \{4, 10, 1\}\)という3個の数字が与えられた時を考えます。

このときの選び方は、\(\{\},\{4\}, \{10\},\{1\}, \{4,10\},\{4,1\},\{10,1\},\{4,10,1\}\)の\(2^3=8\)通りです。

それぞれの場合での選んだ数値の和は、\(0,4,10, 1, 14,5,11,15\)となります。

さらに全ての場合を足すと、60となるので、答えは60です。

プログラム例(再帰関数)

Pythonの例(Colaboratory などで確認してみて下さい)

list = [4,10,1]
def rec_plus(list, now ,sum): # sum は現在までの和を保持するために用いる
  if now<3:
    # now番目を足す時 + now番目を足さない時
    return rec_plus(list, now+1, sum+list[now]) + rec_plus(list, now+1, sum) 
  else:
    return sum
  
print(rec_plus(list,0,0)) # 出力は60

プログラム例(bit演算)

Pythonの例(Colaboratory などで確認してみて下さい)

list = [4,10,1]
def bit_plus(list):
  sum = 0
  for bit in range(1<<len(list)): # 0(0b000)から7(0b111)まで
    for i in range(len(list)):
      mask = 1 << i
      if bit&mask: # 右からi番目にビットが立っているかどうか判定
        sum += list[i]
  return sum
print(bit_plus(list)) # 出力は60

探索再帰関数, bit演算

Posted by cs-learner