A探索（A Search）とは？Pythonコードの具体例と解説付き！

この記事では

• A探索（A Search）とは？
• コードで示す具体例
• コードの解説

を紹介していきます。

A探索（A Search）とは

• 説明: グラフ探索アルゴリズムで、スタートノードからゴールノードまでの最短経路を見つけるために、ヒューリスティック関数を使用して探索を行う方法です。
• 時間計算量: 最悪の場合 $O(E)$（Eはエッジ数）。
• 使用例: パスファインディングやナビゲーションシステム。

現実の例にすると

具体例：迷路の最短経路探索

例えば、迷路のスタート地点からゴール地点までの最短経路を見つける場合を考えます。迷路は2次元のリストで表され、0は通れる道、1は壁、Sはスタート地点、Gはゴール地点を示します。

コード例（Python）

import heapq

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    
    while open_set:
        _, current = heapq.heappop(open_set)
        
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path
        
        x, y = current
        neighbors = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
        
        for neighbor in neighbors:
            nx, ny = neighbor
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != 1:
                tentative_g_score = g_score[current] + 1
                
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return None

# 使用例
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 'G']
]
start = (0, 0)
goal = (4, 4)
path = a_star_search(maze, start, goal)

if path:
    print("最短経路:", path)
else:
    print("経路が見つかりませんでした。")

コードの解説

1. 必要なモジュールのインポート:

   import heapq
   

   heapq モジュールをインポートして、優先度付きキューを実装します。

2. ヒューリスティック関数の定義:

   def heuristic(a, b):
       return abs(a[0] - b[0]) + abs(a[1] - b[1])
   

   マンハッタン距離を計算するヒューリスティック関数を定義します。

3. A*探索関数の定義:

   def a_star_search(maze, start, goal):
   

   a_star_search という名前の関数を定義しています。この関数は、迷路 maze の中で start から goal までの最短経路を見つけます。

4. 初期化:

   rows, cols = len(maze), len(maze[0])
   open_set = []
   heapq.heappush(open_set, (0, start))
   came_from = {}
   g_score = {start: 0}
   f_score = {start: heuristic(start, goal)}
   

   迷路の行数と列数を取得し、優先度付きキュー open_set にスタート地点を追加します。また、各ノードのコストを記録する辞書 g_score と f_score を初期化します。

5. 探索ループ:

   while open_set:
       _, current = heapq.heappop(open_set)
       
       if current == goal:
           path = []
           while current in came_from:
               path.append(current)
               current = came_from[current]
           path.append(start)
           path.reverse()
           return path
   

   優先度付きキューが空になるまでループを続けます。キューの先頭から現在のノードを取り出し、それがゴール地点であるかを確認します。ゴール地点であれば、経路を復元して返します。

6. 隣接ノードの探索:

   x, y = current
   neighbors = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
   
   for neighbor in neighbors:
       nx, ny = neighbor
       if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != 1:
           tentative_g_score = g_score[current] + 1
           
           if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
               came_from[neighbor] = current
               g_score[neighbor] = tentative_g_score
               f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
               heapq.heappush(open_set, (f_score[neighbor], neighbor))
   

   現在のノードの隣接ノードを探索し、それらが迷路の範囲内であり、壁でない場合に処理を行います。各隣接ノードに対して、仮のコスト tentative_g_score を計算し、必要に応じてコストを更新し、優先度付きキューに追加します。

7. 経路が見つからない場合:

   return None
   

   すべての探索が終了してもゴールに到達できない場合、None を返します。

8. 使用例:

   maze = [
       [0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0],
       [0, 1, 1, 1, 0],
       [0, 0, 0, 0, 'G']
   ]
   start = (0, 0)
   goal = (4, 4)
   path = a_star_search(maze, start, goal)
   

   迷路 maze と開始位置 start、ゴール位置 goal を定義し、a_star_search 関数を呼び出します。

9. 結果の表示:

   if path:
       print("最短経路:", path)
   else:
       print("経路が見つかりませんでした。")
   

   関数の結果に基づいて、最短経路が見つかった場合はその経路を表示し、見つからなかった場合はメッセージを表示します。

まとめ

今回のポイントをまとめます。

• A探索とは、グラフ探索アルゴリズムで最短経路を見つけるために、ヒューリスティック関数を使用して探索を行う方法