ノード制約アルゴリズム
ノード制約アルゴリズム
以下のアルゴリズムは，各ノードiに対してノード整合を達成する手続き NCと，制約ネットワーク全体に対してノード整合を達成する手続きNC-1からな る．
procedure
NC(i):
D
i
← D
i
∩{x|P
i
(x)};
procedure
NC-1(G):
begin
for
i ←1 until n
do
NC(i);
end
アーク整合操作
先に述べたように，アーク整合操作は有向アーク(i,j)に対して D
i
←D
i
∩{x|∃y[y∈D
j
∧ P
ij
(x,y)]}を実行する．
これにより，
与えられたノードiの候補値集合D
i
からアーク (i,j)で結ばれたノードjの候補値集合D
j
に制約P
ij
を満 足しうる要素をもたない要素を全て除去
する．以下のREVISE手続きにより行う．
function
REVISE((i,j))
begin
DELETE
←
false
;
for each
x∈D
i
do
if
<P
ij
(x,y)なるy∈D
j
が存在しない>
then
begin
< D
i
からxを除去する>;
DELETE
←
true
;
end
return
DELETE
end
以下を仮定するとREVISEの計算量は
O(a
2
)
となる．
各領域D
i
の要素数: a(簡単のために全て同じとする)
...Return
講義の詳細
...Return
...Return