アルゴリズム：全探索

この記事では、アルゴリズムの一つ、全探索に関して簡単に記載する。

1. 目的

　・全探査について理解する。

　・C言語で全探査を行う方法について理解する。

アルゴリズム：全探索

2. 全探索とは

　・ある問題に対してすべての可能性を試し、最適な解を求めるアルゴリズムの一種。

　・あり得る全てのパターンをしらみつぶしに全て調べる方法。

　問題点：

　・全探索は一般に計算量が非常に大きくなりがちで、

　　問題によっては、膨大な計算量により、時間がかかってしまう。

　・全探索しても現実的な時間で実行が終るかどうかを検討する必要がある。

3. 基本的な全探索手順

　・問題を分解して、可能な解の候補を列挙する。

　・列挙した候補を一つずつ評価し、最適解を探す。

　・最適解が見つかった場合、探索を終了する。

　例：

　ある複数の数値の中から最大値を探索する。

　(1) 最初の数を最大値として選び、残りの数と比較する。

　(2) 次の数が現在の最大値より大きければ、その数を新しい最大値とする。

　(3) 残りの数がなくなるまで、2を繰り返す。

　(4) 最大値が見つかったら、探索を終了する。

　　など。

　例2：

　2枚のカードに1～Nの数値が書かれており、

　その中から合計S以下となるカードの組み合わせはいくつあるか。

　(1) 1枚目と2枚目のとりえる数値の組み合わせを算出する。

　(2) 1枚目と2枚目の数の足した値を算出する。

　(3) 合計した数値がS以下かどうか判定する。

　(4) S以下の場合、組み合わせカウントを+1する。

　(5) これを、全てのパターン分繰り返す。

4. プログラムの作成(最大値の全探索)

　・最大値を探す全探索プログラム

　・13個の値が与えられ、その中から最大値をprintfで出力する。

#include <stdio.h>

int main() {
    int n = 13, max, i;
    int a[] = {1,2,3,5,10,15,20,25,11,12,14,25,17}; // 初期化された13個の要素を持つ配列とする

    max = a[0]; // 最初の要素を最大値とする
    for (i = 1; i < n; i++) { // 2番目の要素から最後の要素までループする
        if (a[i] > max) { // 要素が現在の最大値よりも大きければ、最大値を更新する
            max = a[i];     
        }
    }
    
    printf("最大値は%dです\n", max); // 最大値を表示する
    return 0; // プログラムの正常終了を示す
}