経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
人材獲得作戦の試験問題を解いてみた - 良いもの。悪いもの。はてな部屋
出遅れた感があるけど、人材獲得作戦の試験問題をPythonで解いてみた。もちろん、調べたりググったりするの禁止で。というかググればコピペで終わりのような気がする。今回はゆるめの記事なので、メインのブログではなく、こちらに書いておく。 普通にダイクストラ法で書いたけど、何故か40分もかかった。途中でコードが気に入らなくて最初から書き直したり、ケアレスミスの修正をしたりしたからか。それにしてもすっきりしないコードだ。INFを100000で決め打ちしていたりとか、優先順位付きキューを用いていなかったりとか、周りに壁があること前提だとか。いろいろひどいなぁ。 これだけじゃ面白くないので、ダイクストラ法とA*アルゴリズムの違いを説明してみる。ダイクストラ法はスタート地点から順に隣接するノードの距離を足し合わせていき、常に最も距離の短いノードからそれに隣接するノードを調べていく方法で、A*は距離を足し
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
