ビームサーチ
完全性を実現する派生としては、深さ優先探索を組み合わせたビームスタックサーチや深さ優先ビームサーチや、不一致制限探索(limited discrepancy search)と組み合わせたの不一致バックトラック付きビームサーチ(BULB)がある 。これらのアルゴリズムはAnytimeなアルゴリズム(英語版)、つまり、短時間である程度良い解を見つけ、その後に段々と時間を使ってより良い解を見つけていくことで、途中で中断してもその探索時間に応じた良い解を見つけられるアルゴリズムである。
こういった完全性を実現できる・Anytimeな派生としては、狭いビーム幅で探索を行った後にビーム幅を段々と広げながら再探索を繰り返していく反復広化や、探索木のレベルごとの優先度付きキューなどを保持しておくことで狭いビーム幅での探索結果を残したまま幅を広げていくchokudaiサーチなどもある。
局所探索法としては、ランダムに生成された β {\displaystyle \beta } 個の状態を選んでから、探索木の各レベルで新しい状態リストを β {\displaystyle \beta } 個まで枝刈りしながら、解が得られるまで現在の状態リストからの近傍の探索を繰り返していく手法をローカルビームサーチと呼ぶ。
ローカルビームサーチは局所解で終わることが多いため、よく使われる解決策として次の β {\displaystyle \beta } 個ノードを状態のヒューリスティック評価を使って、ランダム性を加えて選択することがある。この種の探索は、確率的ビームサーチと呼ばれる。
他の派生としては、フレキシブルビームサーチとリカバリービームサーチがある。