A* (A-star) アルゴリズムは、グラフ探索アルゴリズムの一種で、特に最短経路問題において優れた性能を発揮します。本記事では、A* アルゴリズムの原理、特徴、そしてPythonを用いた実装について、具体的な例を交えながら解説します。
A* アルゴリズムとは
A* アルゴリズムは、ダイクストラ法を拡張したアルゴリズムであり、各ノードに対して「推定コスト」を導入することで探索を効率化します。推定コストは、以下の2つの要素から構成されます。
A* アルゴリズムは、これらの合計値 (f(n) = g(n) + h(n)) を最小化するようにノードを探索します。
【ポイント】 ダイクストラ法ではスタートノードからの実コスト g(n) のみを考慮しますが、A*アルゴリズムでは、それに加えてゴールまでの推定コスト h(n) も考慮します。これにより、「ゴールに向かっている」ノードを優先的に探索できるため、多くの場合、ダイクストラ法よりも効率的に最短経路を見つけることができます。
ヒューリスティック関数
ヒューリスティック関数 h(n) は、A* アルゴリズムの性能を左右する重要な要素です。h(n) には、以下の性質が求められます。
- 許容性 (Admissibility): h(n) は、実際のコストを決して超えないこと。
- 一貫性 (Consistency): あるノードnから隣接ノードnへの移動において、
h(n) <= h(n') + c(n, n')が成り立つこと (c(n, n') はノードnからn'への移動コスト)。
一貫性のあるヒューリスティック関数は、許容性を満たします。
- ユークリッド距離: 2次元平面上の最短経路問題において、2点間の直線距離は許容性を持つヒューリスティック関数となります。
- マンハッタン距離: 格子状の経路を持つ問題において、x方向とy方向の距離の合計は許容性を持つヒューリスティック関数となります。
【具体例数】
迷路の中にいて、出口までの最短経路を探しているとします。
- ユークリッド距離: あなたがいる場所から出口まで、壁を無視して直線を引いた距離を考えるようなものです。実際には壁があるので、直線距離よりも実際の経路は長くなる可能性がありますが、「これ以上は絶対に短くならない」という下限値にはなります。
- マンハッタン距離: 迷路が碁盤の目のように区切られているとします。このとき、あなたがいる場所から出口まで、縦方向と横方向にのみ移動して進む場合の距離を考えます。これも、壁の配置によっては実際の経路よりも短くなる可能性がありますが、許容性のある推定値となります。
アドミシブル(許容性)なヒューリスティック関数の重要性
ヒューリスティック関数は、探索空間を効率的に探索するために使用されます。過大評価をしないヒューリスティック関数を使用することで、A*アルゴリズムは最適解（最短経路）を見つけることが保証されます。 過大評価をしてしまうと、本来の最短経路よりもコストが高いと判断されてしまい探索候補から外れてしまう可能性があります。
A* アルゴリズムの手順
A* アルゴリズムは、以下の手順で最短経路を探索します。
初期化:
- スタートノードの f(n), g(n), h(n) を計算します。g(n) は 0、h(n) はヒューリスティック関数で計算します。
- オープンリスト (Open List) にスタートノードを追加します。オープンリストは、これから探索する候補となるノードの集合です。
- クローズドリスト (Closed List) を用意します。クローズドリストは、既に探索済みのノードの集合です。
探索: オープンリストが空になるまで、以下のステップを繰り返します。
- オープンリストの中で最も f(n) の値が小さいノード n を選択します。
- ノード n をオープンリストから削除し、クローズドリストに追加します。
- ノード n がゴールノードであれば、探索を終了します。
- ノード n に隣接する全てのノード n' について、以下の処理を行います。
- n' がクローズドリストに含まれていれば、スキップします。
- n' の g(n'), h(n'), f(n') を計算します。
- g(n') = g(n) + c(n, n')
- h(n') はヒューリスティック関数で計算
- f(n') = g(n') + h(n')
- n' がオープンリストに存在しない場合、n' をオープンリストに追加し、親ノードを n に設定します。
- n' がオープンリストに存在し、今回計算した f(n') の方が小さい場合、f(n'), g(n') を更新し、親ノードを n に変更します。
経路復元: ゴールノードから親ノードを辿ることで、スタートノードまでの最短経路を復元します。
以下のようなグリッド状のマップで、S（スタート）からG（ゴール）までの最短経路を探す場合を考えます。（数値は各マスでの移動コスト、灰色のマスは壁）
0 1 2 3 4 5 0 S 1 . . . . 1 . 2 # # . . 2 . . 3 . . . 3 . . # # 1 . 4 . . . . 2 . 5 . . . . . G
この時、A*アルゴリズムがどのように探索を進めていくかを図で説明します。
初期状態: * オープンリスト: {S(f=0+h)} hはSからGの推定コスト * クローズドリスト: {}
Sを展開: * オープンリスト: {A(f=1+h), B(f=2+h)} * クローズドリスト: {S}
Aを展開: * オープンリスト: {B(f=2+h), C(f=4+h)} * クローズドリスト: {S, A} ...と続いていき最もfの値が小さいノードを探索していきます。
Python による実装例
まず、グラフのノードを表す Node クラスを定義します。
class Node: def __init__(self, x, y, cost=0, heuristic=0, parent=None): self.x = x # x座標 self.y = y # y座標 self.cost = cost # 実コスト (g) self.heuristic = heuristic # 推定コスト (h) self.parent = parent # 親ノード def __eq__(self, other): return self.x == other.x and self.y == other.y def __lt__(self, other): return (self.cost + self.heuristic) < (other.cost + other.heuristic) #隣接ノードを取得する関数を追加 def get_neighbors(self): neighbors = [] # ここでは、上下左右の4方向に移動可能と仮定します。 for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: new_x, new_y = self.x + dx, self.y + dy # 座標がグリッドの範囲内にあるか確認するバリデーションが必要 # (ここでは省略) neighbors.append(Node(new_x, new_y)) return neighbors # 距離を計算する関数を追加 def distance_to(self, other): #ユークリッド距離 return ((self.x - other.x)**2 + (self.y - other.y)**2)**0.5
次に、A* アルゴリズムを実装する astar 関数を定義します。 この関数では、隣接ノードの取得にget_neighbors、距離の計算にはdistance_toを使用します。
def astar(start, goal, heuristic_func): open_list = [start] closed_list = [] while open_list: # オープンリストからf値が最小のノードを取得 current_node = min(open_list) open_list.remove(current_node) closed_list.append(current_node) # ゴールに到達したら経路を返す if current_node == goal: return reconstruct_path(current_node) # 隣接ノードを調べる neighbors = current_node.get_neighbors() for neighbor in neighbors: if neighbor in closed_list: continue # 新しいgスコアを計算 tentative_g_score = current_node.cost + current_node.distance_to(neighbor) if neighbor not in open_list or tentative_g_score < neighbor.cost: neighbor.cost = tentative_g_score neighbor.heuristic = heuristic_func(neighbor, goal) neighbor.parent = current_node if neighbor not in open_list: open_list.append(neighbor) # 経路が見つからない場合はNoneを返す return None
最後に、経路を復元する reconstruct_path 関数を定義します。
def reconstruct_path(node): path = [] while node: path.append((node.x, node.y)) node = node.parent return list(reversed(path))
使用例
# スタートとゴールのノードを作成 start_node = Node(0, 0) goal_node = Node(5, 5) # ユークリッド距離をヒューリスティック関数として定義 def euclidean_distance(node, goal): return ((node.x - goal.x)**2 + (node.y - goal.y)**2)**0.5 # A*アルゴリズムを実行 path = astar(start_node, goal_node, euclidean_distance) # 結果を表示 if path: print("最短経路:", path) else: print("経路が見つかりませんでした。")
【実行結果の解説】
このコードを実行すると、(0, 0) から (5, 5) までの最短経路が [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)] のように出力されます（障害物がない場合）。 この結果は、A*アルゴリズムがユークリッド距離を参考にしながら、最もコストの低い経路を正しく見つけ出したことを示しています。
コードの拡張
上記のコードは最も基本的な A* アルゴリズムの実装です。以下のように拡張することで、より実用的なコードにすることができます。
- 障害物の考慮:
Nodeクラスにis_obstacle(障害物かどうか) 属性を追加し、get_neighbors関数で障害物を避けるように変更します。 - 移動コストの多様化: 地形によって移動コストを変える場合 (例えば、平地はコスト1、森はコスト3など)、
Nodeクラスにterrain_cost属性を追加し、tentative_g_scoreの計算に反映させます。 - より複雑なヒューリスティック関数: 問題に応じて、より洗練されたヒューリスティック関数を設計します。 例：移動に方向転換が必要な場合、方向転換回数を考慮に入れる。
障害物を考慮したコード例
class Node: def __init__(self, x, y, cost=0, heuristic=0, parent=None, is_obstacle=False): self.x = x self.y = y self.cost = cost self.heuristic = heuristic self.parent = parent self.is_obstacle = is_obstacle # 障害物かどうか def __eq__(self, other): return self.x == other.x and self.y == other.y def __lt__(self, other): return (self.cost + self.heuristic) < (other.cost + other.heuristic) def get_neighbors(self, grid): neighbors = [] for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: new_x, new_y = self.x + dx, self.y + dy # グリッドの範囲内 かつ 障害物でない なら隣接ノード if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and not grid[new_x][new_y].is_obstacle: neighbors.append(grid[new_x][new_y]) return neighbors def distance_to(self, other): return ((self.x - other.x)**2 + (self.y - other.y)**2)**0.5
def astar(start, goal, heuristic_func, grid): open_list = [start] closed_list = [] while open_list: current_node = min(open_list) open_list.remove(current_node) closed_list.append(current_node) if current_node == goal: return reconstruct_path(current_node) neighbors = current_node.get_neighbors(grid) # gridを渡す for neighbor in neighbors: if neighbor in closed_list: continue tentative_g_score = current_node.cost + current_node.distance_to(neighbor) if neighbor not in open_list or tentative_g_score < neighbor.cost: neighbor.cost = tentative_g_score neighbor.heuristic = heuristic_func(neighbor, goal) neighbor.parent = current_node if neighbor not in open_list: open_list.append(neighbor) return None
# グリッド (障害物情報を含む) grid = [[Node(x, y, is_obstacle=(x == 2 and y < 5)) for y in range(6)] for x in range(6)] #x=2, y=0,1,2,3,4が障害物 # スタートとゴールのノードを設定 start_node = grid[0][0] goal_node = grid[5][5] # A*アルゴリズムを実行 path = astar(start_node, goal_node, euclidean_distance, grid) if path: print("最短経路:", path) else: print("経路が見つかりませんでした。")
【障害物を考慮した場合の実行結果と解説】
上記のコードでは、x=2 の列に障害物を設定しています。実行すると、障害物を避けた経路が探索され、例えば [(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5)] のような結果が得られます。
まとめ
A* アルゴリズムは、適切なヒューリスティック関数を用いることで、効率的に最短経路を探索できる強力なアルゴリズムです。Python による実装も比較的容易であり、さまざまな問題に応用可能です。A*アルゴリズムとダイクストラ法を拡張したものですので、違いをコードレベルで比較してみると、アルゴリズムの理解が深まります。
【この他の最短経路アルゴリズに関する記事】
最後にPythonの学習に利用できるUdemy
のサイトを紹介します。ぜひ活用ください。
[PR]
