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