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*アルゴリズムの意味なし。)

August 16, 2011

SIMロック解除とケータイ補償お届けサービスあるいは外装交換

SIMロック解除をドコモに頼んでやってもらうと、ケータイ補償お届けサービス(1回目5,250円、2回目8,400円)あるいは外装交換(5,250円?)を利用して新しい携帯電話にしてもSIMロック解除をされた状態にして受け取ることができる、と言う事をDSの店員さんに確認してGalaxy S2のSIMロック解除をしました(3,150円)。設定画面等からSIMロック解除されているかどうか確認することはできない、らしい…

docomoでは「GALAXY S II SC-02C」、SAMSUNGでは「GALAXY S2(SC-02C)」という表記。どっちでもいいのか。

(追記) 無事海外(タイ、中国、マカオ)でも使えました。