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

• 問題提起

  • 規模が大きい問題は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なら？
  • またあるいは、抜き出す特徴量の数が変わったら？