幅優先探索

幅優先探索とは、探索木を浅い階層から順に、同じ深さの枝をすべて調べてから次の深さへ進む探索方法です。根に近いところを横にくまなく見ていくイメージです。

たとえば迷路で「スタートから1歩で行ける場所」を全部調べ、次に「2歩で行ける場所」を全部調べる、という進め方です。最短経路を確実に見つけられる長所がありますが、調べる範囲が広がると必要なメモリが急増する短所があります。

ゴールまでの手数を最小にしたい問題で特に有効な探索方法です。