複数ループによる全探索アルゴリズム

探索基本

ループによる全探索とは

特定の条件を満たすようなものを発見する方法を探索アルゴリズムと言います。全探索は全ての場合を確認して、条件を満たすものが存在するかを判定します。

全探索アルゴリズムの中でもループを使ったものは基本となっており、競技プログラミングなどでも良く出題されます。

シンプルなものは、線形探索のように1重のループで表せるアルゴリズムです。これを応用して、2重にも3重にも重なったループで複雑な問題を解けるようになります。

アルゴリズム

例として2重のループで表現できる全探索アルゴリズムを説明します。\(0 \le i, j \lt n\)として、\(i, j\)のすべての組み合わせを探索し、特定の条件を満たすかを確認します。

  1. \(i\)を0とする
  2. \(j\)を0とする
  3. \(i,j\)の値を見て、問題の条件を満たすか判定し、良ければ\(i,j\)を出力し終了する
  4. \(j\)が\(n\)以上なら5.へ。そうでなければ\(j\)を1増やして3.へ
  5. \(j\)が\(n\)以上なら-1を出力して終了。そうでなければ\(i\)を1増やして2.へ

このアルゴリズムは、実際のプログラムではループ文をネスト(入れ子)にして書くことができるので、プログラム例を見たほうがわかりやすいでしょう。

計算量

ループ文の中身の処理、つまり問題の条件を満たすかどうかの判定に定数時間\(O(1)\)しかかからないとします。

先ほどのアルゴリズムのように2重ループのとき(2変数があるとき)は、\(n^2\)通りの場合を調べるので、計算量は\(O(n^2)\)。
3重ループのときは\(n^3\)通りの場合を全て調べるので\(O(n^3)\)になります。

プログラム例

\(n\)を10として、\(i+j=13\)を満たす\(i,j\)の組み合わせがあるかを判定し、その答えを出力させます。この組み合わせは何通りかありますが、一つでも分かればよく、なければ\(-1\)を2つ出力することとします。

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

def loop_search(n):
  for i in range(n):
    for j in range(n):
      if i+j==13:
        return i,j
  else -1,-1
print(loop_search(n = 10)) #出力は(4, 9)

C++の例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ((i + j) == 13) {
                cout << i << " " << j << "\n";
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << "\n";
    return 0;
}

探索基本

Posted by cs-learner