A*（エースター）

A*（エースター）

A*（エースター）アルゴリズムは、ダイクストラ法を発展させたアルゴリズムで、ゴールから遠ざかるような無駄な経路は探索しないように工夫することで処理を高速化します。

解き方・ソースコード

ゴールから遠ざかっていることを判断するため、現在値からゴールへのコストの推定値を考えます。

今回はコストの推定値として、マンハッタン距離が与えられているものとします。（21行目）

マンハッタン距離は、各座標の差の絶対値を使うためどの経路でも同じ距離が得られます。

[Google Colaboratory]

import heapq

def astar(edges, nodes, goal):
    dist = [float('inf')] * len(nodes)
    dist[0] = 0
    q = []
    heapq. heappush( q, [0, [0]])
    
    while len(q) > 0:
        _, u = heapq.heappop(q)
        last = u[-1]
        if last == goal:
            return u
        for i in edges[last]:
            if dist[i[0]] > dist[last] + i[1]:
                dist[i[0]] = dist[last] + i[1]
                # 推定値を踏まえてコストを算出
                heapq.heappush(q, [dist[last] + i[1] + nodes[i[0]], u + [i[0]]])
    return []
    
# コストの推定値
nodes = [ 10, 14, 10, 10, 9, 9, 5, 0, 9, 8, 6, 4, 7, 3 ]

# 辺のリスト（終点とコストのリスト）
edges = [ [[4, 1], [5, 1]],
          [[2, 12], [3, 4], [4, 15]],
          [[1, 12], [9, 2], [11, 6]],
          [[1, 4], [5, 3], [8, 3]],
          [[1, 15], [0, 1], [6, 6]],
          [[0, 1], [3, 3], [6, 4]],
          [[4, 6], [5, 4], [10, 1]],
          [[11, 4], [13, 5]],
          [[3, 3], [9, 1], [10, 5]],
          [[2, 2], [8, 1], [12, 1]],
          [[6, 1], [8, 5], [13, 3]],
          [[2, 6], [7, 4], [12, 5]],
          [[9, 1], [11, 5], [13, 6]],
          [[7, 5], [10, 3], [12, 6]] ]

print('解：', astar( edges, nodes, 7))

[実行結果]

解： [0, 5, 6, 10, 13, 7]

A*（エースター）アルゴリズムを使って最短経路を求めることができました。