互換性アルゴリズム

コンピュータサイエンスにおいて、互換性アルゴリズムは、制約充足問題(CSP)をより効率的に解決するために使用される手法です。CSP は、変数によって表されるオブジェクトがそれらの変数の値に制約を受ける数学の問題です。CSP での目的は、制約と一致する値を変数に割り当てることです。CSP 内の 2 つの変数AおよびB が、問題の性質またはその解決策を変更することなく相互に交換できる (つまり、AをBに置き換え、BをAに置き換える) 場合、 AとBは交換可能な変数です。交換可能な変数は CSP の対称性を表し、この対称性を利用することで、 CSP 問題の解決策の探索空間を縮小できます。たとえば、A =1 およびB =2 の解決策を試した場合、交換対称性により、B =1 およびA =2 の解決策を調査す​​る必要はありません。

制約充足問題における互換性の概念と互換性アルゴリズムは、1991年にユージン・フロイダーによって初めて導入されました。^{[1] [2]互換性アルゴリズムは、}バックトラッキング検索アルゴリズムの検索空間を削減し、 NP完全CSP問題の効率を向上させます。 ^[3]

定義

完全に交換可能

変数vの値aは値bと完全に互換性があるため、v = aとなる解はaをbに置き換えても解のままであり、その逆も同様である。^[2]

近隣の互換性

変数vの値aが値bと近傍交換可能であるのは、vのすべての制約に対して、v = aと互換性のある値がv = bと互換性のある値とまったく同じ場合に限られます。^[2]

完全に代替可能

変数vの値aは、値bと完全に置き換え可能であるためには、v = aとなる解が、aをbに置き換えても解として残る必要がある（ただし、その逆は必ずしも当てはまらない）。^[2]

動的に交換可能

変数vの値aは、変数割り当ての集合Aに関して、Aによって誘導される部分問題において完全に交換可能である場合にのみ、変数bと動的に交換可能である。^[2]

擬似コード

近傍互換性アルゴリズム

CSP内の近傍の交換可能な値を検索します。各変数について繰り返します。

次の方法で判別ツリーを構築します。

各値vについて繰り返します。

隣接する変数Wごとに繰り返します。

v と一致する各値 w について繰り返します。

存在する場合は移動し、存在しない場合はw|Wに対応する識別ツリーのノードを構築する^[2]

K-互換性アルゴリズム

このアルゴリズムは、制約充足問題の解を明示的に求めるために使用できます。また、このアルゴリズムをkステップ実行することで、後続のバックトラック探索を簡素化する前処理としても使用できます。

CSP内のk個の交換可能な値を検索します。各変数について繰り返します。

次の方法で判別ツリーを構築します。

各値vについて繰り返します。

変数の 各( k −1)組について繰り返す

それぞれの( k −1)組の値wに対してこれを繰り返します。wとvはWによって誘導される部分問題の解を構成します。

存在する場合は移動し、存在しない場合はw|Wに対応する識別ツリーのノードを構築する^[2]

複雑性分析

近傍交換可能アルゴリズムの場合、各ループに最悪ケースの境界を割り当てると、n個の変数（各変数に最大d個の値を持つ）に対して、境界は次のようになります 。 ${\displaystyle O(nd(nl)*d)=O(n^{2}d^{2})}$

同様に、最悪のケース の場合のk互換性アルゴリズムの複雑性分析では、組の変数と組の値の場合、境界は次のようになります。 ${\displaystyle O(n^{k-1})}$ ${\displaystyle (k-1)}$ ${\displaystyle d^{k-1}}$ ${\displaystyle (k-1)}$ ${\displaystyle O(ndn^{kl}d^{k-1})=O(n^{k}d^{k})}$

例

互換性アルゴリズムの例

図は、頂点を色で表した単純なグラフの色分け例を示しています。辺で結ばれた2つの頂点は同じ色になりません。各頂点で使用可能な色が表示されています。黄色、緑、茶、赤、青、ピンクは頂点Yを表し、定義上、これらの色は完全に互換性があります。例えば、解 orange|X (Xはオレンジ), green|Y の緑を栗色に置き換えると、別の解が得られます。

アプリケーション

コンピュータサイエンスにおいて、互換性アルゴリズムは人工知能、グラフ彩色問題、抽象化フレームワーク、ソリューション適応などの分野で広く利用されている。 ^{[2] [4] [5] [6] [7] [8] [9]}

参考文献

1. Belaid Benhamou および Mohamed Reda Saidi 「Not-Equals binary制約ネットワークにおける優位性による推論」、情報およびシステム科学研究所 (LSIS)、数学および情報センター、フランス。
2. フロイダー, EC: 制約充足問題における互換性のある値の排除. AAAI-91論文集, アナハイム, CA (1991) 227–233
3. Assef Chmeiss と Lakhdar Sais「CSP における近隣代替可能性について」、Artrois 大学、フランス その間、あなたは ce です。
4. Haselbock, A.: 制約充足問題における互換性の活用. 第13回IJCAI論文集 (1993) 282–287
5. Weigel, R., Faltings, B.: 制約充足問題のコンパイル. 人工知能 115 (1999) 257–289
6. Choueiry, BY: 資源配分のための抽象化手法。EPFL博士論文番号1292 (1994)
7. Weigel, R., Faltings, B.: 構成問題におけるケース適応のための互換性. AAAI98 Spring Symposium on Multimodal Reasoning, Stanford, CA, TR SS-98-04. (1998)
8. Neagu, N., Faltings, B.: ケース適応における互換性の活用. 第4回ICCBR01論文集 (2001)
9. SAT エンコーディングによる完全な動的代替可能性、Steven Prestwich、コーク制約計算センター、コンピュータサイエンス学部、ユニバーシティ カレッジ、コーク、アイルランド