組み合わせ爆発の問題を解こう その6 – h*()を求める
2012-09-27Mathematics
前回、A*アルゴリズムの式を出しました。もう一度下に示します。
数式だけだとイメージが湧かないので、実際に、変数nにスライドパズルを入れてみます。
↑の図のh*()が今回求めたいものです。図にも書いてありますが、h*()は、ある状態からゴールまでにスライドさせる数がどれくらいあるか、の推定値です。推定値なので、厳密な値である必要はないのですが、ある程度は妥当な値にしたいところです。
さて、このh*()の値は今回解いている「スライドパズル」の性質をよく考えて決めなければなりません。ということで、下の図を見て下さい。
これは、壁がない場合の、3×3のパズルです。一番上がゴールで、下に行くほど、完成から遠のいています。さて、この図の右に、完成状態から、どれくらいパネルがずれているかを書いてみました。例えば、ゴールの1つ下は、8のパネルが右に1つずれているから、それを直せばゴール、ということです。更にその下は、7と8がそれぞれ1ずつ、右にずれている…。なんか…ぼんやりと見えてきますね。
スライドパズルというのは、つまり、完成状態のときにあるべきパネルの位置を目指して、ズレを修正していくパズルである、と考えることができます。このズレは、1回のスライドでは、高々1つ分しか修正できません。完成状態から3ずれている場合は、少なくとも3回スライドさせないとゴールにはたどり着かない、ということです。
そう考えると、今回の問題は…。問題をもう一度掲載して、ズレ具合を出してみました。
この問題は、最初は、ゴールの状態と比べると7ずれていることが分かります。7…、どこかで見た数字ですね。この問題の解答例をその1(組み合わせ爆発の問題を解こう その1 – 問題編)に示しましたが、その記事の最後にも、7回スライドさせて完成したと書いてあります。
とすると、このずれ具合がh*()、つまり何回スライドさせればゴールになるかの推定値に使えそうですね。
では次回、この「ずれ具合」の値を使って、実際にパズルを解いてみたいと思います。
Topic
- Mathematics (15)
- Natural Language Processing (1)