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