分枝限定法
ぶんしげんていほう
名詞 上級 ★★★★★意味
分枝限定法は、組合せ最適化問題や整数計画問題を解くための探索アルゴリズムで、解空間を木構造として表現し、部分問題（ノード）を順次分割（分枝）しつつ、上界・下界による評価で有望でない枝を除外（限定）する手法です。計算量を削減しながら最適解を保証できる点が重要で、特にNP困難問題の実用的解法として広く利用されています。
用例
0-1ナップサック問題のようなNP困難な問題を解く際、分枝限定法を用いることで効率的に最適解を求めることができます。
NP困難な組合せ最適化問題に対して、全探索よりも計算量を削減しながら最適解を保証できるアルゴリズムとして紹介されています。
類義語
branch and bound、分枝限定アルゴリズム、分枝限定手法
対義語
全探索、brute force、列挙法
関連語
整数計画、組合せ最適化、探索木