アーク制約アルゴリズム
Arc Constraint Algorithm

AC-1


与えられた制約ネットワークの全てのアークを，固 定された順序で巡回して，候補値集合から削除が起きなくなるまでREVISEを繰 り返し適用する．

procedureAC-1(G) begin for i ←1 until n do NC(i); Q ←{(i,j)|(i,j)∈arcs(G), i≠j }; repeat begin CHANGE ←false; for each (i,j)∈Q do CHANGE ←(REVISE((i,j))∨CHANGE); end untile¬CHANGE end

(制約ネットワークの例)


(演習問題)


AC-1の計算量


以下を仮定するとAC-1の最悪計算量はO(a³ne)となる．

• 制約ネットワークのノード数: n
• 制約ネットワークのアーク数:e
• 各領域D_iの要素数: a(簡単のために全て同じとする)

AC-2


領域からの要素の削除を機械的に繰り返すのではなく， REVISEによって領域から要素の削除が行われたとき，その影響を次々と隣接す るノードに伝播していく．伝播が静まるまで待ってからもとのループに戻る．

procedureAC-2(G) begin for i ←1 until n do NC(i); for i ←1 until n do "GLOBAL LOOP" begin Q ←{(i,j)|(i,j)∈arcs(G), j < i }; Q' ←{(j,i)|(j,i)∈arcs(G), j < i }; while Q ≠φdo begin while Q ≠φdo begin (k,m)←pop(Q); if REVISE((k,m)) then Q'←Q'∪{(p,k)|(p,k)∈arcs(G), p≦i, p≠m }; end Q ←Q'; Q'←φ; end end end

(制約ネットワークの例)
(クロスワードパズルに対するAC-2の実行例)


(演習問題)


AC-2はWaltzのアルゴリズム，もしくは 制約伝播法(contratint propagation)を用いた 記号的弛緩法(symbol relaxation method)とし ても呼ばれる．

AC-3


AC-3は，AC-2とは違って制約の伝播を幅優先に行う ．AC-1との違いは，変数の領域から候補値の削除 が生じたとき，矛盾の生じたアークだけを再考の対象とすることである．

procedureAC-3(G) begin for i ←1 until n do NC(i); Q ←{(i,j)|(i,j)∈arcs(G), i≠j }; while Q ≠φdo begin (k,m)←pop(Q); if REVISE((k,m)) then Q←Q∪{(i,k)|(i,k)∈arcs(G), i≠k, i≠m }; end end

(制約ネットワークの例)
(クロスワードパズルに対するAC-3の実行例)


(演習問題)


AC-3の計算量


以下を仮定するとAC-3の最悪計算量はO(a³e)となる．

• 制約ネットワークのノード数: n
• 制約ネットワークのアーク数:e
• 各領域D_iの要素数: a(簡単のために全て同じとする)

• 講義の詳細