深さ優先探索
深さ優先探索
コンピュータで迷路の問題を解く時、探索木の始点から場合分けを続けて終点にたどり着く経路が見つかれば、それが迷路の回答になります。このとき、探索にかかる時間は検索する方法によって変わり、主に２つの手法があります。
深さ優先探索では、あるノードから行き止まりになるまで進み続け、行き止まりになったら１つ手前のノードに戻って探索を行うということを繰り返します。深さ優先探索の場合、解が見つからなければ一つ手前のノードに戻って探索し直せばよいので、幅優先探索と比べてあまりメモリを必要としません。しかし、解が見つかったとしても、それが最短距離でゴールにたどり着く解であるとは限らないというデメリットがあります。
クイズ
迷路を場合分けの問題としてコンピュータに与えて解くときに適切なアルゴリズムがある．これは木のような構造をしており，条件の場合分けに対応して枝が分岐し，枝を辿ることで目的の条件に合致するものが見つかるという発想に基づいている．枝を探索する方法の一つに，探索にメモリを大量に必要としない代わりに必ずしも見つけた経路がゴールへの最短経路とは限らないものがある．この方法の名前として最も適切な選択肢を１つ選べ．
- 正解を見る
- 解説を見る幅優先探索とは探索の途中のノードを全て記憶しておく必要がある為，大量のメモリが必要となります．一方深さ優先探索では一旦行き止まりのノードまで行き解が見つからない場合は分岐までもどる，という方法をとる為，メモリはそれほど必要としません．
（参考: G検定公式テキスト 第2版 第2章 2-1 P39-40）
（参考: G検定公式テキスト 第１版 P18-22 探索・推論）👉G検定の受験対策は約1,000問収録の「G検定実践トレーニング」へ
深さ優先探索を体験できる記事を紹介！
下記のリンク先にてPythonのコードを用いて実際に深さ優先探索のアルゴリズムを実行できる記事を公開中。ぜひご覧ください。
👉より体系的に学びたい方は「人工知能基礎」（東京大学松尾豊先生監修）へ
人工知能基礎講座を提供中
人工知能の第一人者である東京大学の松尾豊教授が監修した人工知能基礎講座を受講してみませんか？
人工知能の歴史から自然言語処理、機械学習、深層学習といった最先端のトピックやAIに関わる法律問題まで網羅しているので全てのビジネスパーソン・AIの初学者におすすめです。
サンプル動画
人工知能基礎講座はこちら↓
AI初学者・ビジネスパーソン向けのG検定対策講座
G検定受験前にトレーニングしたい方向けの問題集「G検定実践トレーニング」も提供中です。
zero to oneの「E資格」向け認定プログラム
日本ディープラーニング協会の実施するE資格の受験ならzero to oneの「E資格」向け認定プログラム (税込165,000円) をおすすめします。当講座は、東京大学大学院工学系研究科の松尾豊教授と東北大学大学院情報科学研究科の岡谷貴之教授が監修する実践的なプログラムとなっています。
厚生労働省の教育訓練給付制度対象のE資格認定プログラムの中では最安値※となり、実質負担額49,500円～(支給割合70%の場合)で受講可能です。※2023年弊社調べ
