分枝限定法
関数 f ( x ) {\displaystyle f(x)} の最小値を求める最適化問題を考える。 x ∈ S {\displaystyle x\in S} とする。
分枝限定法には2つの手続きが必要である。
分枝限定法は以下のような問題で使われる。
ナップサック問題
非線型計画問題
巡回セールスマン問題 (TSP)
二次割り当て問題 (QAP)
最大充足可能性問題 (MAX-SAT)
最近傍探索 (NNS)
また、各種ヒューリスティクスの基盤でもある。例えば、上限と下限の差がある値以下になったとき分枝を止めたいという場合もある。これは、「実用には十分な」解を求めるのに使われ、必要な計算量を大幅に減らすことができる。特にコスト関数にノイズがある場合や統計的推定に基づくコスト関数にはこのような手法が現実的である。そのようなコスト関数は確率的に誤差を生じる可能性がある。例えば生物学で有機体間の進化的関係を評価する場合、何らかのヒューリスティックを用いないとデータが大きすぎる。
同じ理由で、ゲーム木の探索にも分枝限定法がよく使われ、例えばアルファ・ベータ法は分枝限定法の一種である。