再帰関数・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\)になります。0なら「選ばない」に対応させます。1\)を選んだことになります。\(b=0\)とする\(b\)の値から、ビットが立っている場所を確認する。ビットと対応する場合について、探索の条件を満たすか判定する\(b\)が\(2^n\)以上なら終了。ないなら、1増やして2に戻るビットが立っている場所を確認するのに、ANDやORなどのビット演算に関する知識が必要です。慣れないうちは難しいかもしれません。すべての場合の和を計算する使い所がわかりにくいので具体例を使って考えてみましょう。値が違う\(n\)個の数字が与えられます。選び方をすべての場合について考えます。それぞれの場合で選んだ数値の和を、さらにすべて足して和を求めて下さい。1\}\)という3個の数字が与えられた時を考えます。\{4,10\},\{4,1\},\{10,1\},\{4,10,1\}\)の\(2^3=8\)通りです。14,5,11,15\)となります。全ての場合を足すと、60となるので、答えは60です。Search)深さ優先探索とは、全探索アルゴリズムの一種です。...順列(n!)の全探索\(n!\)通りの全探索を行いたい時に順列が用いられます。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。