Constraint Networks 2.2~2.3 ５月７日 上田研究室 M2　西村　光弘

2.2 Numeric and Boolean Constraints 2.1.2（P27）で取り扱った関係の記述を、より簡潔 で扱いやすいように記述する 　　　　　　　　　↓ 　算術制約やブーリアン制約を用いる 算術制約：より簡潔な表現 ブーリアン制約：禁止されるタプルを表現

2.2.1 Numeric Constraint 算術式で制約を簡潔に表現する 例：4-queens problem ∀i,jに対し、 横列が同じでない → xi≠ｘｊ 斜めの場所にない → ｌxi – xjｌ≠ｌi - jｌ Rij = {(xi, xj) ｌ xi ∈ Di, xj ∈ Dj, xi≠ｘｊ and ｌxi – xjｌ≠ｌi - jｌ}

Numeric Constraint もう一つの例 + α 変数領域を整数の有限部分集合にする ２つの変数の間の２項制約を線形不等式の結合で表す 　　（3xi + 2xj ＜ 3 ）∧（-4xi + 5xj ＜ 1） Crypto-arithmetic Puzzles 上記の線形制約を用いて 簡単に定式化できる “integer liner program” 上のような線形制約はnumeric constraintの特別なもので、スケジューリングや一時的空間的推論に適用される http://bach.istc.kobe-u.ac.jp/puzzle/　パズルのページ 　９５６７ 　１０８５ １０６５２ SEND 同じ文字は同じ数字が 隠されている 数字は０～９ ＋MORE MONEY

2.2.2 Boolean Constraints 制約問題の変数が２値である場合、関係を記述するのによくBoolean制約を使う 例：Alex, Bill, Chrisをpartyに招待する場合 A＝命題“Alexはpartyに来る”（B,Cも同様）とする わかっていること ・Alexが来るならBillも来る ・Chrisが来るならAlexも来る → 　(A → B) ∧ (C → A) ↓同じ意味 (￢A∨B) ∧ (￢C∨A)

例：Alex, Bill, Chrisをpartyに招待するChrisが来るとしたらBillは来る？ 命題論理 命題理論φ = C ∧ (A→B) ∧ (C→A) Chrisが来るとしたら、Billが来るかどうか →Billが来ないと仮定して矛盾が生じるかどうかを見る つまり、φ∧￢Bを解いて満たされるかをチェック 　　　　　　　　　　　　↓ この場合は矛盾が示されるので、“Billは来る”

CNF (conjunction normal form) 命題変数・・・P,Q,Rで表す。 取りうる値は｛true, false｝or｛1, 0｝ Clause(節)・・・命題変数と選言記号（disjunction）を用いてα、βなどで表す α＝（P∨Q∨R）　 （P∨Q∨R∨T）→（α∨T）と略記 （α∨Q）∨（β∨￢Q）→（α∨β） CNF・・・clauseの集合をφで表す φ＝｛α1,・・・,αt ｝

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の規則も破らないように、変数に真値を割り当てたもの 関連する制約問題で矛盾しないかどうかを決定すること どのclauseも偽にはならないように、変数に値を割り当てたモデル

Primal constraint graph 命題理論φの構造をinteraction graphで描画・・・G（φ） 無向グラフ ノードは各命題変数 エッジは同clauseにある変数の各ペア B C A D Figure2.8 E G(φ)＝｛（￢C）,（A∨B∨C）,（￢A∨B∨E）,（￢B∨C∨D）｝

2.2.3 Combinatorial Circuits Diagnosis Boolean命題言語は回路を表すのによく使われる 回路の診断作業は制約充足問題として定式化されうる 定式化の方法 変数と各ゲート（AND、OR、XOR）を関連づける Boolean制約によって、各ゲートのinputとoutputの関係を記述する 観測されるoutputから、回路の振る舞いが適切か間違いかを確認する

2.3 Properties of Binary Constraint Networks 今まで出てきた制約を処理する概念はBinary Networkのために紹介された 　　Binary Networkは役に立つ 　　　　　　　　↓なぜかというと・・・ 後の章にでてくる制約の一般的理論を理解するの に役に立つから この2.3節ではbinary constraint networkの特徴について書いてある

2.3.1 Equivalence and Deduction with Constraints 制約を計算する主な概念はconstraint deduction ↓ 初期の制約集合から、新しい制約集合を 推論すること 例：幾何制約ｘ＞ｙとｙ＞ｚからｘ＞ｚを推論する 推論された新しい制約を加えた集合は、初期の 集合と同等のconstraint networkを生み出す

例：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） 元の制約集合をR、R’13を加えた制約集合をR’とすると、このRとR’は同値であると言える（equivalence） redundant

図：graph-coloring x2 x2 red blue red blue R= R’= ≠ ≠ ≠ ≠ red blue red ＝ (a) (b) Figure2.10

RedundancyとEquivalenceを 一般的に言うと 制約ネットワークからある制約を取り除いても解の全ての集合が変わらない時の、そのある制約のこと Equivalence ２つの制約ネットワークにおいて 同じ変数の集合の上で制約ネットワークが定義されている 同じ解の集合を表現できる

定義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

図：join and projection R12 R23 x1 x2 x2 x3 blue red blue red red blue R13 = π{x1,x3}(R12 　R23) ↓join R12 　R23 x1 x3 　 → projection x1 x2 x3 blue blue blue red blue red red red blue red

例2.2 composition 0-1matrix 2項関係を0-1matrixで表現すると、compositionはBoolean matrixの掛け算になる red blue red blue R12 = red blue 0 1 R23 = red blue 0 1 1 0 1 0 red blue 0 1 0 1 1 0 R12・R23 = R13 = × = = red blue 1 0 1 0 1 0 0 1 0 1

2.3.2 The Minimal and the Projection Networks 問題提起 どんな関係もbinary constraint networkとして 表現されるか？ ↓答え 多くの場合は表現できない（特別なケースだけ表現できる） 　　　　　　　　　　　　　　　　↓なぜなら 異なる関係の数　＞　異なるbinary constraint networkの数 　　　　　　　　　　　　　　　　↓どうするか Binary projection networkによって関係を近似する

定義 2.3 projection network 初期の関係 ρ ↓変数の各ペアーでρをprojectionする P(ρ)はnetwork P = (X, D, P)で定義される D={Di}, Di=πi(ρ), P={Pij},Pij=πxi,xj(ρ)

例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)} 一般的には このように うまく戻らない 例２．４へ

例2.4 定理2.1ρ⊆sol(P(ρ)) 初期の関係ρ sol(P(ρ)) Projection network P(ρ) x1 x2 x3 1 1 2 1 2 2 sol(P(ρ)) 2 1 3 x1 x2 x3 2 2 2 1 1 2 1 2 2 2 1 2 2 1 3 余分な解が増えた 2 2 2

定理2.2 ￢∃R’, ρ⊆sol(R’)⊂sol(P(ρ)) Projection network P(ρ)はρを表現するのに、最も厳しい上限のbinary networkである 説明は前頁（P21）の図を参照 問題提起 P(ρ)はsol(ρ)を表現するのに最も厳しい 関係記述かどうか？

定義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’ 　　のほうが条件が厳しい

定義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である

例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）｝

定義2.6 minimal network R 0のminimal networkは M(R 0)=M(ρ)=∩ R iと定義される R 0と同等の全てのnetworkの集合を｛R 1,…, R l ｝ ρ＝sol(R 0) R 0のminimal networkは M(R 0)=M(ρ)=∩　R iと定義される 定理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 l i=1 定理2.3 証明はexercise 説明書きは、P43定義2.6の下２行　　minimal networkは、そのminimal networkの解集合をもつprojection networkと同じものとみなせる 命題2.2は定理2.3から自明 P43下２行　　minimal networkによって認められる変数のペアがあったとしたら、少なくとも１解は存在することを保証する

2.3.3 Binary-Decomposable Network 例2.6 ρはbinary constraint networkで表現可能 projectedな関係であるπxyzρはbinary networkで表現不可能 なぜならπxyzρ⊂sol(P(πxyzρ)) 定義2.7 関係がbinary-decomposableであるとは、その関係が binary constraintsで表現可能であるということ x y z t x y z a a a a a a a ρ = πxyzρ= a b b b a b b b b a c b b a

図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)} R34={(1,3),(1,4),(2,4),(3,1),(4,1),(4,2)} x1 x2 x3 x4 ↓ 1 R13={(1,2),(1,4),(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)} 2 R13’={(1,2),(2,1),(3,4),(4,2),(4,3)} 3 R13’’={(1,4),(2,3),(2,1),(3,4),(4,1)} R13’’’={(1,4),(2,1),(3,4),(4,3)} 4 R13’’’’={(2,1),(4,1),(3,2),(2,3),(3,4),(1,4)} ↓ M13 = R13∩R13’∩R13’’∩R13’’’∩R13’’’’ = {(2,1),(3,4)}