「AIについて学び始めたけど、アルゴリズムってなんだか難しそう…」 「G検定の勉強中だけど、『探索』ってよく聞くけどイマイチわからない…」
そんな風に感じているAI初心者さん、必見です！
AIの世界、特にG検定のシラバスでも重要な位置を占める「探索アルゴリズム」。その中でも、最も基本的でパワフルな手法の一つが「深さ優先探索（Depth First Search, DFS）」です。
実は、このDFS、あなたが迷路を解くときや、インターネットでリンクを次々にクリックしていくときの考え方にちょっと似ています。
この記事では、
- 深さ優先探索（DFS）って、結局なに？
- どういう仕組みで動いているの？（Pythonコード付きで解説！）
- どんなことに使えるの？（G検定頻出の応用例も！）
- G検定対策として、どこを押さえておくべき？
といった疑問に、AI初心者さんにも分かりやすく、図解も交えながら徹底解説していきます。この記事を読めば、DFSの基礎がしっかり身につき、G検定対策も一歩前進すること間違いなしです！
深さ優先探索（DFS）とは？ ～基本のキ～
深さ優先探索（DFS）を一言でいうと、「行けるところまで、とことん深く進んで、行き止まったら戻ってくる探索方法」です。
想像してみてください。あなたが巨大な迷路に入ったとします。ゴールを探すために、どうしますか？
おそらく、まず一つの道を選んで、ひたすら奥へ奥へと進んでいくでしょう。そして、行き止まりにぶつかったら、少し戻って、まだ試していない別の分かれ道を選んで、また奥へと進んでいく… これを繰り返しますよね？
DFSは、まさにこの考え方をコンピュータで実現するアルゴリズムです。主に木構造やグラフ構造と呼ばれる、点（ノード）とそれらを繋ぐ線（エッジ）で構成されたデータを探索する際に使われます。
- スタート地点から出発
- 最初の分岐を可能な限り深く進む (A → B → D など)
- 行き止まり (D) に到達
- 一つ手前の分岐点 (B) に戻る (バックトラック)
- まだ探索していない別の分岐に進む (B → E など)
- これを繰り返し、全ての到達可能なノードを訪問する
このように、「深さ」を優先して探索を進めるのがDFSの最大の特徴です。
DFSはどうやって動くの？ ～2つの実装方法～
DFSの「深く進んで戻る」動きは、主に2つの方法でプログラムとして実装されます。
- 再帰（さいき）を使った方法
- スタックを使った方法（反復）
どちらの方法でも同じ結果になりますが、考え方とコードの書き方が少し異なります。AI初心者さんにも分かりやすいように、Pythonコード例と一緒に見ていきましょう！
1. 再帰を使った方法
「再帰」とは、関数の中で自分自身を呼び出すテクニックです。DFSの「深く進む」動きと相性が良く、コードが比較的シンプルに書けることが多いです。
考え方:
- 現在のノードを「訪問済み」にする。
- 現在のノードに隣接しているノードを一つずつチェックする。
- まだ訪問していない隣接ノードが見つかったら、そのノードを新たな現在ノードとして、自分自身（DFS関数）を呼び出す。
- 全ての隣接ノードをチェックし終わったら（もしくは行き止まりなら）、呼び出し元の処理に戻る（これが自然なバックトラックになります）。
Pythonコード例（再帰）:
Python
# グラフを隣接リスト形式で表現
# 例: AとB、AとC、BとD、BとE、CとFが繋がっているグラフ
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
# 訪問済みノードを記録するセット
visited_recursive = set()
# 再帰を使ったDFS関数
def dfs_recursive(node):
"""
再帰を使って深さ優先探索を行う関数
:param node: 現在のノード
"""
if node not in visited_recursive:
print(f"訪問: {node}") # ノードを訪問したことを出力
visited_recursive.add(node) # 訪問済みにする
# 隣接するノードを一つずつチェック
for neighbor in graph.get(node, []): # graph[node]だとキーが存在しない場合にエラーになるためgetを使う
dfs_recursive(neighbor) # 再帰呼び出し！
# 実行例
print("--- 再帰DFS開始 ---")
dfs_recursive('A') # 開始ノードを'A'とする
print("--- 再帰DFS終了 ---")メリット: コードが直感的で理解しやすい。
デメリット: 探索が非常に深くなると、「スタックオーバーフロー」というエラーが発生する可能性がある（関数の呼び出し階層が深くなりすぎるため）。
2. スタックを使った方法（反復）
「スタック」は、「後入れ先出し（Last-In, First-Out, LIFO）」という特徴を持つデータ構造です。本を積み重ねるのをイメージすると分かりやすいでしょう。最後（上）に置いた本からしか取れませんよね。
考え方:
- 空のスタックを用意し、開始ノードを入れる。
- スタックが空になるまで、以下の処理を繰り返す。
- スタックからノードを一つ取り出す（最後に追加されたもの）。
- そのノードが未訪問なら、「訪問済み」にして、処理を行う（例: 画面に出力）。
- そのノードに隣接する未訪問のノードを全てスタックに入れる。
スタックに後から入れたノード（より深く探索した先で見つかったノード）が次に取り出されるため、自然と深さ優先の動きになります。
- 初期状態：スタックに開始ノード’A’が入る。
- ‘A’を取り出し、訪問済みに。隣接する’B’, ‘C’をスタックに入れる。（スタック: [‘B’, ‘C’]）
- ‘C’を取り出し、訪問済みに。隣接する’F’をスタックに入れる。（スタック: [‘B’, ‘F’]）
- ‘F’を取り出し、訪問済みに。（スタック: [‘B’]）
- ‘B’を取り出し、訪問済みに。隣接する’D’, ‘E’をスタックに入れる。（スタック: [‘D’, ‘E’]）
- …というように、スタックの中身がどう変化していくかを図示する。
Pythonコード例（スタック）:
Python
# グラフは再帰版と同じものを使用
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
# 訪問済みノードを記録するセット
visited_iterative = set()
# スタックを使ったDFS関数
def dfs_iterative(start_node):
"""
スタックを使って深さ優先探索を行う関数（反復版）
:param start_node: 開始ノード
"""
stack = [start_node] # スタックを初期化し、開始ノードを入れる
while stack: # スタックが空になるまでループ
node = stack.pop() # スタックからノードを取り出す (LIFO)
if node not in visited_iterative:
print(f"訪問: {node}") # ノードを訪問したことを出力
visited_iterative.add(node) # 訪問済みにする
# 隣接するノードをスタックに追加
# 逆順で追加すると、再帰版と訪問順が近くなることが多い（必須ではない）
for neighbor in reversed(graph.get(node, [])):
if neighbor not in visited_iterative: # 未訪問の隣接ノードのみスタックへ
stack.append(neighbor)
# 実行例
print("\n--- 反復DFS開始 ---")
dfs_iterative('A') # 開始ノードを'A'とする
print("--- 反復DFS終了 ---")メリット: 探索が深くなってもスタックオーバーフローの心配がない。
デメリット: 再帰版に比べて、コードが少し複雑に見えるかもしれない。
DFSって何がすごいの？ ～特徴とメリット・デメリット～
DFSの仕組みが分かったところで、その特徴、良い点（メリット）、少し注意が必要な点（デメリット）を整理しましょう。これは、もう一つの有名な探索アルゴリズム「幅優先探索（BFS）」と比較すると分かりやすいです。
DFSの主な特徴:
- 深さ優先: とにかく行けるところまで深く進む。
- バックトラック: 行き止まりや訪問済みの場所に来たら、戻って別の道を探す。
- スタックベース: 再帰（内部的にスタック使用）または明示的なスタックで実装される。
メリット:
- 実装が比較的シンプル: 特に再帰版は直感的に書きやすい。
- ゴールが深い場所にあれば高速な可能性: 運良くゴールの方向に深く進めば、幅広く探索するBFSより早く見つかることがあります。
- 省メモリな場合がある: 探索中の経路（一本道）に関する情報だけを覚えておけば良いので、横に広く探索して多くのノード情報を一時的に保持する必要があるBFSに比べて、メモリ使用量が少なく済むことがあります（特にグラフが縦長の場合）。
デメリット:
- 最短経路を見つける保証はない: 最初に見つけた経路が、必ずしも最短であるとは限りません。より浅い場所にあるゴールを見逃して、遠回りしてしまう可能性があります。（※最短経路探索ならBFSの方が得意です）
- 無限ループの可能性: グラフにサイクル（ぐるっと回って戻ってこれる経路）があると、訪問済みチェックをしっかりしないと無限に同じ場所を回り続けてしまう可能性があります。
- ゴールが浅い場所にあると非効率な場合も: ゴールがスタート地点のすぐ近くにあっても、DFSはまず関係ない方向に深く探索してしまうかもしれません。
- DFS: スタートから一本の経路を深く掘り進んでいく様子。
- BFS: スタートから近い順に、同心円状（レベルごと）に探索範囲が広がっていく様子。
DFSはどこで使われているの？ ～AI・G検定頻出の応用例～
DFSはそのシンプルさと特性から、様々な場面で活躍しています。G検定でも問われやすい、代表的な応用例を見てみましょう。
- 経路探索:
- 迷路の解を見つける。
- ゲームでキャラクターが目的地まで移動できる経路を探す。
- ネットワークで二つのコンピュータが繋がっているか調べる。
- 連結成分の検出:
- SNSの友人関係グラフなどで、繋がりのあるグループ（コミュニティ）を見つける。
- 地図データで、道路で繋がっている地域の塊を特定する。
- トポロジカルソート:
- 大学の履修科目など、前提条件のあるタスクの実行可能な順序を決める（例:「統計学入門」を履修してから「機械学習」を履修する）。これは有向非巡回グラフ（DAG）という特殊なグラフで使われます。
- ゲームAI（人工知能）:
- チェスや将棋、囲碁などのゲームAIが、「もしこの手を打ったら、相手はこう打ってきて…」と、可能な手を深く読み進める（探索する）際に使われます。特にミニマックス法やその改良版であるアルファベータ法といったアルゴリズムの内部で、DFSの考え方が活用されています。（G検定シラバスの「探索・推論」の重要テーマです！）
- ハノイの塔:
- 有名なパズル問題「ハノイの塔」の標準的な解き方（再帰的な手順）は、まさにDFSの考え方に基づいています。問題を小さな問題に分解して深く掘り下げていく様子がDFSと共通しています。（これもG検定シラバスで触れられていますね！）
このように、DFSは多くのアルゴリズムの基礎となる、非常に重要な考え方なのです。
【G検定対策ポイント】DFSと関連キーワード
G検定合格を目指す上で、DFSについて押さえておくべきポイントと、関連キーワードをまとめます。
G検定におけるDFSの位置づけ:
- シラバスの主要項目「探索・推論」における、最も基本的なアルゴリズムの一つです。
- 第一次AIブーム（1950年代後半～1960年代）では、この「探索」がAI研究の中心的なテーマでした。DFSのようなアルゴリズムが、当時のAI（主にパズルやゲームを解くもの）の基礎を支えていました。
セットで覚えるべき重要キーワード:
- 幅優先探索 (BFS): DFSとの違い（探索順序、使うデータ構造:キュー、最短経路保証の有無）をしっかり理解しておくことが最重要です。比較問題は頻出です。
- 探索木 (Search Tree): DFSやBFSが探索を進める過程を、木のような図で表したもの。ノードが状態、エッジが遷移を表します。
- バックトラック (Backtracking): DFSの基本動作。行き詰まったら戻ること。
- スタック (Stack): DFS（反復）で使うデータ構造（LIFO）。
- 再帰 (Recursion): DFS（再帰）で使うプログラミング技法。
- 計算量 (Computational Complexity): アルゴリズムの効率を表す指標。DFSの計算量は、グラフの頂点数をV、辺数をEとすると O(V + E) となります。「全ての頂点と辺を基本的に1回ずつチェックするから、このくらいの時間がかかるんだな」くらいの理解でOKです。
- 有向非巡回グラフ (DAG): トポロジカルソートが可能なグラフの種類。
これらのキーワードの意味と、DFSとの関連性を理解しておけば、G検定の探索・推論に関する問題に対応しやすくなります。
まとめ
今回は、AIの基礎でありG検定でも重要な「深さ優先探索（DFS）」について、その仕組みからPythonコード例、応用、対策ポイントまで解説しました。
DFSの重要ポイント:
- 「行けるところまで深く進み、行き詰まったら戻る」探索方法。
- 再帰またはスタックを使って実装できる。
- 経路探索やゲームAIなど、様々な場面で使われる基礎技術。
- BFSとの違いを理解することが重要。
DFSは、一見難しそうに感じるかもしれませんが、基本的な考え方は迷路探索と同じで、意外とシンプルです。この記事のPythonコードを実際に動かしてみたり、図を見ながら動きを追いかけたりすることで、さらに理解が深まるはずです。
AIやアルゴリズムの世界は奥が深いですが、DFSのような基礎を一つずつマスターしていくことが、G検定合格、そしてその先のAI活用への着実な一歩となります。
この記事を読んで、DFSについてもっと知りたいことや、分かりにくかった点はありますか？ ぜひコメントで教えてくださいね！
コメント