幅優先探索（BFS）の理解

問題

幅優先探索（Breadth-First Search）に関する次の記述のうち、正しいものを1つ選べ。

幅優先探索（BFS）は、開始ノードから近い階層（深さ）にあるノードをすべて探索してから、次の階層へと進むアルゴリズムです。

全ての経路を同じペースで進めるため、ゴールが見つかった時点でそれが「最短経路」であることが保証されます。

しかし、探索中のすべての状態（ノード）をメモリに保持しておく必要があるため、探索空間が広いとメモリ消費が急激に増大（メモリ枯渇）するという欠点があります。

1. 幅優先探索は近い階層から順に探索するため、最短経路を見つけやすい。

正しい：BFSの最大の特徴です。スタートから近い順に全方位へ探索を広げるため、最初に見つかったゴールへの経路が最短経路となります。

2. 幅優先探索はメモリ消費が少ない。

誤り：同じ階層のノードをすべて記憶しておく必要があるため、深さ優先探索（DFS）と比較してメモリ消費が非常に大きくなります。

3. 幅優先探索は深さ優先探索よりも常に高速である。

誤り：ゴールが深い位置にある場合や、探索空間が広大でメモリが不足する場合は、深さ優先探索の方が早く解に到達できることがあります。

4. 幅優先探索はランダム探索の一種である。

誤り：BFSは規則的かつ網羅的に探索を行う決定論的なアルゴリズムであり、ランダム性はありません。

← 前の問題次の問題 →

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