分岐限定法とは？
分岐限定法とは、組合せの候補を木のように枝分かれさせて調べる際に、その枝を最後までたどっても現時点の最良解を超えられないと計算できた時点で、枝ごと切り捨てる解法。最適解は保証したまま探索量を減らす。
ぶんきげんていほう
分岐限定法の意味
組合せの候補を木のように枝分かれさせて調べる際に、その枝を最後までたどっても現時点の最良解を超えられないと計算できた時点で、枝ごと切り捨てる解法。最適解は保証したまま探索量を減らす。
分岐限定法の具体例
ナップサック問題で、残りの品物を全部詰め込めたと仮定しても今までの最高価値に届かない枝は、それ以上展開しない。生産計画や配送順序の決定など、組合せ最適化の問題で使われる。
分岐限定法は試験でどう引っ掛けられる？
切り捨てても最適解は失われないので、はじめから最適性をあきらめる近似解法とは区別する。ただし枝を切れない場合は全候補を調べることになり、計算量が必ず減る保証はない。
分岐限定法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。