- 制約ネットワークの整合性
- 後に学ぶ制約充足アルゴリズムでは，制約が満足されるよう，各変数の 可能な値の集合を絞り込んでいく．
- 各ノードに対応付けられた変数の可能な値の集合が，どれだけ制約を満足し ているかを判断する概念として以下のノード整合，アー ク整合，経路整合がある．
- ノード整合(node consistent)
- [定義: ノード整合]
- 制約ネットワークの全てのノードがノード整合しているとき，その制約ネットワークはノード整合しているという．
- [ノード整合操作]
- アーク整合(arc consistent)
- [定義: アーク整合]
- 制約ネットワークの全ての有向アークがアーク整合しているとき，その制約ネットワークはアーク整合しているという．
- [アーク整合操作]
- 経路整合(path consistent)
- [定義: 経路整合]
- 制約ネットワークの全ての長さmの経路についてk次経路整合(k≦m)していない ものが含まれていないとき，その制約ネットワークは m次経路整合しているという． ただし，ノードi,j間に 長さmの経路があっても，ノードi,j間に直接の制約が無ければそこには経路制 約が成立しているともいえないとも言えないことに注意．
- 制約ネットワークの全ての経路が全ての j≦kに対してj次経路整合のとき，
- 制約ネットワークが強k次経路整合(k < n)であっても， 各変数領域が単一要素からなる集合でなければ解が存在するという保証はない．
- 制約充足問題の解法
- 強n次整合(nは与えられた制約充足問題のノード数)を達成する．
- 後戻り法(backtracking)と組み合わせる．
ノードi(ノードiと変数 viに対応づけられた領域からなる)について， ∀x[x∈Di →Pi(x)] が成立するとき，iはノード整合(node consistent)しているという． |
Di ←Di ∩{x|Pi(x)}
有向アーク(i,j)について， ∀x[x∈Di →∃y[y∈Dj∧Pij(x,y)]] が成立するとき，(i,j)はアーク整合(arc consistent)しているという． |
クロスワードパズルの例
Di ←Di ∩{x|∃y[y∈Dj∧Pij(x,y)]}
(ノード整合とアーク整合の例．2次経路整合はしていない)
ノードの集まり(i0,i1,...,im)を通る長さmの経路は，条件
∀x∈Di0 ∀z∈Dim
[Pi0(x)∧Pim(z)∧Pi0im(x,z)
→∃y1,...,ym-1[y1∈Di1 ∧...∧ym-1∈Dim-1
∧Pi1(y1)∧...Pim-1(ym-1)
∧Pi0i1(x,y1)∧...Pim-1im(ym-1,z)]]
が成立するとき，m次経路整合(path consistent)しているという．
|
(経路整合を考慮する状況)
...Return