分枝限定法

分枝限定法（ぶんしげんていほう、）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（）と限定操作（）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。
1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。
概要.
関数 formula_1 の最小値を求める最適化問題を考える。 formula_2 とする。
分枝限定法には2つの手続きが必要である。
分枝限定法は、限定法の種類によって分類したり、探索木のノードの生成/検査方法で分類したりする。
分枝限定法の設計戦略は、状態空間木を問題を解くのに使うという点でバックトラッキングとよく似ている。これらの違いは、分枝限定法が木の走査順序を限定していないという点と、分枝限定法が最適化問題でしか使われないという点である。
動的計画法や貪欲法は部分問題の最適性が必要であるが、成立しない部分問題に対して、適切に場合分けして分枝することにより、分枝限定法でうまく行くこともある。
分枝が場合分けをするので並列実装や分散実装に適している。
効率的な分枝.
この手法の効率は、ノード分割手続きと上限および下限を推定する手続きに強く依存する。他の全ての条件が同じなら、オーバーラップしない部分集合に分割するのが最もよい。
理想的には、この手続きは探索木の全てのノードが刈りこまれるか解かれたときに停止する。その時点で刈りこまれていない部分は、上限と下限が関数の大域的最小値と等しくなっている。実際には、ある所定の時間が経過すると手続きを停止することが多く、その時点では刈りこまれていない部分の最大下限値と最小上限値が大域的最小値の区間を定義している。これとは別に時間制限ではなく、アルゴリズムを何らかの誤差基準で停止させる方法もある。例えば （最大 - 最小）/（最大 ＋ 最小）がある特定値以下になった時点で停止させる。
この手法の効率は、分枝法と限定法に使われたアルゴリズムの有効性に強く依存する。間違った選択をすると分枝が繰り返され、全く刈り込みが行われず、あまりにも細かく分割されることになる。それは定義域を総当りするのと何ら変わりないことになり、多くの場合現実的でない。あらゆる問題でうまくいく限定法アルゴリズムは存在しないし、今後見つかるとも思えない。従って、分枝法と限定法のアルゴリズムは問題毎に設計する必要がある。
応用.
分枝限定法は以下のような問題で使われる。
また、各種ヒューリスティクスの基盤でもある。例えば、上限と下限の差がある値以下になったとき分枝を止めたいという場合もある。これは、「実用には十分な」解を求めるのに使われ、必要な計算量を大幅に減らすことができる。特にコスト関数にノイズがある場合や統計的推定に基づくコスト関数にはこのような手法が現実的である。そのようなコスト関数は確率的に誤差を生じる可能性がある。例えば生物学で有機体間の進化的関係を評価する場合、何らかのヒューリスティックを用いないとデータが大きすぎる。
同じ理由で、ゲーム木の探索にも分枝限定法がよく使われ、例えばアルファ・ベータ法は分枝限定法の一種である。