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

この記事では

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

を紹介していきます。

探索アルゴリズム全般について知りたい方はこちら！

A探索（A Search）とは
まとめ

A探索（A Search）とは

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

ヒューリスティック（Heuristic）とは

問題解決や意思決定の際に用いられる経験則や直感的な方法のことです。具体的には、厳密な計算や論理的な手順を省略し、効率的に解を見つけるための近道や簡便な方法を指します。

現実の例にすると

「最短ルートで目的地に到達する」

例えば、地図を使って最短ルートで目的地に到達しようとしているとします。A*探索では、現在地から目的地までの距離（コスト）と、各道の進みやすさ（ヒューリスティック）を考慮して、最も効率的なルートを選びます。まず、最も近い道を選び、次にその道からさらに進むべき道を選びます。

このプロセスを繰り返して、最短かつ最も効率的なルートを見つけることができます。

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

例えば、迷路のスタート地点からゴール地点までの最短経路を見つける場合を考えます。迷路は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("経路が見つかりませんでした。")

コードの解説

必要なモジュールのインポート:
```
import heapq
```
heapq モジュールをインポートして、優先度付きキューを実装します。
ヒューリスティック関数の定義:
```
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
```
マンハッタン距離を計算するヒューリスティック関数を定義します。
A*探索関数の定義:
```
def a_star_search(maze, start, goal):
```
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)}
```
迷路の行数と列数を取得し、優先度付きキュー open_set にスタート地点を追加します。また、各ノードのコストを記録する辞書 g_score と f_score を初期化します。

探索ループ:

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))

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

経路が見つからない場合:
```
return None
```
すべての探索が終了してもゴールに到達できない場合、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)

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