分枝限定法とは？ぶんしげんていほう
分枝限定法とは、最適化問題を部分問題に分割（分枝）し、各部分問題の解が取り得る上界・下界を見積もって、既知の暫定解より良くなり得ない枝を探索前に切り捨てる（限定）手法。厳密解を保証しながら探索空間を大幅に削減でき、整数計画やスケジューリング問題の求解に使われる。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
ナップサック問題で、残り容量に対して価値密度の高い品物を分割可能と仮定した値を上界とする。この上界が現在の暫定最良解を下回る枝は、その先を一切調べずに打ち切れる。良い暫定解を早く得るほど枝刈りが効くため、初期解を貪欲法で作ることが多い。
試験での引っ掛け
枝刈りで探索が減っても最悪計算量は指数のままで、多項式時間になるわけではない。またヒューリスティクスと混同しやすいが、分枝限定法は最適解を必ず得る厳密解法であり、近似解しか保証しない手法とは性質が違う。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。