| このリンクをクリックして、PPC に関する古い記事を見つけてください。 |
プレゼンテーション
制約プログラミング(PPC) は、「制約」と呼ばれる関係を使用したプログラミングで構成されます。問題には特定の数の変数があり、それぞれがドメインと特定の数の制約を持ちます。制約には 1 つ以上の変数が含まれ、これらの変数が同時に取ることができる値を制限します。 PPC 問題の解決策を見つけるには、すべての制約が満たされるように、各変数の許可された割り当てのセットを記述する必要があります。
有限領域での制約プログラミング
制約充足問題の説明
問題には、それぞれが有限の領域を持つ特定の数の変数と、特定の数の制約が含まれます。
制約には 1 つ以上の変数が含まれ、どの組み合わせが許可され、どの組み合わせが禁止されるかを定義します。制約に 2 つの変数が含まれる場合、それはバイナリ制約と呼ばれます。不定数の変数が関係する場合、グローバル制約と呼ばれます。
PPC 問題の解を見つけるには、すべての制約が満たされるように、各変数に値を割り当てます。すべての可能性をリストアップし、それらが制約に違反するかどうかをチェックすることが可能です。ただし、これは計算量が非常に多くなります。最も重要な部分は「フィルタリング」と呼ばれ、制約から不可能な値を推定することで構成されます。変数の候補が 1 つだけの場合、その変数はインスタンス化されます。ただし、フィルタリングによって常にすべての変数をインスタンス化できるわけではありません。その後、任意の選択を行ってから、フィルタリングを再度開始する必要があります。この選択が矛盾につながる場合は、バックトラッキングによって任意の選択をキャンセルします。
検索アルゴリズム: 深さ、幅、ヒューリスティック、LDS
ローカルな一貫性
ローカル整合性は、特定の変数がこの変数にリンクされた制約に違反していないことを検証することで構成されます。次に、他の変数と制約を無視します。これにより、特定の不可能な値をフィルタリングすることが可能になりますが、特定の制約が無視されるため、完全なフィルタリングは不可能になります。
ノードの一貫性
それは 1 つの変数のみを考慮することで構成されます。ただし、制約は通常、少なくとも 2 つの変数に関連します。したがって、この一貫性から得られる情報はほとんどありません。
アークの一貫性
これは Arc Consistency (AC) とも呼ばれ、最もよく使用される方法です。これは、バイナリ制約 (つまり、2 つの変数が関与する) の場合に適用されます。バイナリ制約は、関係する 2 つの変数を接続する円弧によって表すことができるため、円弧という言葉が使用されます。各変数の各値が制約の解に属している場合、制約は円弧の一貫性を満たします。この特性を満たさない値を削除することで、アークの一貫性を確立します。
たとえば、制約 V 1 = V 2を使用して V 1 ∈ [1,2,3] および V 2 ∈ [1,3] とします。次に、解決策 1-1 と 3-3 があります。 V 1の値 2 はソリューションに属さないため、ドメインから削除されます。
ハイパーアークの一貫性
ハイパーアーク一貫性 (HAC) とも呼ばれ、非バイナリ制約のアーク一貫性を一般化したものです。その名前は、関係する変数がハイパーアーク (ハイパーグラフ内のアークの名前) によってリンクできるという事実に由来しています。これは一般化アーク一貫性とも呼ばれます。原則はバイナリ制約の場合と同じです。つまり、各変数の各値が制約の解に属している場合に限り、制約は HAC になります。このプロパティを満たさないすべての値を削除することで、ハイパーアークの一貫性を確立します。
たとえば、Alldiff 制約は、それが定義されている変数が 2 つの異なる値を取ることを意味します。私たちは、この制約に対するハイパーアークの一貫性を効果的に確立する方法を知っています。
k-一貫性
これは、k 個の変数を考慮し、制約に違反していないかどうかをテストするために、考えられる値のすべての k タプルをテストすることで構成されます。 k が大きいほど、フィルタリングはより効果的になります。ただし、テストする組み合わせが多数あるため、これは依然として面倒なままであることがよくあります。 3-consistency は良好な結果をもたらしますが、実装が複雑なため、制約ソルバーに存在することはほとんどありません。
2 一貫性は実際には円弧の一貫性です。問題に n 個の変数が含まれている場合、n 整合性はすべての可能性をテストすることで構成されます。
パス
端子の一貫性
変数の領域が大きすぎる場合 (要素数が数千)、すべての可能性を列挙するのは非常に面倒になります。次に、ドメインの下限と上限のみを処理します。これは、<、>、= などの特定の制約で非常にうまく機能します。
ローカル整合性アルゴリズム
AC1、AC2、AC3、AC4、AC5、AC6、AC7、AC8、AC2001
例
N-レディース
N クイーン問題は、N 個のクイーンを NxN チェス盤上に配置し、そのうちの 1 人が他のクイーンを食べることができないようにするというものです (チェスのルールに従って、クイーンはその行、列、またはいずれかにある駒を「食べる」ことができます) 2 つの対角線)。この問題の詳細については、「 8 クイーン問題」を参照してください。
この問題は、行 i の女王の列位置を表す N 個の変数 (V i ∈ [1..N]、i=1 .. N) で表すことができます。実際、2 つのクイーンを同じライン上に置くことはできず、ラインの数と同じ数のクイーンが存在するため、ラインごとにクイーンは 1 つだけ存在します。
変数 V iに課せられる制約は次のとおりです。
すべての i ≠ j に対して：
- V i ≠ V j (2 つのクイーンを同じ列に配置しないでください)。
- V i – i ≠ V j – j (同じ対角線の北西-南東に 2 つのクイーンを配置しないでください)
- V i + i ≠ V j + j (同じ北東-南西の対角線上に 2 つのクイーンを配置しないでください)
送る+もっと=お金
方程式を次のようにします。
送信 +もっと見る ----- お金
目標は、合計が検証されるように各文字に数字を関連付けることです。したがって、変数は s、e、n、d、m、o、r および y となり、すべて [0,9] の整数になります。制約を課します
数独
Sudoku は、9×9 のグリッドに 1 から 9 までの数字を埋めて、各行、列、サイズ 3×3 のサブボックスに各数字が 1 回だけ現れるようにすることで構成されます。
したがって、[1,9] では変数は当然整数になります。次に、各行、列、サブボックスでよく知られているグローバル制約AllDifferent を使用します。
その他
3Dシーン認識、定性的時間推論
アプリケーション
PPC はスケジュールや割り当ての問題に非常に効果的であるため、主に複雑な物流問題で使用されます。
他の領域の制約
- 条項
- ブール値
- 本物
- 間隔
- セット
- 鎖
制約ソルバー
- 理論研究
- ソルバーのアーキテクチャ
- プロパゲーターの表現言語: インデックス、CHR
- 無料および商用ソルバーへのリンク