【G検定過去問風テスト】幅優先探索と深さ優先探索の違いと特徴を理解しよう！
※本記事では、アフィリエイトプログラムより教材を紹介しています。
📝 問題
探索木を探索する手法である「幅優先探索」と「深さ優先探索」に関する記述として、最も適切な選択肢を1つ選べ。
- A）幅優先探索は、スタート地点から1つのルートを縦方向に突き進み、行き止まりになったら前の分岐点まで戻る手法であるため、メモリの消費量が非常に多い。
- B）深さ優先探索は、スタート地点に近い階層から横方向に順番にすべて調べていく手法であり、最初に見つかったゴールが必ず最短ルートになる。
- C）幅優先探索は、同じ階層の選択肢を横方向に網羅しながら探索するため、必ず最短ルートでゴールを見つけることができるが、途中の選択肢を記憶しておく必要がありメモリ消費量が大きい。
- D）深さ優先探索は、縦方向へ深く掘り下げて探索するため、幅優先探索と比べて計算効率が常に優れており、必ず最短ルートでゴールを見つけることができる。
🔍 ここをクリックして正解を見る
- 正解: C）幅優先探索は、同じ階層の選択肢を横方向に網羅しながら探索するため、必ず最短ルートでゴールを見つけることができるが、途中の選択肢を記憶しておく必要がありメモリ消費量が大きい。
💡 合格に近づく！徹底解説
- 重要度: ★★★
■ 1分で分かる！この問題の要点
- 幅優先探索は「横方向（同じ深さ）」に平たく探索します。最初に見つけたゴールが必ず「最短ルート」になりますが、すべての分岐を記憶するためメモリを大量に消費します。
- 深さ優先探索は「縦方向（奥深く）」に突き進みます。行き止まりになったら戻る（バックトラック）ためメモリの消費は少ないですが、最初に見つけたゴールが最短ルートとは限りません。
■ 初学者向け解説（例え話や背景）
この2つの違いは、試験で最も「あべこべ」のひっかけ問題が作られやすい超重要ポイントです。
- 幅優先探索は「お掃除ロボットの丁寧なお部屋掃除」
スタート地点から同心円状に、じわじわと周囲をまんべんなく（横に）探索していきます。だから、一番近い壁（ゴール）を見つけたときは、それが自動的に「最も近い（最短の）壁」になります。ただし、部屋全体のマップ（通ったルート）をたくさん覚えておかなければならないため、ロボットの脳みそ（メモリ）をたくさん使います。 - 深さ優先探索は「迷路でひたすら壁づたいに奥へ突き進む人」
目の前の道を「行き止まり」にぶつかるまでトコトンまっすぐ突き進みます。行き止まりになったら、1つ手前の分岐点に戻って別の道を試します。この方法なら、いま歩いている1本のルートだけを覚えておけばいいので、脳みそ（メモリ）は節約できます。しかし、たまたま最初に見つけたゴールが、実はものすごく遠回りしたルートだった……ということが起こり得るのです。
■ 選択肢の解説
- A) 幅優先探索は、スタート地点から1つのルートを縦方向に突き進み...（×）: 縦方向に突き進み、行き止まりから戻る（バックトラックする）のは「深さ優先探索」の特徴です。
- B) 深さ優先探索は、スタート地点に近い階層から横方向に順番に...（×）: 横方向に順番に調べていくのは「幅優先探索」の特徴です。
- C) 幅優先探索は、同じ階層の選択肢を横方向に網羅しながら探索するため、必ず最短ルートでゴールを見つけることができるが、途中の選択肢を記憶しておく必要がありメモリ消費量が大きい。（○）: 幅優先探索の特徴（横方向、最短ルート保証、メモリ消費大）をすべて正しく説明しています。
- D) 深さ優先探索は、縦方向へ深く掘り下げて探索するため...必ず最短ルートでゴールを見つけることができる。（×）: 深さ優先探索では、最初に見つかった解が最短ルートであるとは限りません。
👉 次の問題＆解説テキスト
お疲れ様です！
この調子で次の問題に挑戦しますか？
それとも、立ち止まって詳しい解説を確認しますか？
