Now Loading...

Now Loading...

深さ優先探索

深さ優先探索

コンピュータで迷路の問題を解く時、探索木の始点から場合分けを続けて終点にたどり着く経路が見つかれば、それが迷路の回答になります。このとき、探索にかかる時間は検索する方法によって変わり、主に2つの手法があります。
深さ優先探索では、あるノードから行き止まりになるまで進み続け、行き止まりになったら1つ手前のノードに戻って探索を行うということを繰り返します。深さ優先探索の場合、解が見つからなければ一つ手前のノードに戻って探索し直せばよいので、幅優先探索と比べてあまりメモリを必要としません。しかし、解が見つかったとしても、それが最短距離でゴールにたどり着く解であるとは限らないというデメリットがあります。

クイズ

迷路を場合分けの問題としてコンピュータに与えて解くときに適切なアルゴリズムがある.これは木のような構造をしており,条件の場合分けに対応して枝が分岐し,枝を辿ることで目的の条件に合致するものが見つかるという発想に基づいている.枝を探索する方法の一つに,探索にメモリを大量に必要としない代わりに必ずしも見つけた経路がゴールへの最短経路とは限らないものがある.この方法の名前として最も適切な選択肢を1つ選べ.
  • 正解を見る
  • 解説を見る
    幅優先探索とは探索の途中のノードを全て記憶しておく必要がある為,大量のメモリが必要となります.一方深さ優先探索では一旦行き止まりのノードまで行き解が見つからない場合は分岐までもどる,という方法をとる為,メモリはそれほど必要としません. (参考: G検定公式テキスト 第2版 第2章 2-1 P39-40) (参考: G検定公式テキスト 第1版 P18-22 探索・推論)

特別割引クーポンのお知らせ

<人工知能基礎&G検定実践問題集>

・クーポン:aibgt220920-2bso
・有効期間:2022年10月21日(金)

*使い方:以下バナーより「購入する」に進んでいただき、左下のクーポン欄にご記入、適用してください。

zero to one G検定 jdla

<G検定実践トレーニング>

・クーポン:gt220920-1dao
・有効期間:2022年10月21日(金)

*使い方:以下バナーより「購入する」に進んでいただき、左下のクーポン欄にご記入、適用してください。

zero to one G検定 jdla