① 人工知能の基礎と動向 ／ 3. 探索・推論
深さ優先探索とは
深さ優先探索とは、1本の枝を可能な限り深くたどり、行き止まりに達したら戻って別の枝を試す探索手法です。メモリ効率がよい一方、最短経路を保証しない点が幅優先探索との決定的な違いです。
この用語はG検定シラバスの「3. 探索・推論」に含まれます。 章全体の用語は用語解説①（全54語）にまとまっています。
一言でいうと
行けるところまで深く進み、行き止まりで戻ってやり直す探索方法です。メモリは節約できます。
探索の順序
ある枝を選んだら、行き止まりになるまで進み続けます。行き止まりに達したら1つ前に戻り（バックトラック）、まだ試していない別の枝を選びます。
長所と短所
現在たどっている経路だけを覚えておけばよいため、メモリ効率に優れます。
一方、たまたま長い経路で先にゴールへ到達することがあるため、最初に見つけた経路が最短とは限りません。また、枝が非常に深い（あるいは無限に続く）場合は探索が終わらない危険もあります。
どんなときに向くか
解が深い位置にあると見込める場合や、「条件を満たす解が1つ見つかればよい」場合に向きます。
行き止まりで1つ前に戻ることをバックトラックと呼びます。この戻る仕組みがあるため、記憶しておくのは現在たどっている経路だけで済み、メモリ効率がよくなります。
混同しやすい用語との違い
| 用語 | ポイント |
|---|---|
| 深さ優先探索 | 1本の枝を深くたどる。メモリ効率よい／最短経路は保証しない |
| 幅優先探索 | 浅い階層から横に探索。最短経路を保証／メモリ消費大 |
🎯 G検定での押さえどころ
- メモリ効率がよい
- 最短経路は保証しない
- 幅優先探索との対比で押さえる
⚠️ よくある誤りの選択肢
- 「深さ優先探索は最短経路を必ず見つけられる」→ 誤り。保証しません
- 「深さ優先探索はメモリ消費が大きい」→ 誤り。メモリ効率に優れます
関連する用語
ご利用にあたって 本ページの内容は、JDLAが公開しているG検定シラバス2024や公式テキストなど、一般に公開されている情報をもとに独自に整理・解説したものです。実際の試験の出題内容を示すものではなく、また合格を保証するものでもありません。制度・法令・試験要項は変更されることがあるため、最新の情報は必ずJDLA公式サイトでご確認ください。