Tip:
Highlight text to annotate it
X
それでは正解です。
幅優先探索は、その名前が示すように、ノードをこの順番に展開していきます。
1、2、3、4、5、6、7 と
拡張のたびに、このように横方向に探索していきます、幅優先です。
これは最適でしょうか?
そうですね、これはいつも、まず最短の経路へと拡張していきますから、
どこに終状態が隠れていようと、経路が他より短いことを確認しながら、
終状態を見つけるので 、つまり、最適だということです。
最低コスト優先は、ます長さが0の経路から拡張し、
次に長さが2の経路に進みます。
その次は長さが4、次は長さが5、
長さ6、長さ7、そして最後に長さ8です。
このように、全ての経路で一番コストの低いものを見つけますから、
個々のコストがマイナスになる箇所がない限りは、確実です。
深さ優先探索は、まず、一番深い場所に進もうとします。
つまり、1から2に行き、3に到達したら、4に行き、
そして戻って、5、6、7です。
これからわかるように、必ずしも最短のものを見つけるとは限りません。
例えば、終状態が5と3にあるとしましょう。
すると3に続く長い方の経路をたどって、そこに終状態を見つけてしまい、
5の位置の終状態は探しません。
つまり、最適ではないということです。