分枝限定法とは？
分枝限定法とは、解の候補を枝分かれさせながら列挙する際に、その枝から得られる最良の値を見積もり、すでに見つかっている解より良くなり得ないと分かった枝を打ち切る手法。全列挙と同じ最適解を保証しつつ、調べる範囲を大幅に減らす。
ぶんしげんていほう
分枝限定法の意味
解の候補を枝分かれさせながら列挙する際に、その枝から得られる最良の値を見積もり、すでに見つかっている解より良くなり得ないと分かった枝を打ち切る手法。全列挙と同じ最適解を保証しつつ、調べる範囲を大幅に減らす。
分枝限定法の具体例
荷物の詰め合わせで価値を最大にする問題で、まず適当な組合せから価値1000の解を得ておく。ある枝が残り全部を詰めても最大900にしかならないと見積もれた時点で、その先を一切調べずに切り捨てる。
分枝限定法は試験でどう引っ掛けられる？
打ち切っても最適解は失われない点が要点で、近似解を返す手法ではない。見積りが甘いと枝がほとんど切れず全探索と変わらなくなるため、良い見積りと良い初期解を先に得ることが効率を左右する。
分枝限定法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。