分枝限定法は、膨大な選択肢から最適な解を探索する組合せ最適化問題を効率的に解くアルゴリズムです。探索範囲を細分化する「分枝」と、解の上限・下限を見積もる「限定」を組み合わせ、見込みのない探索ルートを打ち切る「剪定」を行うことで、計算時間を大幅に削減しながら理論上厳密な最適解を確実に得られるのが特徴です。
分枝限定法とは
分枝限定法とは、膨大な選択肢の中から最適な解を見つけ出す組合せ最適化問題を効率的に解くための探索アルゴリズムです。
詳しく解説
分枝限定法は、すべての候補を調べる全探索をベースにしながら、無駄な探索を省く「剪定」を行うことで計算時間を大幅に削減します。このアルゴリズムは「分枝」と「限定」という2つのステップで構成されます。まず、問題をより小さな部分問題に分割していきます（分枝）。次に、各部分問題に対して得られる解の予測値（境界値）を計算します（限定）。もし、ある部分問題から得られる最良の予測値が、すでに発見されている暫定の最適解よりも劣ることが判明した場合、その先を探索しても意味がないため探索を打ち切ります（剪定）。これにより、解の品質を保証しつつ、探索空間を劇的に縮小できるのが最大の特徴です。
具体例・使われ方
分枝限定法は、配送ルートの最適化問題（巡回セールスマン問題）や、ナップサック問題などの代表的な組合せ最適化問題の解決に利用されます。また、機械学習の分野においては、スパース表現を求めるための変数選択（特徴量選択）や、数理最適化パッケージを用いた整数計画問題の解決に広く応用されています。さらに、AIのゲーム探索（チェスや将棋など）における探索木の評価や、意思決定の効率化にも役立っています。
似た用語との違い
すべての可能性をしらみつぶしに調べる「全探索」が膨大な計算時間を要するのに対し、分枝限定法は無駄な探索を省くことで現実的な時間での解決を図ります。また、その場で最善に見える選択を繰り返す「発見的アルゴリズム（メタヒューリスティクスや貪欲法など）」は高速ですが必ずしも最適解を得られるとは限りません。一方、分枝限定法は、計算を途中で省略しつつも、理論的に「厳密な最適解」を保証できる点で大きく異なります。
注意点
分枝限定法は優れたアルゴリズムですが、最悪の場合には剪定がうまく機能せず、結局すべての選択肢を探索することになり計算量が爆発する可能性があります（NP困難な問題など）。効率的に探索を行うためには、解の境界値をいかに正確かつ高速に見積もるかという「バウンディング関数」の設計が極めて重要であり、問題の性質に応じたチューニングが求められます。