コンピューターがたくさんあっても解けない問題

問題提起
- 規模が大きい問題はHadoopを使えば大丈夫、と思っていませんか？
- 分散コンピューティングをしたとしても、対応できないタイプの問題が存在します。
- 計算量の観点から、コンピューターで解ける問題と解けない問題を知りましょう。
コンピューターがたくさんあっても解けない問題の例
- 問題の説明
  - 5人で2人3脚をする場合(5人6脚)の最も良い並び方を知りたい。
  - 5人の並び方を入力すれば、シミュレーションする機能(関数やクラス)がすでにあるとする。
  - 最も良い並び方を知るには、すべての並び方のパターンでシミュレーションする必要がある。
- 並び方のパターンはいくつあるだろうか？
  - 3人の場合
    - 以下のようになるので、パターンは全部で6通り
      A - B - C \ C - B B - A - C \ C - A C - A - B \ B - A
  - 4人の場合
    - 以下はAを最初にしたパターン。これがほかに3ケースある。(Bを最初にしたパターン、ｃを最初にしたパターン、Dを最初にしたパターン)。
    - 以下にあるようにAを最初にしたときのパターン数は6通りで、それが4通りあるため、総パターン数は6 × 4 の 24通りとなる。
      A - B - C - D \ D - C \ C - B - D \ D - B \ D - B - C \ C - D
  - 5人の場合
    - 4人の場合は、3人のパターン数(6通り) × 4通りの24通りとなった。
    - 5人の場合は、4人のパターン数(24通り) × 5通りなので、24 × 5の120通りとなる。
  - 一般式
    - 3人の場合: 3 × 2 × 1 = 6
    - 4人の場合: 4 × 3 × 2 × 1 = 24
    - 5人乗場合: 5 × 4 × 3 × 2 × 1 = 120
    - n人の場合: n × (ｎ - １) × (n - 2) × ... × 1
      - n! と表記する。
問題の規模と計算量の関係を可視化する
- - 問題の規模(人数)が増えると、パターン数が爆発的に増加する。
人数が増えたらどうなるか？
- 5人のときは、5分で計算ができるとする(120パターンの計算に5分かかる)。10人になったら、どうなるだろうか？
  - 5人のパターン数: 120
  - 10人のパターン数: 3628800(5人のパターン数の30240倍)
  - 5分 × 30240 = 151200分(2520時間)
こういったものが、コンピュータがたくさんあっても、解けないタイプの問題
- 計算量が爆発的に増加する問題(計算量のオーダーが、指数関数的な増加傾向を示すもの)
- 計算量が問題の規模と比例するなら、まだ対応可能
  - その場合、問題の規模が多くなった分だけ、コンピューターを用意すれば良い。(10倍の規模になったら、10倍のコンピュータを用意すれば良い)
では、例えば、このようなケースはどうだろうか？
- 問題
  - 10人11脚をする。
  - もっともよい並び方を知りたい
  - 並び方を与えれば、シミュレーションする機能(関数)があるとする。
- 解法(アルゴリズム)
  - すべての組み合わせを算出し、シミュレーションする。
  - PCで計算すると、それに10分かかるとする。
- その後、仕様変更が起きたとする。
  - お客さんの要望で、10人から15人になる(15人14脚)。
  - そのかわり、PCの倍の速さで計算できるサーバが10台手に入る。(20倍の速さで計算できるようになったとする)
  - 1日(24時間)で、結果を出さねばならない。
- 果たして対応できるか？
  - 10人の場合の並び方の総数: 3,628,800
  - 15人の場合の並び方の総数: 1.30767E+12
  - 問題の規模(並び方の総数)は、360360倍になる。
  - 計算時間はどうなるか？
    - pcの場合: 10分の360360倍なので、3603600分。(60060時間)
    - サーバを使えば、pcの20倍の速さで計算できるので、60060時間 ÷ 20 = 30003時間(125日)
  - 結論: 全然無理
- 結果、どうなるか？
  - 仕様変更となってしまい、設計からテストまで全部やり直し。
このような例ではどうだろうか？
- 問題
  - 100の特徴量の候補があり、この中から、最も良い特徴量の組み合わせを知りたい。
- 条件
  - 抜き出す特徴量の数は3つとする。
  - 3つの特徴量を与えれば、モデルを計算する機能(関数)があるとする。
- 100の特徴量から3つを抜き出すパターンをすべて算出する場合、1時間かかるとする。
- 120の特徴量になった場合、実用的な時間で問題を解けるだろうか？
- あるいは、110ならどうだろうか？ 130なら？
- またあるいは、抜き出す特徴量の数が変わったら？