FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

A*アルゴリズムっぽいものをJavaScriptで実装する

前回のブログから4日も日があいてしまった。
アルゴリズムをちょっと調べていて、迷路探索などに使われるA*(エースター)アルゴリズムを知った。
覚えて損は無いだろうから、JavaScriptでA*を組んでみることにした。

まず、A*を知ったこのページのソースコードをナナメ読みした。
第4回 できるだけ短いルートでゴールに到達する - 地球にやさしいアルゴリズム:ITpro

上記のページではA*についての詳しい説明が無かったので、エースターで検索して見つけた以下のページを読んで何となく理解した。
A*(A-star:エースター)探索アルゴリズム|カンガルーハウス

二次元長方形の迷路から脱出するプログラムを作ってみた。
仕様はこのようにした。
・スタートからの移動コストと、ゴールまでの推定移動コストを足してコストを算出
・現在地の座標から次に探索する座標を求める(次の座標は必ず現在地に隣接する座標)
・移動コストよりも、現在地になった回数が少ない方を優先して、次に探索する座標を求める
・ゴールまで到達した後、「スタートからの移動コスト」が最小の座標をゴール地点からたどって最短ルートを求める
「とにかく調べていない座標に移動する。調べた回数が同じ場合は、コストが小さい方に移動する」というコンセプト。
一応ソースを載せておく。
test_html.txt  astar_v1_js.txt
実行してみるとわかるが、本当の最短ルートを見つけられない。
また、次の座標は必ず現在地に隣接する座標のため、袋小路に入ると次のルートを探すのに時間がかかる。

そこで、上記の「できるだけ短いルートでゴールに到達する」で書かれていたソースコードを熟読。
いかに自分が理解しないでナナメ読みしてたかを実感。
仕様をこのように改良した。
・ゴールまでの推定移動コストのみでコストを算出
・探索候補配列中のコスト最小座標を、次に探索する座標とする
・ゴールまで到達した後、「この座標のコストを求めたときの現在地」をゴール地点からたどって最短ルートを求める
改良と言うより、全く別物になっている。
ソースコードを載せておく。html は script src しか変えていないので略。
astar_v2_js.txt
いざ実行してみると、またまた本当の最短ルートを見つけられない。
袋小路に入った場合のループ回数は大幅に減った。

本当の最短ルートを見つけるべく、コスト算出部分だけ仕様を変更
・スタートからの移動コストと、ゴールまでの推定移動コストを足してコストを算出
・探索候補配列中のコスト最小座標を、次に探索する座標とする
・ゴールまで到達した後、「この座標のコストを求めたときの現在地」をゴール地点からたどって最短ルートを求める
ソースコードは以下のとおり。
astar_v2_1_js.txt
晴れて本当の最短ルートを見つけることができたが、スタート地点からしらみ潰しに探索している感じだ。
探せばもっと効率が良いA*実装例がありそうだが、必要になったときに調べよう。

お手本のソースコードを熟読する前に自分であれこれ考えてみたので、理解が深まった気がする。
この記事に載せた3つのソースコードを書くのに3日間かったけど。
スポンサーサイト

コメント

コメントの投稿

非公開コメント

プロフィール

himax64

Author: 南西
30代後半の無職です。
就活もせずダラダラ生きてます。
作ったもの

最新記事
人気記事
検索フォーム
カテゴリ
月別アーカイブ
最新コメント
最新トラックバック
RSSリンクの表示
QRコード
QRコード
カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。