深さ優先探索の特徴

• 空間計算量（メモリ使用量）はそこそこ．

  • 分岐度b，最大深さmの状態空間で，最大bmのメモリを使う．

• 時間計算量はO（bm）．

  • 多くの解がある問題に大しては，深さ優先のほうが幅優先より早いことが多い．

しかし．．．

• 解を見逃すかもしれない．（探索が完全でない）

  • ある経路の深さが大きい，または無限大の場合．

• 最適でない解を見つけるかもしれない．（探索が最適でない）

前のｽﾗｲﾄﾞ

次のｽﾗｲﾄﾞ

最初のｽﾗｲﾄﾞに戻る

ｸﾞﾗﾌｨｯｸｽの表示