組み合わせ爆発の問題を解こう その4 – 爆発するものは何か。
2012-09-18Mathematics
これまで、「スライドパズルを解く」という具体的な問題を通して、深さ優先探索と幅優先探索という2通りの解答方法をご紹介しました。
この2つの解答方法は、数学的に考えれば、必ず解答が求まる方法です。何故ならば、2つの方法とも、すべての動かし方の組み合わせを列挙するからです。
しかし、実際にはこのような手法では、あらゆるスライドパズルの問題を解くことはできません。何故ならば、スライドパズルの大きさが増えるにつれて、考えられる動かし方の組み合わせは膨大になるからです。
例題では3×3のパズルだったため、適当なPCを使えばすぐに答えが求まりますが、4×4、5×5と盤面が大きくなるに連れて、計算時間がかかるようになってしまいます。性能の良いマシンや、スーパーコンピュータを用意すれば良いかというと、そうでもありません。深さ優先探索や幅優先探索というのは、いわゆる「しらみつぶし」に組み合わせを列挙する「ナイーブな」方法です。ナイーブというのは、「何も工夫されていない」ということです。それが悪い、ということではないのですが、スライドパズルを解くためには、工夫が必要であるということです。
さて、2つの言葉をご紹介します。それは「時間計算量」と「空間計算量」です。Wikipediaを引けばわかりますが、これらの言葉は「計算複雑性理論」の言葉で、問題の難しさを説明するときに用いられる言葉です。スライドパズルの難しさというのは、まさに「時間計算量」が爆発したり、「空間計算量」が爆発する問題であるところにあります。
時間計算量の爆発というのは、コンピュータに処理させる事が多すぎて、時間がかかりすぎることを言っています。深さ優先探索の場合、手数を進めて、それ以上進められない場合は戻る、という処理を行います。3×3のスライドパズルの場合、全部の動かし方が9000通り以上有ると書きましたが、9000回のスライド+数千回の手順を戻す処理を行なっています。3×3で9000回なので、4×4は、数十万通り? もっとあるかもしれませんね。
3×3のスライドパズルの場合、考えられる盤面の状態の可能性は単純に9!(9の階乗、9!=9×8×7×6×5×4×3×2×1)、と言いたいところですが、どんな並べ方にも出来得るわけではないので9!÷2といったところでしょうか。4×4なら16!となりますが、9!と比べて、少なくとも10から16の数字を掛けるため、16!は9!の百万倍になります。
深さ優先探索なら、1秒間に2000億回計算できるスーパーコンピュータなら解けそうですね、時間は掛かりそうですが…。
空間計算量の爆発というのは、メモリの使用量が爆発的に増えるということを示します。幅優先探索で解答を求めるとき、仮にどの盤面の状態でも平均して次に2方向への動かし方ができるとしましょう。
最初の状態から2方向動かせるとしたら、1手目として考えられる状態は2つ考えられます。2手目としては、さらに2つの動かし方ができるので、4通り考えられます。3手目は4つの状態からそれぞれ2つの動かし方が考えられるから8通りですね。30手目のときは2の30乗となります。1つの状態を1バイトで表せるとしても、2の30乗のバイト数が必要で、これは1GBです。32手目では4GBのメモリが必要となり、一般的な32bitOSで扱えるメモリの範囲を超えてしまいます。
では64bitなら良いかというと、今度は物理的なメモリの問題が出てきます。仮にメモリが1TBあるとしても、40手目まで進められるだけです。このように、1手進めるだけでメモリの使用量が倍になってしまうため、幅優先探索では空間計算量が爆発してしまう、と言えます。
なお、実際に幅優先探索を使ってスライドパズルを解くと、普通のPCを使用すると途中でメモリの確保に失敗してプログラムが強制終了します。仮想記憶を使うとしても、ハードディスクからの読み込みは時間がかかりますし、さらにハードディスクの容量まで使い切ってしまうことは容易に想像されます。
つまり、ちょっと盤面の大きいスライドパズルは、幅優先探索では解けない、ということです。
以上の話をまとめると次のようになります。
- 深さ優先探索は時間計算量が爆発する
- 幅優先探索は空間計算量が爆発する
爆発すれば、それだけ処理に時間が掛かるし、それに、答えを出す前にプログラムが強制終了してしまうことも考えられます。
では、4×4とか5×5のスライドパズルは解けないのかというと、そうではありません。すべて列挙するから解けなくなるだけであって、効率的に組み合わせを列挙すれば大丈夫です。
ということで、次回は、A*アルゴリズムについて説明したいと思います。
Topic
- Mathematics (15)
- Natural Language Processing (1)