バックトラッキングと分枝限定法

バックトラッキングと分枝限定法は、候補解の空間を木として探索する系統的な探索パラダイムであり、有効な解や最適な解に繋がらない部分木を剪定することで、指数関数的な探索を実用的に実行可能にします。

Definition

バックトラッキングは、部分的な候補解の木に対する深さ優先探索であり、部分的な候補が有効な解に完成できないと判明した瞬間にその枝を剪定します。分枝限定法は、これに目的関数の数値的な境界を追加し、最良の可能性のある値が現在の最良解を上回ることができない枝を破棄します。

Scope

このトピックでは、探索木を中心に構成される網羅的探索手法について扱います。具体的には、制約に違反した時点で部分的な候補を破棄するバックトラッキングと、最適化において達成可能な最良の目的関数の上限を用いて部分木を剪定する分枝限定法です。N-クイーン問題、グラフ彩色、数独などの制約充足の例や、巡回セールスマン問題、整数計画法などの組み合わせ最適化の例を含み、最悪ケースで指数関数的なコストがかかるにもかかわらず、これらの手法がNP困難問題に対して依然として価値がある理由について議論します。

Core questions

• 問題の解空間は、部分的な割り当ての探索木としてどのようにモデル化されますか？
• バックトラッキングが実行不可能な枝を早期に剪定するために、どのような制約チェックが用いられますか？
• 最適化において枝を剪定するために、下限と上限はどのように計算されますか？
• 分岐と限定の順序は、実用的なパフォーマンスにどのように影響しますか？
• 最悪ケースが指数関数的であるにもかかわらず、これらの手法がNP困難問題に用いられるのはなぜですか？

Key concepts

• 探索木
• 深さ優先探索
• 制約伝播
• 剪定
• 限定関数
• 現行解
• N-クイーン問題
• 整数計画緩和

Key theories

探索木の剪定

両パラダイムは、候補解を深さ優先で探索される木として構成します。正当性は網羅性から、効率性は有効な解や改善された解を含まないことが証明された部分木を剪定することから生まれます。

分枝限定法における限定関数

分枝限定法は、これまでに発見された最良の解と、各部分木で達成可能な最良の値に対する限定（例：LP緩和）を維持します。部分木の限定が現行解を改善できない場合、その部分木は破棄されます。

Clinical relevance

分枝限定法は、スケジューリング、ルーティング、計画などに使用される整数計画法や混合整数計画法のソルバーを含む、オペレーションズリサーチにおける厳密な組み合わせ最適化の基盤です。バックトラッキングは、制約ソルバー、SAT形式の探索、パズルソルバー、パーサーの基礎となっており、剪定を伴う系統的な探索が厳密な解を得るための実用的な方法となっています。

History

バックトラッキングは、1950年代から1960年代にかけて、特にゴロム（Golomb）とバウマート（Baumert）によって記述され、一般的な手法として体系化されました。分枝限定法は、1960年にアイサ・ランド（Ailsa Land）とアリソン・ドイグ（Alison Doig）によって整数線形計画法のために導入され、それ以来、組み合わせ最適化の中心となり、現代の混合整数計画法ソルバーを支えています。

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

バックトラッキングと分枝限定法の違いは何ですか？

バックトラッキングは通常、実現可能性問題や制約充足問題に用いられ、制約に違反する枝を剪定します。分枝限定法は最適化を目的とし、さらに数値的な境界を用いて剪定を行い、最良の目的関数値が既に発見された最良解を上回ることができない部分木を破棄します。

これらの手法が最悪ケースで指数関数的である場合、なぜ使用されるのですか？

NP困難問題に対しては、多項式時間の厳密なアルゴリズムは知られていませんが、効果的な剪定は実際のインスタンスにおいて探索木の大部分を排除することが多く、分枝限定法やバックトラッキングのソルバーは、最悪ケースの境界が示唆するよりもはるかに速く、証明可能な最適解を定期的に見つけ出します。