ビームサーチ

コンピュータサイエンス分野において、ビームサーチとは、枝刈りをしながら木・グラフを探索するヒューリスティックな探索アルゴリズムである。ビームサーチは、枝刈りを行うことで幅優先探索を省コスト化したもので、幅優先探索は全探索を行うが、ビームサーチでは事前に決めておいた数の候補から、最良のものを選ぶ。これは、貪欲法から候補数を広げた形ともいえる。

「ビームサーチ」という名前は、1977年にカーネギーメロン大学のラジ・レディによって付けられた。

詳細

ビームサーチでは、幅優先探索を使用して木構造を探索する。木の各レベルで、リストに保持してある現在のレベルのノードからたどれる次のレベルのノードを列挙して評価値順でソートする。この時、次のレベルのノードのリストには上位からあらかじめ決められた数 $\beta$ 個（このサイズをビーム幅という）のノードしか保持しない。次のレベルでは、その絞り込んだ後ノードのリストからたどれるノードを処理する。

ビーム幅が大きいほど枝刈りされるノードは少なくなり、ビーム幅が無限大の場合、枝刈りされる状態は無く幅優先探索と同じになり、逆にビーム幅が 1 の場合は、貪欲法と同じになる。ビーム幅によって、探索の実行に必要なメモリが制限できる。目標ノードが枝刈りされる可能性があるため、ビームサーチは完全・最適ではない（解・最適解を見つけられずに終了する可能性がある）。

用途

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

派生

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

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

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

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

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