分枝限定法
再帰は候補集合 S {\displaystyle S} が1つの元になった時点で停止するか、 S {\displaystyle S} の上限が下限と一致した場合に停止する。どちらにしても、停止したときの S {\displaystyle S} のどの元も関数を最小値にする。
分枝限定法は、限定法の種類によって分類したり、探索木のノードの生成/検査方法で分類したりする。
分枝限定法の設計戦略は、状態空間木を問題を解くのに使うという点でバックトラッキングとよく似ている。これらの違いは、分枝限定法が木の走査順序を限定していないという点と、分枝限定法が最適化問題でしか使われないという点である。
動的計画法や貪欲法は部分問題の最適性が必要であるが、成立しない部分問題に対して、適切に場合分けして分枝することにより、分枝限定法でうまく行くこともある。
分枝が場合分けをするので並列実装や分散実装に適している。