Constraint Networks

Constraint Networks 2.2~2.3
５月７日
上田研究室
M2 西村光弘
1
2.2 Numeric and Boolean
Constraints
2.1.2（P27）で取り扱った関係の記述を、より簡潔
で扱いやすいように記述する
↓
算術制約やブーリアン制約を用いる
算術制約：より簡潔な表現
ブーリアン制約：禁止されるタプルを表現
2
2.2.1 Numeric Constraint
 算術式で制約を簡潔に表現する
例：4-queens problem
全ての２つの変数ｘiとｘｊ（図の縦列）
∀i,jに対し、
横列が同じでない → xi≠ｘｊ
斜めの場所にない → ｌxi – xjｌ≠ｌi - jｌ
Rij = {(xi, xj) ｌ xi ∈ Di, xj ∈ Dj,
xi≠ｘｊ and ｌxi – xjｌ≠ｌi - jｌ}
3
Numeric Constraint
もう一つの例 + α
 変数領域を整数の有限部分集合にする
 ２つの変数の間の２項制約を線形不等式の結合
“integer liner program”
で表す
（3xi + 2xj ＜ 3 ）∧（-4xi + 5xj ＜ 1）
Crypto-arithmetic Puzzles
上記の線形制約を用いて
簡単に定式化できる
SEND
＋MORE
MONEY
同じ文字は同じ数字が
隠されている
数字は０～９
4
2.2.2 Boolean Constraints
 制約問題の変数が２値である場合、関係を
記述するのによくBoolean制約を使う
例：Alex, Bill, Chrisをpartyに招待する場合
A＝命題“Alexはpartyに来る”（B,Cも同様）とする
→ (A → B) ∧ (C → A)
わかっていること
・Alexが来るならBillも来る
↓同じ意味
・Chrisが来るならAlexも来る
(￢A∨B) ∧ (￢C∨A)
5
例：Alex, Bill, Chrisをpartyに招待する
Chrisが来るとしたらBillは来る？
 命題論理
命題理論φ = C ∧ (A→B) ∧ (C→A)
 Chrisが来るとしたら、Billが来るかどうか
→Billが来ないと仮定して矛盾が生じるかどうかを見
る
つまり、φ∧￢Bを解いて満たされるかをチェック
↓
この場合は矛盾が示されるので、“Billは来る”
6
CNF (conjunction normal form)
 CNF＝論理積標準形

命題変数・・・P,Q,Rで表す。
取りうる値は｛true, false｝or｛1, 0｝

Clause(節)・・・命題変数と選言記号（disjunction）
を用いてα、βなどで表す
α＝（P∨Q∨R）（P∨Q∨R∨T）→（α∨T）と略記
（α∨Q）∨（β∨￢Q）→（α∨β）

CNF・・・clauseの集合をφで表す
φ＝｛α1,・・・,αt ｝
7
CNFとSAT
（propositional satisfiability problem）
 CNFは、変数が命題（true or false）であるような制
約ネットワークでよく見られる
補足説明
CNF theory φ＝（A∨B）∧（C∨￢B）→変数３つ、制約（clause）２つ
制約A∨Bは関係RAB＝[(1,0),(0,1),(1,1)]を表す
 SATは命題充足可能性問題

CNF理論がmodelを持つかどうかを決定すること
model＝どのclauseの規則も破らないように、変数に真値を割り当てたもの

関連する制約問題で矛盾しないかどうかを決定するこ
と
8
Primal constraint graph




命題理論φの構造をinteraction graphで描画・・・G（φ）
無向グラフ
ノードは各命題変数
エッジは同clauseにある変数の各ペア
B
A
C
D
Figure2.8
E
G(φ)＝｛（￢C）,（A∨B∨C）,（￢A∨B∨E）,（￢B∨C∨D）｝
9
2.2.3 Combinatorial Circuits
Diagnosis
 Boolean命題言語は回路を表すのによく使われる
 回路の診断作業は制約充足問題として定式化さ
れうる
 定式化の方法


変数と各ゲート（AND、OR、XOR）を関連づける
Boolean制約によって、各ゲートのinputとoutputの関係
を記述する
 観測されるoutputから、回路の振る舞いが適切か
間違いかを確認する
10
2.3 Properties of Binary
Constraint Networks
 今まで出てきた制約を処理する概念はBinary
Networkのために紹介された
Binary Networkは役に立つ
↓なぜかというと・・・
後の章にでてくる制約の一般的理論を理解するの
に役に立つから
 この2.3節ではbinary constraint networkの特徴に
ついて書いてある
11
2.3.1 Equivalence and
Deduction with Constraints
 制約を計算する主な概念はconstraint deduction
↓
初期の制約集合から、新しい制約集合を
推論すること
例：幾何制約ｘ＞ｙとｙ＞ｚからｘ＞ｚを推論する
推論された新しい制約を加えた集合は、初期の
集合と同等のconstraint networkを生み出す
12
例：graph-coloring problem
図の説明
 各ノードは変数x１、x２、x３
 それぞれ同じdomain｛red, blue｝
 Not-equal制約
 R21=R32=｛（blue, red）,（red, blue）｝
 エッジのないx1とx3の関係はuniversal relation
 R13={(red, blue),(blue, red),(red, red),(blue, blue)}
 制約からの解は２つでρ123={(red, blue, red)(blue, red, blue)}
 そこから推論されるx１とx３の関係は、新しい制約R’13={(red,
red)(blue, blue)}を作る（deduction）
redundant
 元の制約集合をR、R’13を加えた制約集合をR’とすると、このRと
R’は同値であると言える（equivalence）
13
図：graph-coloring
R=
x2
x2
red
blue
red
blue
≠
x1
R’=
≠
red
blue
red
blue
≠
x3
x1
red
blue
≠
＝
red
blue
x3
(b)
(a)
Figure2.10
14
RedundancyとEquivalenceを
一般的に言うと
 Redundancy

制約ネットワークからある制約を取り除いても解の全て
の集合が変わらない時の、そのある制約のこと
 Equivalence

２つの制約ネットワークにおいて


同じ変数の集合の上で制約ネットワークが定義されている
同じ解の集合を表現できる
15
定義2.2 Composition
 制約推論はCompositionを通して達成される
 Rxy,Ryz(binary or unary constraint)があるとして、
composition Rxy・Ryzから２項関係Rxzを作る
Rxz={(a,b)ｌa∈Dx, b∈Dz ∃c∈Dy
such that (a,c)∈Rxy and (c,b)∈Ryz}
 compositionの計算の定義をjoinとprojectionを使って定式
化
Rxz = Rxy・Ryz = π{x,z}(Rxy Ryz)
例：R’ = π{x1,x3}(R12 R23) = {(red,red),(blue,blue)}
projection
join
16
図：join and projection
R12
x1
R23
x2
blue red
red blue
x2
x3
blue red
red blue
R13 = π{x1,x3}(R12 R23)
↓join
R12 R23
x1 x2 x3
blue red blue
red blue red
→
projection
x1
x3
blue blue
red red
17
例2.2 composition 0-1matrix
 2項関係を0-1matrixで表現すると、compositionは
Boolean matrixの掛け算になる
red blue
red blue
R12 =
R23 =
red 0 1
blue 1 0
red 0 1
blue 1 0
red blue
R12・R23 = R13 =
0 1
1 0
×
0 1
1 0
=
1 0
0 1
=
red 1 0
blue 0 1
18
2.3.2 The Minimal and
the Projection Networks
問題提起
どんな関係もbinary constraint networkとして
表現されるか？
↓答え
多くの場合は表現できない（特別なケースだけ表現できる）
↓なぜなら
異なる関係の数＞異なるbinary constraint networkの数
↓どうするか
Binary projection networkによって関係を近似する
19
定義 2.3 projection network
初期の関係 ρ
↓変数の各ペアーでρをprojectionする
Projection networkの関係 P(ρ)
P(ρ)はnetwork P = (X, D, P)で定義される
D={Di}, Di=πi(ρ), P={Pij},Pij=πxi,xj(ρ)
20
例2.3 projection network
 ρ123={(1,1,2),(1,2,2),(1,2,1)}
Projection network P(ρ)
P12={(1,1),(1,2)}, P13={(1,2),(1,1)}
P23={(1,2),(2,2),(2,1)}
P(ρ)からの全ての解はsol(P(ρ))
sol (P(ρ))={(1,1,2),(1,2,2),(1,2,1)}
一般的には
このように
うまく戻らない
例２．４へ
21
例2.4 定理2.1ρ⊆sol(P(ρ))
初期の関係ρ
x1
x2
x3
1
1
2
2
1
2
1
2
2
2
3
2
Projection network P(ρ)
P12={(1,1),(1,2),(2,1),(2,2)}
P23={(1,2),(2,2),(1,3)}
P13={(1,2),(2,3),(2,2)}
余分な解が増えた
sol(P(ρ))
x1
x2
x3
1
1
2
2
2
1
2
1
1
2
2
2
2
3
2
22
定理2.2
￢∃R’, ρ⊆sol(R’)⊂sol(P(ρ))
 Projection network P(ρ)はρを表現するのに、
最も厳しい上限のbinary networkである

説明は前頁（P21）の図を参照
問題提起
P(ρ)はsol(ρ)を表現するのに最も厳しい
関係記述かどうか？
23
定義2.4 “tighter than” network
relationship
同じ変数の集合を持つ、２つのbinary network
をRとR’として、
R’がRと比べ少なくても同じtightさである
⇔全てのi,jに対し、R’ij⊆Rij
例：資料P14のgraph-coloring図2.10の(a)と(b)が上の
RとR’に相当する
説明：意味論的に同等で同じ解が得られるのに、 RよりR’
のほうが条件が厳しい
24
定義2.5 intersection on
networks
 2つのnetwork RとR’のintersection（R∩R’）は
binary networkである。（明らか）
命題2.1
 ２つの同等なnetwork RとR’があるなら、


R∩R’はそれらと同等なnetworkである
R∩R’は両方より少なくともtightである
25
例2.5 命題2.1の例題説明
 資料P１４のgraph-coloring図の関係で、（ｂ）のR２３の≠制約
を取り除いたRとR’のintersectionを考える
 R:


R12=R23=｛（blue, red）,（red, blue）｝
R13={(red, blue),(blue, red),(red, red),(blue, blue)}
 R’ :
R12=｛（blue, red）,（red, blue）｝
 R13=｛（blue, blue）,（red, red）｝
 R23={(red, blue),(blue, red),(red, red),(blue, blue)}
 R∩R’ (minimal network)
 R12= R23= ｛（blue, red）,（red, blue）｝
 R13=｛（blue, blue）,（red, red）｝

26
定義2.6 minimal network


R 0と同等の全てのnetworkの集合を｛R 1,…, R l ｝
ρ＝sol(R 0)
 R 0のminimal networkは
l
M(R 0)=M(ρ)=∩ Ri=1iと定義される
 定理2.3
全てのbinary network R に対し、
ρ＝ sol(R), M(ρ) = P(ρ)が成り立つ
命題2.2
If (a,b)∈Mij then ∃t∈sol(M) such that t[i]=a, t[j]=b
27
2.3.3 Binary-Decomposable
Network
 例2.6
ρ=
x y z t
a a a a
a b b b
b b a c
x y
πxyzρ=
z
a a a
a b b
b b a
 ρはbinary constraint networkで表現可能
 projectedな関係であるπxyzρはbinary networkで表現不可能
 なぜならπxyzρ⊂sol(P(πxyzρ))
 定義2.7
関係がbinary-decomposableであるとは、その関係が
binary constraintsで表現可能であるということ
28
図2.11 M13={(2,1),(3,4)}
R12={(1,3),(1,4),(2,4),(3,1),(4,1),(4,2)}
R13={(1,2),(1,4),(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)}
R14={(1,2),(1,3),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,2),(4,3)}
R23={(1,3),(1,4),(2,4),(3,1),(4,1),(4,2)}
x1 x2 x3 x4
R34={(1,3),(1,4),(2,4),(3,1),(4,1),(4,2)}
↓
R13={(1,2),(1,4),(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)}
R13’={(1,2),(2,1),(3,4),(4,2),(4,3)}
R13’’={(1,4),(2,3),(2,1),(3,4),(4,1)}
R13’’’={(1,4),(2,1),(3,4),(4,3)}
R13’’’’={(2,1),(4,1),(3,2),(2,3),(3,4),(1,4)}
1
2
3
4
↓
M13 = R13∩R13’∩R13’’∩R13’’’∩R13’’’’ = {(2,1),(3,4)}
29

Download Report