探索アルゴリズムの比較

問題

探索アルゴリズムに関する次の記述のうち、誤りを1つ選べ。

探索アルゴリズムにおいて、幅優先探索（BFS）は近い状態から順に探索するため最短経路を見つけやすい反面、記憶しておくべき状態が多くなりメモリ消費が激しいです。

一方、深さ優先探索（DFS）はメモリ消費が少ない反面、見つかった解が最短経路とは限らないという特徴があります。

それぞれ一長一短があるため、扱う問題の性質（探索空間の広さやゴールまでの深さなど）に応じて適切なアルゴリズムを選択する必要があります。

1. 幅優先探索は最短経路を見つけやすい。

正しい：幅優先探索は開始状態から同じ距離（階層）にあるすべてのノードを順に調べるため、最初に見つかったゴールへの経路が最短経路であることが保証されます。

2. 深さ優先探索はメモリ効率が良い。

正しい：深さ優先探索は現在探索中の経路のみを記憶しておけばよいため、全方位に探索を広げる幅優先探索に比べてメモリ消費量を少なく抑えることができます。

3. 幅優先探索と深さ優先探索は、どちらも探索順序がランダムに決定されるため、同じ問題でも毎回異なる経路が得られる。

誤り：幅優先探索と深さ優先探索は、データ構造（キューやスタック）やルールに基づいて決まった順序でノードを展開する「決定論的」なアルゴリズムであり、ランダム性はありません。

4. 探索アルゴリズムは問題の性質に応じて選択する必要がある。

正しい：探索空間の広さ、メモリの制限、最短経路が必要かどうかなど、解きたい問題の制約や性質に合わせて適切なアルゴリズムを使い分ける必要があります。

← 前の問題次の問題 →

📚 より詳細を学びたい方へ