PythonでA*アルゴリズムを実装してみる

PythonでNexworkXを使ってA*アルゴリズムを実装してみます。まあNetworkXではA*アルゴリズムは実装されているのですが。

NetworkXは複雑ネットワークでいろいろやるためのPythonのパッケージ。easy_installでインストールするのが楽。

A*（A-star, エースター） アルゴリズムは、経路探索アルゴリズムの一つ。Wikipediaの解説がわかりやすい。(→Wikipedia ja, Wikipedia en)

ここではWikipediaにある疑似コードをほぼそのままの形で実装してみます。ランダムな重みつきエッジで構成される3x3のグリッドにおいて(0,0)から(2,2)への最短ルートを探索します。

以下ではヒューリスティック関数h^*(n)として直線距離を使います。
が、上の設定では直線距離は

を満たさないので、最短経路であることは保証されません…。

なので、一応、ヒューリスティック関数h^*(n)による推定値を常に0とすることで、ダイクストラ法による最短距離を求めてみます。（A*アルゴリズムの意味なし。）