G検定（ジェネラリスト検定） 人工知能とその動向 練習問題 第7問: 幅優先探索と深さ優先探索に関するAからDまでの記述のうち、適切なものをすべて挙げた組合せはどれか。 A　幅優先探索は、解が存在すれば、たどる辺（弧）の数が最も少

正解: 3. A、C

Aは適切です。Poole・Mackworthの教科書『Artificial Intelligence: Foundations of Computational Agents』（第3版）は、幅優先探索は解があれば見つけ、しかも辺の数が最も少ない解を見つけると説明しています。Bは不適切で、深さ優先探索は1本の経路を最後まで調べてから戻るため、浅い位置の解より先に長い経路の解を見つけることがあります。Cは適切で、同書は深さ優先探索の使う記憶量が、開始点から現在の節点までの辺の数に比例すると説明しています。Dは不適切で、閉路や無限の経路にはまって止まらないことがあるのは深さ優先探索の弱点です。幅優先探索の弱点は、記憶量が解の深さに対して指数的に増えることです。したがって適切なものは A、C で、正解は3です。

関連キーワード: 幅優先探索・深さ優先探索・探索木