ビームサーチ

ビームサーチは、探索空間全体を格納するのにはメモリが足りない大規模な課題に対してよく使用される^[5]。たとえば、多くの機械翻訳システムで使用されていた ^[6] （現在、最先端技術では、ニューラル機械翻訳ベースの方法が主に使用されている。）。最適な翻訳を選択するために、各部分についてさまざまな方法で単語を翻訳していく。文の構造に良くあった翻訳が保持され、残りは破棄する。次に、翻訳アルゴリズムは与えられた基準に従って翻訳を評価し、目標を最もよく維持する翻訳を選択する。ビームサーチが初めて使われたのは、ハーピー音声認識システム、CMU1976だった^[7]。

完全性を実現する派生としては、深さ優先探索を組み合わせたビームスタックサーチや^[8]、深さ優先ビームサーチや^[5]、不一致制限探索（limited discrepancy search）と組み合わせたの不一致バックトラック付きビームサーチ（BULB）がある^[9]。これらのアルゴリズムはAnytimeなアルゴリズム（英語版）、つまり、短時間である程度良い解を見つけ、その後に段々と時間を使ってより良い解を見つけていくことで、途中で中断してもその探索時間に応じた良い解を見つけられるアルゴリズムである。

こういった完全性を実現できる・Anytimeな派生としては、狭いビーム幅で探索を行った後にビーム幅を段々と広げながら再探索を繰り返していく反復広化や^[10]、探索木のレベルごとの優先度付きキューなどを保持しておくことで狭いビーム幅での探索結果を残したまま幅を広げていくchokudaiサーチなどもある^[11]。

局所探索法としては、ランダムに生成された ${\displaystyle \beta }$ 個の状態を選んでから、探索木の各レベルで新しい状態リストを ${\displaystyle \beta }$ 個まで枝刈りしながら、解が得られるまで現在の状態リストからの近傍の探索を繰り返していく手法をローカルビームサーチと呼ぶ^[12][13]。

ローカルビームサーチは局所解で終わることが多いため、よく使われる解決策として次の ${\displaystyle \beta }$ 個ノードを状態のヒューリスティック評価を使って、ランダム性を加えて選択することがある。この種の探索は、確率的ビームサーチと呼ばれる^[14]。

他の派生としては、フレキシブルビームサーチとリカバリービームサーチがある^[13]。