メインコンテンツへスキップ
見出し画像

【第26回】AIは近くから探す?奥まで進む?幅優先探索と深さ優先探索とは

    AIが道を探す方法には、大きく分けて2つあります。
    近くから順に見る「幅優先探索」と、奥まで進む「深さ優先探索」です。
    この記事では、この2つの違いと使い分けをやさしく解説します。


    1. 読み方

    • 幅優先探索(はばゆうせんたんさく) / Breadth-First Search (BFS)

    • 深さ優先探索(ふかさゆうせんたんさく) / Depth-First Search (DFS)


    2. 意味(定義):波紋のように広がるか、一本道を突き進むか

    この2つは、探索の「順番」が全く異なります。

    🌊 幅優先探索(BFS):「波紋」スタイル

    スタート地点から「近い順」に探していく方法です。 まず、スタートのすぐ隣にある道(1手先)をすべてチェックします。次に、その隣にある道(2手先)をすべてチェック、というように、まるで水面に投げた石が作る「波紋」のように、同心円状に範囲を広げていくスタイルです。

    • ✨ 特徴: 探索の過程で最初にゴールを見つけたとき、それが必ず「最短ルート」になります。

    🔦 深さ優先探索(DFS):「探検家」スタイル

    とにかく「行けるところまで、深く」進んでいく方法です。 分かれ道に出会ったら、とりあえず片方の道を突き当たり(行き止まり)まで進みます。もし行き止まりだったら、「あ、失敗だ」と戻って(バックトラック)、別の道へ進む、というように、一本の道を掘り進める「探検家」のようなスタイルです。

    • ✨ 特徴: メモリの消費は少ないですが、最初に見つけたゴールが最短ルートであるとは限りません(運が悪いと、ものすごく遠回りの道を見つけてしまう可能性があります)。


    3. 歴史・背景:グラフ理論から生まれた「迷路攻略術」

    これらの手法は、コンピュータが誕生するよりも前、数学における「グラフ理論(点と線でつながった図形を扱う学問)」に基づいています。

    初期のAI開発において、「パズルを解く」「チェスの次の一手を考える」といった問題に取り組む際、科学者たちは大きな壁にぶつかりました。

    前回の記事でお話しした「ブルートフォース(全部試す)」では、選択肢が少し増えるだけで、計算が終わらなくなるからです。

    そこで必要になったのが、「探索の順番にルールを持たせる」という知恵でした。

    • 「とにかく近くから網羅的に見る(幅優先)」

    • 「とりあえず行き止まりまで突き進む(深さ優先)」

    このように、データの辿り方に戦略的なルールを加えることで、計算量を劇的に減らすことが可能になったのです。

    この「いかに効率よく最短ルートを見つけるか」という課題は、コンピュータの処理能力が爆発的に向上した現代においても、AI開発における永遠のテーマです。

    計算リソース(メモリや時間)が限られていた黎明期から、現代のスーパーコンピュータに至るまで、これらのアルゴリズムはAIの思考プロセスを支える根幹の技術として君臨し続けています。


    4. 比較・対比:どっちがどんな時に強い?

    入り口から出口に向かう「迷路」を想像しながら、その違いを整理してみましょう。 スタート地点を進むと、左右の分かれ道が現れます。

    ■ 幅優先探索(BFS)

    • 探す順番: 左右どちらの道へも進んで、その先を確認します。近くの選択肢をすべて網羅してから、遠くへ進む。という、「横(広さ)」に広がるイメージです。

    • 強み: 迷路において、「最短ルート(最も近い出口)」を見つけるのが得意です。

    • 弱点: 探索範囲がどんどん広がるため、メモリ(記憶容量)を大量に消費してしまいます。

    ■ 深さ優先探索(DFS)

    • 探す順番: 左右の道があっても、まずはどちらか一方の道を突き進みます。行き止まりに当たったら戻って別の道へ。という、「縦(深さ)」に進むイメージです。

    • 強み: 行き止まりまで進むだけなので、メモリの消費が比較的少ないのが特徴です。

    • 弱点: たまたま見つけた出口が、実はものすごく遠い道のり(非効率なルート)である可能性があります。

    💡 例え話:「失くしたスマホを探す」とき

    • 幅優先スタイル: まず、ポケットやカバン、机の上や足元など、「手の届く範囲」をすべてチェック。次に、今いる部屋の中へと、少しずつ範囲を広げていく。という探し方です。

    • 深さ優先スタイル: 「まずはリビング!」と決めて、リビングの机の下、ソファの隙間、棚の奥など、一つの場所を徹底的に突き詰めて探す。見つからなければ隣の部屋へ移動して、また深く探す。という探し方です。

    (※現実的にはスマホに電話したり、位置情報で探したりするのが一番早いですが、あくまでアルゴリズムのイメージです!笑)


    5. 活用シーン:私たちの身近なところで使われている!

    ■ 幅優先探索(BFS)の活躍

    • SNSの「友達のつながり」: 「知り合い」→「友人の友人」と、距離が近い順に探すとき。

    • カーナビ・地図アプリ: 現在地から、最も手数の少ない(最短の)ルートを計算するとき。

    • Webクローラー: インターネット上のリンクを、関連性の高いサイトから順番に巡回するとき。

    ■ 深さ優先探索(DFS)の活躍

    • 迷路・パズルの解法: 「とにかく一筋縄ではいかない道を突き進む」というアルゴリズムの実装。

    • 数独(ナンプレ)などのパズル: 数字を埋めていき、矛盾が出たら戻ってやり直す(バックトラック)とき。

    • タスクの依存関係チェック: 「Aが終わらないとBができない」といった、作業手順の順序を整理するとき。


    6. G検定での出題傾向

    G検定では、単なる用語の意味だけでなく、「条件付きの使い分け」が狙われます!以下のポイントを重点的に押さえましょう。

    • 「最短ルート」と「重み」の罠: 「重み(コスト)のないグラフにおいて、最短経路を見つけるのに適しているのは?」と問われたら、迷わず幅優先探索を選びましょう。※逆に、道によってコストが違う場合は別の手法が必要になります。

    • メモリ使用量の対比: 「探索範囲が広がるためメモリを多く消費するのはどちらか?(=幅優先)」、「メモリの消費が比較的少ないのはどちらか?(=深さ優先)」という、リソースに関する比較が出題されます。

    • アルゴリズムの基本動作: どちらが「横(広さ)に広がるか」、「縦(深さ)に突き進むか」という、探索の方向性の違いを理解しておきましょう。

    • データ構造との関連(重要!): 少し高度ですが、仕組みとして使われるデータ構造の名前もセットで覚えましょう。

      • 幅優先探索 → キュー(Queue):先入れ先出し

      • 深さ優先探索 → スタック(Stack):後入れ先出し

    • 「バックトラック(後戻り)」のプロセス: 深さ優先探索の説明として、「行き止まりに当たったら、前の分岐点まで戻って別の道を試す」というバックトラックという言葉がセットで出題されることが非常に多いです。


    実際の試験形式をイメージして、解いてみましょう。

    【問題1:最頻出】

    グラフ探索において、スタート地点から近い順に(階層ごとに)探索を進め、重みのないグラフにおいて最短経路を見つけることができる手法はどれですか?

    • A. 深さ優先探索

    • B. 幅優先探索

    • C. ブルートフォース法

    • D. ヒューリスティック法

    【問題2:頻出】

    深さ優先探索(DFS)の説明として、最も適切なものはどれですか?

    • A. 探索範囲を同心円状に広げていき、すべてのノードを網羅する手法である。

    • B. 行き止まりに到達するまで一つの道を突き進み、その後、分岐点まで戻って別の道を試す手法である。

    • C. 経験に基づいた推測を用いて、正解に近い道から優先的に探索する手法である。

    • D. すべての組み合わせを順番に一つずつ試していく、最も原始的な手法である。

    【問題3:メモリ使用量とアルゴリズム】

    探索木の構造において、探索の過程で「次に探索すべきノード(分岐点)をすべて保持しておく必要がある」ため、メモリ消費量が多くなりやすい手法はどれですか?

    • A. 深さ優先探索 (DFS) 成立

    • B. 幅優先探索 (BFS)

    • C. 枝刈り (Pruning)

    • D. バックトラッキング (Backtracking)

    【問題4:ひっかけ】

    深さ優先探索(DFS)に関する記述として、誤っているものはどれですか?

    • A. 探索のプロセスにおいて、バックトラック(後戻り)という動作が含まれる。

    • B. 幅優先探索に比べ、探索中に保持すべきノードの情報(メモリ消費)が少なくて済む場合が多い。

    • C. 迷路の探索において、必ずしも最短ルートを見つけられるとは限らない。

    • D. 探索の範囲を「横方向」へ広げていくことで、効率的に解を見つける手法である。


    8. 例題の回答と解説

    【問題1】 正解:B

    • 解説: 「近い順に」「最短経路」というキーワードは、幅優先探索の決定的な特徴です。

    【問題2】 正解:B

    • 解説: 「突き進む」「分岐点まで戻る(バックトラック)」というプロセスは、深さ優先探索そのものです。

    【問題3】 正解:B

    • 解説: 幅優先探索は、現在の階層にあるすべてのノードを「次に探すリスト」として保持し続ける必要があるため、メモリ消費が非常に大きくなります。

    【問題4】 正解:D

    • 解説: 「横方向へ広げていく」のは幅優先探索の特徴です。深さ優先探索は「縦(深さ)方向」に突き進みます。


    📝 総評・まとめ

    今回のテーマを整理しましょう!

    • 幅優先探索(BFS): 「波紋」のように広がる。最短ルートを見つけるのが得意だが、メモリを食う。

    • 深さ優先探索(DFS): 「探検家」のように深く進む。メモリ消費が少ないが、最短ルートとは限らない。

    この2つの使い分けこそが、AIが「効率的に」問題を解くための第一歩なのです。


    🚀 次回予告

    幅、深さ。でも、これよりもっと良い方法がありそう。 もし、探索の途中で『あっちの道は明らかに間違いだ!』と判断できたら、もっと速くなれるはず。

    次は、無駄な枝を切り落とす究極のテクニック、【第27回】AIは相手の手を先読みできる?Mini-Max法とは です。お楽しみに!


    【第27回】へ進む

    【第2章】へ戻る

    📚 シリーズトップへ戻る

    ✅ この記事が役に立ったら「スキ」で応援してください!
    あなたの応援が、次の解説を作るエネルギーになります!🚀

     
     
    【G検定合格ロードマップ】 AIを「挫折と突破の物語」で理解し、最短で合格するメソッドを発信。 難しい専門用語を簡単な言葉でストーリー化して解説します。 丸暗記を捨て、効率的に重要キーワードを習得したい方は必見です

    あなたへのおすすめ