ビームサーチ（びーむさーち）
最終更新：2026/4/25
ビームサーチは、幅優先探索において保持する候補数を制限することで、計算コストを抑えて最適解を探索するアルゴリズムである。
別名・同義語 ヒューリスティック探索探索アルゴリズム
ポイント
特に機械翻訳や音声認識などの系列データ処理において、最適な解候補を効率的に探索するために用いられる。探索空間を絞り込むことで計算コストを削減する。
ビームサーチとは
ビームサーチは、探索空間が非常に大きい場合に、最適な解を効率的に見つけ出すためのヒューリスティック探索アルゴリズムです。幅優先探索のように全ての候補を探索するのではなく、各ステップで最も有望な上位k個の候補（ビーム）のみを保持し、それらを拡張していくことで探索空間を絞り込みます。kの値はビーム幅と呼ばれ、この値が大きいほど探索は広範囲になりますが、計算コストも増加します。
ビームサーチの仕組み
- 初期化: 探索を開始する初期状態からスタートします。
- 展開: 現在のビームに含まれる各状態を展開し、可能な次の状態を生成します。
- 評価: 生成された各状態を評価関数を用いて評価します。評価関数は、問題に応じて適切に定義する必要があります。
- 選択: 評価値の高い上位k個の状態を選択し、次のビームとして保持します。残りの状態は破棄されます。
- 繰り返し: ステップ2〜4を、終了条件を満たすまで繰り返します。
ビームサーチの応用例
- 機械翻訳: 入力文に対応する最適な翻訳文を探索します。
- 音声認識: 音声データに対応する最適な単語列を探索します。
- 自然言語処理: テキスト生成や質問応答などのタスクに利用されます。
- 経路探索: グラフ構造における最適な経路を探索します。
ビームサーチの利点と欠点
利点:
- 幅優先探索よりも計算コストが低い。
- 深さ優先探索よりも局所解に陥りにくい。
- 比較的簡単に実装できる。
欠点:
- 最適な解を見つけられる保証はない。
- ビーム幅kの調整が難しい。
- 評価関数の設計が重要。