About: ビームサーチ

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