導入
組合わせ（離散）最適化問題とは「全ての組み合わせの中から、最も良いものを選択する」問題です。
組合せ最適化問題の簡単な例：
N個のon, offスイッチがあり、最適なon, offの組み合わせを選べ（何を基準に最適とするかはここでは定義しません）。
このような問題が与えられたとき、どのような方針で解くのが良いでしょうか。
まず真っ先に考えるのは全探索で解けるのか、ということです。
全ての組み合わせを網羅的に検証することができれば、確実に最良の選択肢を選ぶことができます。
しかし、常に全探索ができるとは限りません。なぜか？
組み合わせ爆発
前述したように、最適化問題は全ての組み合わせの中から最良のものを選択するわけですが、その全ての組み合わせが多すぎると、現実的な時間内では探索が終わらないからです。
例えば、前述したスイッチの選択問題では、各スイッチはon, offの2通りの状態を取れるので、組み合わせ総数は\(2^N\)となります。
また詳細は割愛しますが、経路探索問題の中で有名な巡回セールスマン問題では、訪問箇所をNとすると組み合わせ総数は\(N!\)となります。
Nが増加するにつれて、組み合わせ総数がどうなるかを示したのが下図です。
たったN=20で、\(2^{20}\) は \(10^6\)オーダー、\(20!\) は \(10^{18}\)オーダーとなります。
とんでもないですね！
コンピュータの計算能力
次にコンピュータの計算能力を考えてみます。
一般的にC/C++であれば、1秒あたりの処理回数は\(10^8\)(参考)程度のようです。
一つの組み合わせを調べることを1処理とすると、組み合わせ総数/\(10^8\)で大まかな処理時間が分かります。
では、組み合わせ総数が\(2^N\)の場合に、Nの増加とともに処理時間がどう変化するか見てみます。
| スイッチの個数 N | 組み合わせ総数 | 処理時間 |
|---|---|---|
| 10 | 1024 | \(10^{-5}\) 秒 |
| 20 | \(1.0486 \times 10^6\) | 0.01 秒 |
| 30 | \(1.0737 \times 10^9\) | 約11秒 |
| 40 | \(1.0995 \times 10^{12}\) | 約3時間 |
| 50 | \(1.1259 \times 10^{15}\) | 3ヶ月以上 |
| 100 | \(1.2676 \times 10^{30}\) | 宇宙の年齢の約2万倍 (約32兆年) |
どれくらいの時間まで許容できるかは状況次第ですが、N=50は流石に厳しいですね。
ちなみに１秒以内で終わるのはN=26までです。
複数の探索手法が存在する理由
このように全探索では許容できない時間がかかってしまう場合は、動的計画法、貪欲法など、その他探索手法を使用する必要が出てきます。
つまり、全探索以外の探索手法は、短時間で精度の高い近似解を出すための工夫が施された探索手法です。
ただし、これがベストだという手法がある訳ではなく、探索手法ごとに一長一短があり、また問題の性質に応じて適した探索手法があったりするため、様々な手法が存在しているわけですね。
コメント