制約充足問題

制約充足問題は、変数群に対する値の割り当てを求め、それらの間のすべての制約を同時に満たすことで、多くの組み合わせ問題に統一的な表現を提供します。

Definition

制約充足問題は、変数群、各変数に対する可能な値のドメイン、および値の許容される組み合わせを指定する制約群から構成されます。解とは、いかなる制約も破らない完全な割り当てのことです。

Scope

このトピックでは、制約充足問題（CSP）の形式（変数、ドメイン、制約）と、それを解決するアルゴリズムについて扱います。具体的には、変数および値の順序付けヒューリスティクスを用いたバックトラッキング探索、制約伝播と整合性技術（ノード、アーク、パス整合性、例えばAC-3アルゴリズム）、および問題構造の活用（木構造CSP、カットセット条件付け）が含まれます。これは、CSPの局所探索や、より広範な制約プログラミングの実践と関連しています。同様の問題に対する連続最適化および学習ベースの定式化は、ここでは範囲外とします。

Core questions

• 多様な問題（スケジューリング、地図彩色、パズル）は、どのように変数、ドメイン、制約として統一的に表現されるのでしょうか？
• 制約伝播は、探索前および探索中にどのように値を剪定し、バックトラッキングを減らすのでしょうか？
• どの変数および値の順序付けヒューリスティクスが、バックトラッキング探索を効率的にするのでしょうか？
• 制約グラフの構造（例えば、木構造であること）は、効率的な解決のためにどのように活用できるのでしょうか？

Key concepts

• 変数、ドメイン、制約
• 制約グラフ
• バックトラッキング探索
• 前方チェック
• アーク整合性とAC-3
• 最小残余値ヒューリスティクス
• 制約伝播
• 木構造CSPとカットセット条件付け

Key theories

アーク整合性と制約伝播

CSPは、各変数のすべての値が、隣接する各変数に整合性のあるパートナーを持つ場合にアーク整合性があると言えます。AC-3などのアルゴリズムは、サポートされていない値を繰り返し削除することでこれを強制し、探索前または探索中にドメインを大幅に縮小することがよくあります。

ヒューリスティクスを用いたバックトラッキング探索

CSPは、深さ優先の割り当てとバックトラッキングによって解決されます。これは、最も制約の厳しい変数（最小残余値）の選択、最も制約の少ない値の選択、およびデッドエンドを早期に検出するための前方チェックや伝播のインターリーブなどのヒューリスティクスによって実用化されます。

構造の活用

制約グラフが木構造である場合、CSPは変数の数に比例する時間で解決でき、木に近い構造はカットセット条件付けや木分解を介してこのケースに還元できます。

Clinical relevance

CSP技術は、スケジューリングや時間割作成、リソース割り当て、製品構成、ハードウェアおよびソフトウェアの検証、数独などのパズルソルバーの基盤となっています。これらのアイデアに基づいて構築された制約プログラミング言語とソルバーは、産業計画やオペレーションズリサーチで広く使用されています。

History

制約ネットワークは、1970年代にシーンラベリングとリレーショナル整合性に関する研究から生まれ、1977年のMackworthの論文でノード、アーク、パス整合性が形式化されました。1980年代から90年代にかけて、この分野は制約プログラミングとして成熟し、2006年の『Handbook of Constraint Programming』で体系化され、標準的なAIトピックとして確立されています。

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

制約充足問題は、一般的な探索問題とどう違うのですか？

一般的な探索問題は状態をブラックボックスとして扱いますが、CSPは状態の内部構造を変数への割り当てとして、制約に従って公開します。この構造により、CSPソルバーは一般的な探索では利用できない制約伝播や順序付けヒューリスティクスを使用できます。

アーク整合性は何をするのですか？

アーク整合性は、隣接する変数との間の制約を考慮して、隣接する変数に互換性のある値がない変数のドメインから値を削除します。探索前および探索中にこれを強制することで、探索空間が剪定され、バックトラッキングなしで問題が解決されることもあります。