ビームサーチ
ビームサーチでは、幅優先探索を使用して木構造を探索する。木の各レベルで、リストに保持してある現在のレベルのノードからたどれる次のレベルのノードを列挙して評価値順でソートする。この時、次のレベルのノードのリストには上位からあらかじめ決められた数 β {\displaystyle \beta } 個(このサイズをビーム幅という)のノードしか保持しない。次のレベルでは、その絞り込んだ後ノードのリストからたどれるノードを処理する。
ビーム幅が大きいほど枝刈りされるノードは少なくなり、ビーム幅が無限大の場合、枝刈りされる状態は無く幅優先探索と同じになり、逆にビーム幅が 1 の場合は、貪欲法と同じになる。ビーム幅によって、探索の実行に必要なメモリが制限できる。目標ノードが枝刈りされる可能性があるため、ビームサーチは完全・最適ではない(解・最適解を見つけられずに終了する可能性がある)。