ダイクストラとかA*とか - #3(2010-01-19)■ ダイクストラとかA*とか 単純な迷路の最短経路を見つけるのに、ダイクストラ法とA*だとどのように異なってくるのかわかりやすく見てみたかったので、JavaScriptで実装してみました。 迷路 セルをクリックするとそのセルを通過できなくなります。もう一回クリックすると元に戻ります。スタートやゴールの位置を変更するには、[Set start]や[Set goal]ボタンをクリックしてからセルをクリックします。[Run]をクリックすると経路を探します。 探す過程で、現在のセルの状態とパスの長さを表示するようにしてあって、一ステップずつゆっくり進むようになっています。 一番上はダイクストラ法、二番目がA*で、三番目はA*なのですがヒューリスティックに指定されたゴールまでの距離が等しい場合にはゴールに近いセルから試行するようにしてあります。ちなみに、A*でのセルからゴールまでのヒューリスティック
ほぼ日刊イトイ新聞 -マッチ箱の脳（WEB）篇
