分枝限定法

分枝限定法（Branch and Bound）とは

分枝限定法（Branch and Bound, BB）は、複雑な最適化問題、特に離散最適化や組合せ最適化問題の最適解を効率的に見つけ出すための汎用的なアルゴリズムです。この手法は、考えられる全ての解候補を系統的に探索する過程で、最適化された値の上限と下限を計算し、その情報に基づいて最適でない解候補を「ひとまとめに」排除することで探索空間を大幅に削減します。1960年にA.H. LandとA.G. Doigによって線形計画法の手法として初めて提案されました。

基本概念

分枝限定法は、最適化問題を解く上で、以下の二つの主要な操作を繰り返します。

1. 分枝操作（Branching Operation）
- 与えられた問題の解空間を、より小さな部分問題へと分割する操作です。この分割は、元の問題を複数の部分集合に分割することで行われ、それぞれの部分集合が探索木のノードに対応します。分割された部分集合は、互いに重複していても構いません。

2. 限定操作（Bounding Operation）
- 各部分問題（部分集合）に対して、その中で関数が取りうる最小値（または最大値）の上限と下限を計算する操作です。この操作により、その部分問題に最適解が含まれる可能性を評価します。

分枝限定法の核心は、ある部分問題の下限値が、別の部分問題の上限値よりも大きい場合、その部分問題を探索対象から除外できる点にあります。この操作を「刈り込み（Pruning）」と呼び、探索効率を大幅に向上させます。アルゴリズムでは、これまでに発見された最適解の上限値を保持しておき、下限値がこの上限値を超える部分問題を刈り込むことで、探索空間を絞り込みます。

探索は、部分問題の解空間が単一の解に絞られるか、上限値と下限値が一致した時点で終了します。

分枝限定法の種類と設計戦略

分枝限定法は、限定操作の方法や探索木のノードの生成・検査方法によって様々な種類に分類されます。この手法は、状態空間木を用いて問題を解く点でバックトラッキングと似ていますが、探索順序に制約がない点と、最適化問題にのみ適用される点が異なります。

また、動的計画法や貪欲法が適用できない場合でも、部分問題を適切に分割して分枝することで、分枝限定法が有効となるケースがあります。

分枝操作が並列処理に適しているため、並列実装や分散実装も比較的容易です。

効率的な分枝戦略

分枝限定法の効率性は、部分問題の分割方法（分枝操作）と上限・下限の推定方法（限定操作）に大きく依存します。オーバーラップしない部分集合への分割が最も効率的ですが、現実的な問題では難しい場合も多いため、問題に応じた適切な戦略が必要です。

理想的には、探索木の全てのノードが刈り込まれるか解かれることで探索が終了するのが望ましいです。しかし、実際には、時間制限や誤差基準に基づいてアルゴリズムを停止させることもあります。

分枝操作と限定操作のアルゴリズムは問題ごとに設計する必要があり、あらゆる問題でうまく機能する万能なアルゴリズムは存在しません。

応用分野

分枝限定法は、以下のような様々な分野の問題に適用されています。

ナップサック問題
非線形計画問題
巡回セールスマン問題 (TSP)
二次割り当て問題 (QAP)
最大充足可能性問題 (MAX-SAT)
最近傍探索 (NNS)

また、分枝限定法は、各種ヒューリスティクスの基盤としても利用されています。例えば、上限と下限の差が一定値以下になった時点で探索を打ち切ることで、「実用には十分な」解を効率的に求めることが可能です。

特に、コスト関数にノイズが含まれる場合や、統計的推定に基づいてコスト関数が算出される場合など、計算量が膨大になるケースにおいて、分枝限定法は有効な手法となります。生物学における系統樹の評価など、膨大なデータを取り扱う必要がある分野でも、ヒューリスティックと組み合わせて利用されています。

さらに、ゲーム木の探索にも分枝限定法は広く使われており、アルファ・ベータ法はその一例です。

関連項目

A
* 設計パラダイムによるアルゴリズムの分類

もう一度検索