AC-3アルゴリズム

制約充足において、AC-3 アルゴリズム( Arc Consistency Algorithm #3の略) は、制約充足問題(または CSP)の解決に使用される一連のアルゴリズムの 1 つです。これは、1977 年にAlan Mackworthによって開発されました。初期の AC アルゴリズムは非効率すぎるとよく考えられ、後期のアルゴリズムの多くは実装が難しいため、AC-3 は最も頻繁に教えられ、非常に単純な制約ソルバーで使用されています。AC-3 アルゴリズムは、機械学習における同様の名前の A3C アルゴリズムと混同しないでください。^[1]

AC-3 は、制約、変数、および変数のドメイン (スコープ) を操作します。変数は、複数の離散値のいずれかを取ることができます。特定の変数の値のセットはそのドメインと呼ばれます。制約は、変数が持つことができる値を制限または制約する関係です。制約には、他の変数の値が含まれる場合があります。

アルゴリズム実行中の CSP の現在の状態は、有向グラフとして表示できます。ここで、ノードは問題の変数、変数間のエッジまたはアークは対称制約によって関連付けられており、ワークリスト内の各アークは、一貫性をチェックする必要がある制約を表します。 AC-3 は、変数のペア ( x、y )間のアークを調べることによって処理を進めます。 xとyの間の制約と一致しない値をxのドメインから削除します。アルゴリズムは、まだチェックされていないアークのコレクションを保持します。変数のドメインから値が削除されると、その削除された変数を指す制約のすべてのアーク (現在の制約のアークを除く) がコレクションに追加されます。変数のドメインは有限であり、各ステップで 1 つのアークまたは少なくとも 1 つの値が削除されるため、このアルゴリズムは必ず終了します。

説明のために、非常に単純な制約問題の例を示します。 変数Xには {0、1、2、3、4、5} の値が考えられます。これらの値のセットはXの定義域、つまり D( X ) です。変数Yの定義域は D( Y ) = {0、1、2、3、4、5、6、7、8、9} です。制約C1 = "X は偶数でなければならない"および制約C2 = " X + Yは4に等しくなければならない" と組み合わせると、AC-3 で解決できる CSP が得られます。この問題を表す実際の制約グラフには、 XとYの間に 2 つのエッジが含まれている必要があることに注意してください。これは、 C2が無向であるのに対し、AC-3 で使用されているグラフ表現は有向であるためです。

AC-3 は、まずC1の要求に従ってXの定義域から偶数でない値を削除して問題を解決し、 D( X ) = {0, 2, 4 } を残します。次に、 C2によって暗示されるXとY間の弧を調べます。 ( X =0, Y =4)、( X =2, Y =2)、および ( X =4, Y =0) のペアのみが制約C2と一致します。その後、 AC-3 は D( X ) = {0, 2, 4} および D( Y ) = {0, 2, 4}で終了します。

AC-3 は擬似コードで次のように表現されます。

 入力:変数X
   の集合Xの各変数​​xに対するドメインD(x)
   の集合。D(x)には、xの可能な値vx0、vx1...vxnが含まれる。
   変数xに対する単項制約R1(x)の集合は満たされなければならない。
   変数xとyに対する、満たされなければならない二項制約R2(x, y)の集合
   
 出力：
   各変数の円弧一貫性ドメイン。
 
 function ac3(X, D, R1, R2)
      //初期ドメインは単項制約と整合するように作られる。X
     内の各xについて
         D(x) := { vx は D(x) 内にある | vx は R1(x) を満たす }   
     // 'worklist' には、一貫性があるかどうかを証明したいすべてのアークが含まれます。
     worklist := { (x, y) | 関係 R2(x, y) または関係 R2(y, x) が存在する }
 
     する
         ワークリストから任意の円弧 (x, y) を選択する
         ワークリスト := ワークリスト - (x, y)
         アーク縮小(x, y) 
             の場合、 D(x)が空の
                 場合、失敗
             を返す、そうでない場合
                 worklist := worklist + { (z, x) | z != y であり、関係 R2(x, z) または関係 R2(z, x) が存在する }
     ワークリストが空ではない間
 
 関数arc-reduce(x, y)
      bool change = false
     は、 D(x)内の各vxに対して行われます。
         vxとvyが制約R2(x, y)を満たすようなD(y)内の値vyを見つける
         そのようなvyがない場合{
             D(x) := D(x) - vx
             変更:= true
         }
     返品変更

^{このアルゴリズムは、}最悪の場合の時間計算量はO ( ed3 )、空間計算量はO ( e ) です。ここで、eは弧の数、d は最大ドメインのサイズです。

• AK Mackworth. 関係ネットワークの一貫性。人工知能、8:99-118、1977年。
• スチュアート・J・ラッセル、ピーター・ノーヴィグ著『人工知能：現代的アプローチ』、202-233、2003年。