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

2019年11月21日探索基本,全探索

ループによる全探索とは

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

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

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

例：2重ループによる全探索アルゴリズム

例として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.へ

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

以下は二重ループを C++ 風に書いた時の場合です。

for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        // i, j の値を見て条件を満たすか判定
    }
}

計算量

  • \(O(n^k)\) （k重のループで中身の処理が定数時間の時）

ループ文の中身の処理、つまり問題の条件を満たすかどうかの判定に定数時間 \(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;
}

練習問題

探索基本,全探索