G検定（ジェネラリスト検定） 人工知能とその動向 練習問題 第37問: Poole・Mackworthの教科書（第3版）の3.7節が説明する、グラフの探索での枝刈りに関する記述として、最も不適切なものはどれか。

肢2が不適切です。同節によると、深さ優先探索は、展開した経路の末端の節点を残らず記録しておく必要がありません。

多重経路の枝刈りのためにそれらを記録すると、深さ優先探索の記憶量は指数的になります。そのため、深さ優先探索にもとづく方法では閉路の枝刈りが好まれ、多重経路の枝刈りは、ほぼ全部の節点を記録することになる幅優先の方法で好まれます。

肢1のとおり、閉路の枝刈りは経路の最後の節点が開始点からの経路にすでに現れていないかを確かめるもので、深さ優先の方法では現在の経路を集合として持てば手間は定数倍程度で済みます。肢3のとおり、多重経路の枝刈りは閉リストを使い、閉路の枝刈りの働きを含みます。

肢4について、同節は多重経路の枝刈りが最小コストの経路を捨てないとは限らないとし、最小コスト優先探索のように最初に見つけた経路が最小コストになる方法なら問題ないとしています。