A*(エースター)法による最短コストの探索|HTML5

A*(エースター)法による最短コストの探索|HTML5

A*(エースター)法による最短コスト(ルート)の探索を導き出すアルゴリズムをJavaScriptでコーディングしました。

A*法はダイクストラ法よりも、探索回数が少なくてすむのが特徴です。前回のダクストラ法は23回。今回のA*法は10回で済んでいます。

A*法では、実コスト+推定コストで探索経路を求めます。推定コストとは、終着点のノードから現在のノードの座標位置を引いたものです。斜め移動がある場合は以下の式で求めます。エッジのコストはすべて1です。

dx = tx – x
dy = ty – y
dx と dy を比較して高い値が推定コストとなります。

縦横(4方向)移動のみの場合は、推定コストは dx + dy になります。

A*法では、この推定コストに実コストを加算してスコアを求め、探索コストを計算します。

ここでも前回と同じように、n2というノードが出発点、n24というノードが終着点となっています。両者とも自由に他のノードに置き換えることができます。エッジのコストはすべて1にしています。コードを実行すると、上記の図のような経路が導き出されます。

A*(エースター)法による最短コストの探索(HTML5, JavaScript) : デモ

A*(エースター)法による最短コストの探索(HTML5, JavaScript) : ZIPファイル(47kb)

“A*(エースター)法による最短コストの探索|HTML5” の続きを読む

ダイクストラ法による最短コスト探索2|HTML5

ダイクストラ法による最短コスト探索

前回と同じような、ダイクストラ法による最短コスト(ルート)の探索を導き出すアルゴリズムを再び、JavaScriptでコーディングしました。

ここでは、n2というノードが出発点、n24というノードが終着点となっています。両者とも自由に他のノードに置き換えることができます。エッジのコストはすべて1にしています。コードを実行すると、上記の図のような経路が導き出されます。

ダイクストラ法による最短コスト探索2(HTML5, JavaScript) : デモ

ダイクストラ法による最短コスト探索2(HTML5, JavaScript) : ZIPファイル(45kb)

“ダイクストラ法による最短コスト探索2|HTML5” の続きを読む

ダイクストラ法による最短コスト(経路)探索|HTML5

ダイクストラ法による最短コスト

ダイクストラ法による最短コスト、または最短ルートの探索を導き出すアルゴリズムをJavaScriptでコーディングしました。

ここでは、n1というノードが出発点、n8というノードが終着点となっています。両者とも自由に他のノードに置き換えることができます。ぜひ試してみてください。コードを実行すると、上記の図のような経路が導き出されます。

ダイクストラ法による最短コスト(経路)探索(HTML5, JavaScript) : デモ

ダイクストラ法による最短コスト(経路)探索(HTML5, JavaScript) : ZIPファイル(92kb)

“ダイクストラ法による最短コスト(経路)探索|HTML5” の続きを読む