August 23, 2011

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)として直線距離を使います。
が、上の設定では直線距離は
\forall n,0\leq h^*(n) \leq h(n)
を満たさないので、最短経路であることは保証されません…。

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