制約充足問題の表現
Representation

述語論理による表現


制約が2項からなる場合

∃x1 ∈ D1, ..., xn ∈ Dn [P1(x1) ∧... ∧Pn(xn) ∧ P12(x1,x2)∧...∧P1n(x1,xn)∧ P23(x2,x3)∧...∧P2n(x2,xn)∧ ....∧ Pn-1,n(xn-1,xn)

ただし，P_ij(x_i,x_j) = P_ji(x_j,x_i)なので，制約として P_ij: i < j のみを用いる．

グラフを用いた表現


2項までの場合．

• ノード: 対応する変数の領域
• アーク(エッジ): 制約を受ける変数の対

このグラフを制約ネットワークと呼ぶ．

...Return

• 講義の詳細