組み合わせ爆発の問題を解こう その5 – A*アルゴリズム
2012-09-23Mathematics
少し間が開きましたね、旅行に行っていました。さて、スライドパズルの続きです。そろそろ終わらせたいけど、今回を含めて、あと4回続きそうです。
スライドパズルというのは、最初のシャッフルされた状態から、最後の完成状態まで、どのようにパネルをスライドさせればよいか、という問題でした。スタートとゴールが決まっていて、その間をどうするか考える問題で、「経路探索」と呼ばれる類の問題です。
これまで、経路探索の解決方法として、深さ優先探索と幅優先探索を取り上げましたが、これらは時間計算量や空間計算量が爆発するので、実際には使えないという話までしました。
さて、なぜこれらがダメなのか。理由は、「全部の経路の組み合わせを列挙しようとするから」です。ということは、全部の経路の組み合わせを列挙しなければ良いのです。そこで、今回ご紹介するのが、A*アルゴリズムです。
A*は「えーすたー」と読みます。A*アルゴリズムは、次の考え方に基づきます。
スタートから、ある地点(ある地点をnと置きます)を通って、ゴールまで辿り着くときの最短経路と考えるとき、最短経路のコスト(動く距離の合計とか)をとすると、スタートからゴールまでのコスト
は、次のように考えられます。
なんか、式があっさりしていますね。ここで、がスタートから地点nまでの最小コスト、
が地点nからゴールまでの最小コストです。この2つを足せば、地点nを通った時の、スタートからゴールまでの最小コストが求められますね。
さて、お分かりの通り、とか、
は予め与えることができません。つまり、ちゃんとした
を求めることができないのです。なので、
を求めるのではなく、その推定値である
を求めることを考えてみます。
推定値は、次のようにして求めます。
先ほどの式と、ほぼ同じですね。頭に*がついているだけです。ただ、この細かい違いが重要で、最初の式は「厳密値」を求めるための式であることを示しており、次の式が「推定値」を求めるための式であることを示しています。そう、推定値、でいいんです。
厳密解を求めるのが、ものすごく時間がかかる場合、求められる解の厳密性を犠牲にして、ある程度正確ならOKとするのが、なかなか人間的でいいですね。かのオイラーという数学者は、月の満ち欠けをある程度の精度で予測する(厳密に解こうとすると、まず解けないらしい)ことを考えたそうです。数学は純粋数学であれば厳密性が重要ですが、応用数学ではある程度のブレは許容されたりします(客観的に見て許容出来る場合、ですが)。
上式で推定値を求めるとき、は初期状態から完成状態までに動かす回数、
はそれまで動かした回数、
は完成状態までに動かさなければならない回数とすることができます。
はこれまでの動かし方から分かりますが、では、
は…?
ということで、次回は、について考えたいと思います。
あと、A*をどのように使うのかということを書き忘れていました。A*アルゴリズムのある地点nというのを、最初はスタートから1回動かした時の位置に設定し、ゴールまでのコストの推定値を計算します。次に、2回動かした位置に設定したり、ということを続けて、どんどんnをゴールに近づけていけば、最短経路が求められそうですね。
今後の予定です。
を求める
- A*アルゴリズムでスライドパズルを解く
- まとめ
Topic
- Mathematics (15)
- Natural Language Processing (1)