G検定（ジェネラリスト検定） 人工知能とその動向 練習問題 第43問: 節点S、A、B、C、D、Gからなる有向グラフで、SからGへの経路を探す。辺は矢印の向きにだけ進め、辺とそのコストは、S→A：1、S→B：4、S→C：2、A→B：

最小コスト優先探索が返すのは、コストの合計が最も小さい経路S→C→D→G（2＋2＋2＝6）です。Poole・Mackworthの教科書（第3版）の3.5.4節によると、この探索は最前線（フロンティア）を経路のコストの優先度付きキューとして扱い、コストの小さい経路から展開するので、最初に取り出されたゴールへの経路がコスト最小になります。

S→B→Gは、辺の数が最も少ない経路（4＋6＝10）で、幅優先探索が最初に見つける経路です。S→A→B→Gは、各節点で最も安い辺を選んでいった経路（1＋1＋6＝8）です。

S→A→C→D→Gは、辺1本あたりの平均コストが最も小さい経路（7÷4＝1.75）ですが、合計は7で最小ではありません。辺の数が最少の経路や目先の安い辺が、コスト最小とは限らない点を押さえましょう。