ビームサーチ

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /beam-search#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /beam-search#noredirect を利用してください。
name
ビームサーチ
short description
ビームサーチはグラフ探索アルゴリズムのひとつである。与えられたグラフ (たいてい DAG) を初期状態となる頂点群から幅優先探索と同様に探索していくが、定数 $K$ と頂点に対する評価関数 $\varphi : V \to \mathbb{R}$ をあらかじめ固定しておき、各深さごとにその評価関数による評価値が高い順に $K$ 個のみを保持してそれ以外の頂点は無視する。$K = 1$ のときは貪欲法と一致する。焼きなまし法と並んで、ヒューリスティックコンテストで頻繁に利用されるアルゴリズムである。

話題