■ ダイクストラとかA*とか

単純な迷路の最短経路を見つけるのに、ダイクストラ法とA*だとどのように異なってくるのかわかりやすく見てみたかったので、JavaScriptで実装してみました。

迷路

セルをクリックするとそのセルを通過できなくなります。もう一回クリックすると元に戻ります。スタートやゴールの位置を変更するには、[Set start]や[Set goal]ボタンをクリックしてからセルをクリックします。[Run]をクリックすると経路を探します。

探す過程で、現在のセルの状態とパスの長さを表示するようにしてあって、一ステップずつゆっくり進むようになっています。

一番上はダイクストラ法、二番目がA*で、三番目はA*なのですがヒューリスティックに指定されたゴールまでの距離が等しい場合にはゴールに近いセルから試行するようにしてあります。ちなみに、A*でのセルからゴールまでのヒューリスティックな距離はマンハッタン距離を使っています。

いくつか障害物を置きながら試してみると三番目が最も少ないステップで終わるような気がするのですが、三番目が一番目や二番目以下のステップ数で終わることは証明できるのでしょうか。