Pythonで学ぶアルゴリズム 第26弾：A*アルゴリズム

#Pythonで学ぶアルゴリズム< A*アルゴリズム >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第26弾としてA*アルゴリズムを扱う．

A*アルゴリズム

A*アルゴリズムは，ダイクストラ法を発展させたアルゴリズム．ゴールから遠ざかるような無駄な経路は探索しないように工夫することで高速化する．例えば，以下のようにAからGに向かう経路を調べる場合，逆方向であるXやYに向けて移動するのは明らかに無駄である．

A*アルゴリズムでは，この無駄を避ける．そのためにゴールから遠ざかっていることを判断する必要がある．スタートからゴールへのコストだけでなく，現在地からゴールへのコストの推定値を考える．スタート地点から実際にかかったコストと，ゴールへのコストの推定値を足し合わせる方法などを用いて，推定コストも踏まえた経路が求められる．

ここでは，次のような地図を想定する．startからGの地点まで移動することを考える．

かなり複雑に見えるが，各分岐点までの距離を調べると，次のようなグラフで表現できる．

このような形となれば，ダイクストラ法などによって解けそうである．

ここで，コストの推定値について考える．コストの推定値としては，直線距離を使う方法があるが，ここでは，次に示すマンハッタン距離を用いることとする．

マンハッタン距離は，各座標の差の絶対値を使うため，どの経路でも同じ距離が得られる．
ここでは，移動先のノードからゴールまでのマンハッタン距離をコストの推定値として使うことにする．以下に，ゴールまでのマンハッタン距離をノード内に書いたものを示す．

実装

先ほどの説明によると，新たなコストを踏まえたダイクストラ法と捉えられる．それに従い，Pythonでの実装を行う．ソースコードとそのときの出力を以下に示す．

ソースコード

A_star.py

"""
2021/01/30
@Yuya Shimizu

A*アルゴリズム：無駄なコストも踏まえたダイクストラ法の発展アルゴリズム
"""
import heapq

def A_star(edges, nodes, Goal):
    """ 経路の表現
            [終点, 辺の値]
            start, A, B, C, D, ... → 0, 1, 2, ...とする """
    node = [float('inf')] * len(nodes)    #スタート地点以外の値は∞で初期化
    node[0] = 0     #スタートは0で初期化

    node_name = []
    heapq.heappush(node_name, [0, [0]])

    while len(node_name) > 0:
        #ヒープから取り出し
        _, min_point = heapq.heappop(node_name)
        last = min_point[-1]
        if last == Goal:
            return min_point, node  #道順とコストを出力させている

        #経路の要素を各変数に格納することで，視覚的に見やすくする
        for factor in edges[last]:
            goal = factor[0]   #終点
            cost  = factor[1]   #コスト

            #更新条件
            if node[last] + cost < node[goal]:
                node[goal] = node[last] + cost     #更新
                #ヒープに登録 ※ここで，nodes[goal]という部分がダイクストラ法と異なる
                heapq.heappush(node_name, [node[last] + cost + nodes[goal], min_point + [goal]])

    return []

if __name__ == '__main__':
    #各ノードのマンハッタン距離をリストとしてまとめるstart, A, B, ..., L, M
    Nodes = [
        10, 14, 10, 10, 9, 9, 5, 0, 9, 8, 6, 4, 7, 3
        ]

    Edges = [
        [[4, 1], [5, 1]],                 # ← 頂点startからの辺のリスト
        [[2, 12], [3, 4], [4, 15]],   # ← 頂点Aからの辺のリスト
        [[1, 12], [9, 2], [11, 6]],   # ← 頂点Bからの辺のリスト
        [[1, 4], [5, 3], [8, 3]],       # ← 頂点Cからの辺のリスト
        [[1, 15], [0, 1], [6, 6]],     # ← 頂点Dからの辺のリスト
        [[0, 1], [3, 3], [6, 4]],       # ← 頂点Eからの辺のリスト
        [[4, 6], [5, 4], [10, 1]],     # ← 頂点Fからの辺のリスト
        [[11, 4], [13, 5]],              # ← 頂点Gからの辺のリスト
        [[3, 3], [9, 1], [10, 5]],     # ← 頂点Hからの辺のリスト
        [[2, 2], [8, 1], [12, 1]],     # ← 頂点Iからの辺のリスト
        [[6, 1], [8, 5], [13, 3]],     # ← 頂点Jからの辺のリスト
        [[2, 6], [7, 4], [12, 5]],     # ← 頂点Kからの辺のリスト
        [[9, 1], [11, 5], [13, 6]],   # ← 頂点Lからの辺のリスト
        [[7, 5], [10, 6], [12, 3]]    # ← 頂点Mからの辺のリスト
        ]

    #今ノード数は14（0, 1~13: start, A~G）
    Goal = 7    #いまはGを目的地とする    
    opt_root, opt_cost = A_star(Edges, Nodes, Goal)    #道順とコストを出力させている


    #以下は結果を整理するためのコード

    #出力を見やすく整理するための変換用辞書型リストの作成
    root_converter = {0: 'start'}
    cost_converter = {0: opt_cost[0]}
    for i in range(1, len(Nodes)):
        root_converter[i] = chr(ord('A') + i - 1)
        cost_converter[i] = opt_cost[i]

    arrow = " → "
    result = ""
    for i in range(len(opt_root)):
        if i > 0:
            result += arrow
        result += f"{root_converter[opt_root[i]]}({cost_converter[opt_root[i]]})"

    print(f"ノード(そこまでのコスト)\n\n{result}")

出力

ノード(そこまでのコスト)

start(0) → E(1) → F(5) → J(6) → M(9) → G(14)

よって，14というコストで，目的地Gまでたどり着くことができると計算することができた．

感想

前回のダイクストラ法の続きということで，A*アルゴリズムを学んだ．直線で表現された複雑そうな地図でも上で示したノードを用いたグラフで表現することで，今回のようなアルゴリズムを適用させて最適な経路やコストを求められることを知った．原理では，距離を調べて整理すればグラフにできそうなので，直線でなくても普通の地図にでも適用できそうである．さらに，コストを何かしらの行動に対するものと定義すれば，経路だけでなく何かしらコストを伴う行動の最適化にも利用できるのではないかと思った．今回も非常に面白い内容であった．次回も楽しみである．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社