Tip:
Highlight text to annotate it
X
ここまでアルゴリズムを2つ調べてきました。
一つは、幅優先探索で、常に近くの経路、
最短の経路へと拡張します。
二つ目が、最低コスト優先探索で、常に
合計コストが最低となる経路へ最初に拡張します。
三番目のアルゴリズムとして、深さ優先探索を紹介していきたいと思います。
これは、幅優先探索と逆のやり方になります。
深さ優先探索では、常に最初に最長の経路、
すなわち一番距離の長い経路へと拡張します。
さて、そこで質問ですが、ここにあるそれぞれの木の各ノードが、
どのように拡張されていくのか、考えてみてください。
1番、2番、3番、という感じに、拡張されていく順にボックスに番号を入れていってください。
もし同じ順位のものがある場合には、左から右の順序で、優先度を決めてください。
さらにもう一つ答えてもらいたい質問があります。
これらの探索アルゴリズムのうちで最適なものはどれでしょうか?
すなわち、どれが確実に最適な解を見つけ出すでしょうか?
幅優先探索において最適とは、最短の経路を見つけ出すことです。
もし確実に最短の経路が判明できると思うなら、ここをチェックしてください。
最低コスト優先では、経路の合計コストが一番低くなる経路を見つけ出すことです。
もし確実に最低コストが見つかると思う場合は、ここをチェックしてください。
前提条件として、コストは全て正であるとします。
最後に、深さ優先における、最低、もしくは最適とは、
長さに関して、最短の経路を見つけることです。
深さ優先探索がいつも必ず最短の経路を見つけ出せると思う場合は、ここをチェックしてください。