組み合わせ爆発の問題を解こう その8 – まとめ
2012-09-29Mathematics
長々とお付き合いありがとうございました。
今回の一連の記事では、スライドパズルを解きながら、組合せ爆発の問題点と、その解決方法を見てきました。
- スライドパズルは「スタートとゴールが分かっていて、その間をどのように空マスをスライドさせればよいか探索する、経路探索の問題」である。
- 経路探索の問題点は、経路の組み合わせが膨大であり、単純な方法では、時間計算量や空間計算量が爆発してしまうことである。
さて、経路探索の問題の解決法として、3つ紹介いたしました。
- 深さ優先探索は時間計算量が膨大になる。すべての経路のパターンを計算しないと、最適解が分からない。スライドパズルなら、スーパーコンピュータなら解けそうかも。
- 幅優先探索は空間計算量が膨大になる。最初に見つかった経路が、最適解であることが保証されるが、少し難しい問題は、ほぼ解けない。
- A*アルゴリズムを使うと、ゴールに近いものから順に計算するため、効率的である。
深さ優先探索と幅優先探索は、結局はすべての経路のパターンを調べるから、どんな経路探索の問題にも使える手法とも言えます。迷路の右手法のようなものですね。
A*アルゴリズムは、特にh*()をどのように決めればいいか決めるまでが大変です。g*()やh*()の値の決め方は、対象とする問題の性質を知らなければならないので、A*アルゴリズムを動かすまでは時間がかかりますが、ちゃんと動けば、効率的に解答を求めることができます。
A*アルゴリズムでは、h*()の関数を「ヒューリスティック関数」と言います。ヒューリスティックについては、組合せ爆発と、経験則と、暗号化の話。 でも少し触れましたが、人間がコンピュータに与える「考え方のヒント」です。スライドパズルではゴールからのずれ具合を与えましたが、もっといいヒューリスティック関数があるかもしれませんね。
コンピュータの性能は非常に高くて、多少無理のある計算をしても、答えを出してくれますが、組合せ爆発の問題など、すぐに性能の限界が見えてしまう問題もたくさんあります。
コンピュータを使った計算で重要なことは、どのような問題を解く場合でも、注目している状態を的確に数値に落とせるかということです。そのためには、やっぱり、人間が頭を使わないといけないのですね…。
ということで、下手な説明&分かりにくい図だったかもしれませんが、いつかどこかで情報系の学生の役に立つといいなあ…、と思いながら、組合せ爆発の問題はここまでです。
次は、モンティ・ホール問題をちょっとだけ扱ってみたいと思います。
Topic
- Mathematics (15)
- Natural Language Processing (1)