幅優先探索は、グラフや木構造などのデータ構造で、あるノードから開始して、そのノードから近いノードを順に探索するアルゴリズムです。これは、最短経路を求める問題などに使われます。以下に、Pythonで幅優先探索を実装する手順と具体例を示します。
幅優先探索のアルゴリズム
幅優先探索は、幅優先探索木を作成することによって実装されます。幅優先探索木は、始点ノードからの距離に基づいて、ノードをレベルごとに分類した木構造です。以下に、幅優先探索のアルゴリズムを示します。
- 始点ノードをキューに入れる。
- キューからノードを取り出す。
- 取り出したノードが目的のノードかどうかを調べる。
- 取り出したノードから伸びるすべてのノードをキューに入れる。
- キューが空になるまで2-4を繰り返す。
具体例
次に、幅優先探索を実装する具体例を示します。以下のグラフを例に考えます。
A / \ B C | \ | D E F
このグラフにおいて、始点ノードをA、目的のノードをFとします。このとき、幅優先探索によって、A -> C -> Fの経路が最短経路となります。
コード例
Pythonで幅優先探索を実装するには、以下のようなコードを記述します。
from collections import deque def bfs(graph, start, goal): visited = set() queue = deque([(start, [start])]) while queue: (node, path) = queue.popleft() if node not in visited: if node == goal: return path visited.add(node) for child in graph[node]: if child not in visited: queue.append((child, path + [child]))
このコードでは、dequeを使ってキューを実装しています。始点ノードとその経路をタプルとしてキューに入れ、幅優先探索を実行しています。visitedセットに訪問済みのノードを保存し、ノードが目的のノードであるかどうかを調べ、キューに子ノードを追加します。また、各ノードの経路はpathに保存され、経路が求められたらそれを返します。このコードを使って、先に示したグラフのAからFまでの最短経路を求めるには、以下のように実行します。
まず、上記のグラフを辞書で表現すると、以下のようになります。
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
スタート位置とゴールを設定して下記のようにコードを実行します。
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
start = 'A'
goal = 'F'
result = bfs(graph, start, goal)
print(result)
このコードを実行すると、['A', 'C', 'F']が出力されます。
まとめ
Pythonで幅優先探索を実装する手順と具体例を説明しました。幅優先探索は、最短経路を求める問題などに使われる重要なアルゴリズムの一つです。幅優先探索は、グラフ理論における重要なアルゴリズムであり、様々な分野で利用されています。例えば、ソーシャルネットワーク分析や街路網の最短経路探索など、実生活においても活用されています。
Pythonにおいて、幅優先探索を実装する手順は比較的シンプルであり、dequeを用いたキューの実装や辞書を用いたグラフの表現など、基礎的なデータ構造を使いこなすことが必要です。また、幅優先探索は深さ優先探索と比較して計算量が多くなるため、大規模なグラフに対しては実行時間がかかることがあるため、効率的なアルゴリズムの選択が必要です。
Pythonを用いた幅優先探索の実装は、プログラミング初学者から上級者まで、幅広いレベルの開発者が利用することができます。これまでの解説で紹介した手順と具体例を理解し、実際にコーディングしてみることで、アルゴリズムの基礎を身に付け、プログラミング能力を向上させることができます。dequeを使ってキューを実装することで、簡潔なコードで幅優先探索を実現することができます。
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 [ 米田優峻 ]
