分枝探索法
ぶんしたんさくほう
名詞 上級 ★★★★★意味
分枝探索法は、組合せ最適化や探索問題において、解空間を木構造として表現し、部分解を順次展開しながら最適解を探索する手法です。探索の過程で上界・下界を評価し、有望でない枝を剪定することで計算量を削減します。整数計画やスケジューリング、ゲーム木の評価など、膨大な組合せが存在する問題で広く利用され、計算資源の有効活用と解の品質向上に寄与します。
用例
0-1ナップサック問題のようなNP困難な問題を解く際、全探索では時間がかかるため分枝探索法を用いて有望な解のみを絞り込む。
計算量が膨大になる組合せ最適化問題において、無駄な探索を省くための具体的な適用例を示しています。
類義語
枝刈り法、Branch and Bound、B&B法
対義語
貪欲法、全探索、ヒューリスティック法
関連語
組合せ最適化、整数計画、スケジューリング