分岐限定法とは？
分岐限定法とは、最適化問題で解空間を分岐によって部分問題に分け、各部分問題の到達可能な最良値の限界（バウンド）を見積もり、既に得ている暫定解を超えられないと分かった枝を丸ごと切り捨てて探索量を減らす手法。整数計画やナップサック問題の厳密解法として使われる。
ぶんきげんていほう
分岐限定法の意味
最適化問題で解空間を分岐によって部分問題に分け、各部分問題の到達可能な最良値の限界（バウンド）を見積もり、既に得ている暫定解を超えられないと分かった枝を丸ごと切り捨てて探索量を減らす手法。整数計画やナップサック問題の厳密解法として使われる。
分岐限定法の具体例
ナップサック問題で、残り容量に対して品物を分割できると仮定した上限値を計算し、その上限が暫定解の価値を下回る枝は展開しない。線形計画法で緩和解を求め、それを限界値に使う実装が一般的。
分岐限定法は試験でどう引っ掛けられる？
バックトラッキングは「実行可能かどうか」で枝を切るが、分岐限定法は「最適解になり得るか」で切る点が違う。また枝刈りは探索を速くするだけで、得られる解は厳密最適であり近似解ではない。
分岐限定法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。