Excel（エクセル）で学ぶアルゴリズム：A*（エースター）探索

A*は「スタートからゴールまで」の距離を事前情報を与え、移動距離と距離を合算した値を元に最短経路を探す探索アルゴリズムです。
この距離の設定方法とかにいくつか流派があるようなんですが、目安になればなんでもいいです。ここでは直線距離を元にしています。

A*（エースター）探索の例

まずは迷路を用意しました。スタートからゴールまで進みたいんですが、

総当たり方式（ダイクストラ法）で進むと、このようにかなり余計な道も進むことになります。

これに対し、A*では事前情報（ヒューリスティックコスト）としてスタートからゴールまでの距離を情報として入力し、これを目安にします。
Excel上での距離の測定はこの記事を元に、

=Round(Sqrt((Abs(Column(絶対参照のゴールの位置)-Column(現在地))^2)+(ABS(ROW(絶対参照のゴールの位置)-ROW(現在地))^2)),1)

という長ったらしい式で行っています。
要は二点間の距離を求めて、それを小数点1位までに四捨五入してます。

式をスライドさせていけば距離も自動計算されますが、

A*では、距離にそれぞれスタート地点から進んだ距離を足し算した数値を使います。

まずはスタート地点から最も数値の少ない数値の方向へ進み、進んだ地点を確定します。

再びスタート地点または確定された位置から、最も数値の少ない数値の方向へ進みます。これを繰り返します。

分岐点では進める方向それぞれに数値を求め、また最小値のセルへと進行します。

最小値が複数ある場合は、どの道を先に選んでもかまいません（実際の移動距離が少ないほうを先に進むほうが確実かも）。

最終的にこうなります。総当たり方式よりかなり省略されたルートで最短距離を進んでいることがわかります。

以上です。ただ試した感じ、正解ルートが大回りする迷路などでは普通に総当たりと同じ結果になるし、計算が煩雑な分余計に時間がかかるまであります。
逆方向にどんどん進んだりしないのが強みなので、ゲームでタップした位置にキャラクターを動かしたい時などは使えるかもしれません。