制約充足問題
2003/04/28
1G00P139-1 若槻聡一郎
2.5 記号を用いた制約充足問題
クロスワードパズル
性質に関する推論
・時間的なもの
・空間的なもの
多面体の分析
などに用いることができる
例2.8 クロスワードパズル
１～８を変数とみなす
空欄に以下の単語が入る
HOSES,LASER,SAILS,
SHEET,STEER
HEEL,HIKE,KEEL,KNOT,
LINE
AFT,ALE,EEL,LEE,TIE
制約充足問題としての解法
変数はそれぞれ文字数が決まっている（１，
２，３，８は５文字、４，５は４文字、６，７は３
文字）
２つの単語が交差するところは同じ文字で
なくてはならない（１の３文字目と２の１文字
目は同じ文字、など）
制約充足問題としての解法(2)
以上のことを考えながら、制約を課していく。
例えば１と２の間には次のような制約ができる。
C1,2 := {(HOSES,SAILS),(HOSES,SHEET),
(HOSES,STEER),(LASER,SAILS),
(LASER,SHEET),(LASER,STEER)}
制約充足問題としての解法(3)
これらの制約を考えていくと、以下のような
解が得られる。
性質に関する推論
ある出来事が起こった正確な時間、物体
の位置などに関する推論を行うとき、それ
らを具体的に数値化してしまうと考えられ
る選択肢が無限になってしまう
→それらを抽象的な記号として考えることで
有限個の選択肢で考えることができる！
例2.9 時間に関する推論
・あるミーティングに関する問題
・おのおのの人物はある連続した期間ミーティングに
出席していた
Jonesがいる間にミーティングが始まった
Whiteがいる間にミーティングが終わった
Whiteはミーティングが始まった後に到着した
SmithはJonesがいなくなった後に到着した
BrownとWhiteはSmithがいるときに会話をした
→このときJonesとWhiteは話すことは可能だったか？
問題の解釈
ミーティングに参加している間の行動につ
いてはいろいろ考えられる（誰かと話す、
昼休みを取る、電話を受ける、などなど）
→これらの行動をイベント（event）と総称す
る
これらのイベントは切れ目のない有限の時
間とする
問題の解釈（一例）
問題の条件から、以下の解釈が考えられる
（実線はその人が出席していた時間帯を表
す）
時間の記号表現について
すべての人の出席時間帯は以下のDの形
で表される
以下では、Aがいた時間帯を(abegin , aend)、B
がいた時間帯を( bbegin < bend )とおく
二つの時間の関係について
二人が出席していた時間の関係としては以
下にあげる１３個の可能性が考えられる
・before, after
・meets, met-by
・overlaps, overlapped-by
・starts, started-by
・during, contains
・finishes, finished-by
・equals
A before B, B after A
・aend < bbegin
A meets B, B met-by A
・aend = bbegin
A overlaps B, B overlapped-by A
・ abegin < bbegin
・ aend < bbegin
・ aend < bend
A starts B, B started-by A
・ abegin = bbegin
・ aend < bend
A during B, B contains A
・ bbegin < abegin
・ aend < bend
A finishes B, B finished-by A
・ bbegin < abegin
・ aend = bend
A equals B
・ abegin = bbegin
・ aend = bend
TEMP, REAL-OVERLAP
前述の２つの時間の関係の全体集合を
TEMPとする
AとBが時間を「共有」していた、ということ
のみを示す制約をREAL-OVERLAPとする。
（これは、before、after、meets、met-by以
外の９つの制約の結合として得られる）
・ abegin < bend
・ bbegin < aend
問題の解法（その１）
１個１個のイベントを変数（variable）とする
イベントと変数名は以下のようになる
イベント
ミーティングをしていた期間
Jonesがいた期間
Brownがいた期間
Smithがいた期間
Whiteがいた期間
変数名
M
J
B
S
W
この変数を用いて適当な制約を定義する
制約（ミーティング×人物）
問題文からミーティングと人物に関する３つの
制約がわかる
①(〔overlaps〕∪〔contains〕∪〔finished-by〕)(J,
M)
②〔overlaps〕(M, W)
③〔REAL-OVERLAP〕(M, S)
※Brownについては問題文からミーティングに
いたかどうかわからないので言及しない
制約からわかること
①Jbegin < Mbegin , Mbegin < Jend
②Wbegin < Mend , Mend < Wend , Mbegin < Wbegin
③ Mbegin < Send , Sbegin < Mend
（MとSはある長さの時間を「共有」してい
た）
制約（人物×人物）
同じく人物間の制約もわかる
①〔before〕(J, S)
→Jend < Sbegin
②〔REAL-OVERLAP〕(B, S)
→ Bbegin < Send , Sbegin < Bend
③〔REAL-OVERLAP〕(B, W)
→ Bbegin < Wend , Wbegin < Bend
④〔REAL-OVERLAP〕(S, W)
→ Sbegin < Wend , Wbegin < Send
問題の解決
質問は、「 JonesとWhiteは話すことは可能
だったか？ 」
→これは、〔REAL-OVERLAP〕(J,W)をみたす
ような解が存在するか？ということと同じ
この問題では、 Jbegin < Wend は常に成り立
ち、 Wbegin < Jend が成り立つ場合も考えられ
るので、この質問に関する回答はYESであ
る
回答例
M
J
B
S
W
問題の解法（その２）
この解き方では、変数は、３つのイベントか
ら導かれる（３つのイベントA,B,Cがあり、A
とBの関係、BとCの関係は既知とする。ここ
からAとCの関係が導かれるというもの）
例えば〔overlap〕(A,B)、〔before〕(B,C)の
場合は〔before〕(A,C)となる
これを(overlap, before, before)のように
書く
問題の解法（その２）
このような３つの時間関係の集合はすべて
TEMP×TEMP×TEMP（以下T３と表記）の
部分集合（subset）として表される
T３は４０９個の要素からなる
時間関係における選言命題
選言命題（before∨meetsなど）によって、
状況を部分的に知ることができる。
時間関係における選言命題では、AとBの
間の関係がわかっていれば、BとAの関係
も一意に決まる（例えばAとBの関係が
before∨meetsならばBとAの関係は
after∨met-byとなる）
制約充足問題の定義（１）
n個（n>3）のイベントがあるとき、２個のイ
ベントの選び方はｎC２通り考えられる
イベントi, j (i, j ∈[1…n], i<j)間に実際に
成り立つ時間関係をxi,j、成り立ち得る時間
関係の集合をDi,jとおく(このときxi,j∈Di,j,、
Di,j⊆TEMP)
制約充足問題の定義（２）
同様に、３つのイベントの選び方はｎC３通り
考えられる
イベントi, j, k(i, j, k ∈[1…n], i<j<k)間に
できる制約をCi,j,kとおくと
Ci,j,k := T３∩(Di,j× Dj,k×Di,k)
問題から読み取れる制約
この問題ではJ,M,B,S,Wの５つのイベント
があるので、１０種類のxが存在する
問題文から以下のことが読み取れる
xJ,M∈{overlaps, contains, finished-by}
xM,W∈{overlaps}
xJ,M∈ REAL-OVERLAP
問題から読み取れる制約（２）
xJ,S∈{before}
xB,S∈ REAL-OVERLAP
xB,W∈ REAL-OVERLAP
xS,W∈ REAL-OVERLAP
残りのxはTEMP
問題の解決
問題で聞いているのはxJ,W∈ REAL-OVERLAP
となるようなxJ,Wが存在するかということ
→これは存在する（ ∵xJ,W∈ TEMP）
具体例はCJ,M,W := (contains,
overlaps,overlaps)など（∵overlaps∈REALOVERLAP）
例2.10 空間に関する推論
・２軒の庭付きの家と道に関する
問題
・２軒の家が道路によってつな
がっている
・１つ目の家は庭に囲まれている
か庭の境界に接している
・２つ目の家は庭に囲まれている
・このとき２つ目の家の庭と道路
の関係はどう推論できるか？
２つの物の関係について
以下の８つが考えられる
disjoint, meet, equal, covers, coveredby,
contains, inside, overlap
RCC8(Region Connection
Calculus with 8 relations)
２つの物の関係の全体集合
ここでは３つの物の関係を考える
これはRCC8× RCC8× RCC8（以下S３と
表記）の部分集合（subset）
RCC8の要素は１９３個
制約充足問題の定義
問題に出てくる「物体」をH1（１つ目の家）、
G1（１つ目の家の庭）、H2（２つ目の家）、
G2（２つ目の家の庭）、R（道路）とおく
物体A, B間に実際に成り立つ位置関係を
xA,B、成り立ち得る位置関係の集合をDA,Bと
おく(このときxA,B∈DA,B,、DA,B⊆RCC8)
制約充足問題の定義（２）
同様に、物体A, B, C間にできる制約をCA,B,C
とおくと
CA,B,C := S３∩(DA,B× DB,C×DA,C)
問題から読み取れる制約
xH1,G1∈{inside, coveredby}
xH2,G2∈{inside}
xH1,H2∈{disjoint}
xH1,R∈{meet}
xH2,R∈{meet}
問題から読み取れる制約（２）
xG1,G2∈{disjoint, meet}
xH1,G2∈{disjoint, meet}
xG1,H2∈{disjoint, meet}
xG1,R∈ RCC8
xG2,R∈ RCC8
問題の解法
この場合はG2とRの関係なので、G2とH2
とRについて考えれば十分である（H1とG1
はあまりG2とRの関係に影響してこない）
CG2,H2,R := S３∩(contain×meet ×DG2,R)
なので、G2とRの関係xG2,Rとして考えら
れるのは、
xG2,R∈{contains, covers, overlap}である
例2.11 多面体の分析
以下の直線によって作られた２つの物体
がどんな形の立体に対応するか
接点（junction）
接点には４種類あり、各々の接点は２つか
３つの辺を持っている
左からL字型、fork型、T字型、arrow型
4つのラベル
辺の性質を明確にするため、＋、－、→、←
の４つのラベルを使う
＋(convex)は２つの見える面の間を移動する
ときに270°かかるもの
－(concave)は２つの見える面の間を移動す
るときに90°かかるもの
矢印(boundary)は一方の面が隠れていると
きに書く
ラベルの使用例
矢印は隠れてな
い方の面が矢印
の進行方向右側
に来るように書い
ていく
解釈の仕方
解釈の仕方は１つに限定する必要はない
（Fig2.13の場合辺ACとAEは、立体が「浮い
ている」と考えれば→、「壁にかかってい
る」と考えれば－と解釈できる）
解釈の仕方（２）
辺ABは＋にも－にもなりうる
（立方体と考えればABは明らかに＋だが、
面ABCDを底面とする箱の一部（AEとDGに
つながる面が欠落したもの）と考えれば－
とみなせる）
ただし、後者の考え方のときは適応する立
体がない（後者の解釈の仕方だとC,E,Gに
つながるfork型の接点が欠落している）
接点とラベルの関係
Huffmanさんが発
見した、立体が存
在しうる状況にお
いての接点とラベ
ルの関係
→これらを使うと制約
充足問題の観点か
ら議論できる！
問題の解法（１）
接点を変数、辺を制約とする
２つの接点に関する制約を変換テーブルを
用いて作っていく
例えば、接点AとBは辺ABを共有している
ので、クロスワードのときと同じように、共
有する部分は同じ物にしなければならない
だが、クロスワードとは少し勝手が異なる
（＋や－の場合はよいが、矢印を使うときは
ABとBA（接点の場所）で逆になる）
変換テーブル（L字型）
L :={(→,←),
(←,→),
(＋,→),
(←,＋),
(－,←),
(→,－)}
変換テーブル（fork型）
fork :={(＋,＋,＋),
(－,－,－),
(→,←,－),
(－,→,←),
(←,－,→)}
変換テーブル（T字型）
T :={(→, ←,←),
(→,←,→),
(→,←,＋),
(→,←,－)}
変換テーブル（arrow型）
arrow :={(←,→,＋),
(＋,＋,－),
(－,－,＋)}
変換テーブルの使用例
Fig2.13に関してAとEに対する制約CA,Eを決
める
接点Aは第2要素がAE、接点Eは第2要素
がEAとなっているのでそれぞれの第2要素
が同じ物になるような制約がかかる
CA,E :={((←,→,＋), (→,←)),
((←,→,＋), (－,←)),
((＋,＋,－), (←,＋)),
((－,－,＋), (→,－))}
問題の解法（１）
前述のように２つの接点に関する制約を定
めていく
２つの接点に関する制約＝１つの辺の制
約なので、制約は辺の数分だけできる
この方法でやっていけばうまく立体の形を
定めていける
問題の解法（２）
辺を変数とする（とりうる値は＋、－、→、
←）
今度は接点を制約とする
例えばFig.2.13なら以下の七つの制約が
できる
arrow(AC, AE, AB), fork(BA, BF, BD),
L(CA, CD), arrow(DG, DC, DB),
L(EF, EA), arrow(FE, FG, FB), L(GD, GF)
問題の解法（２）
１つ目の解き方と同様、この解き方も辺の
向きを気にしなくてはならない
よって、辺にも向きを考えるための以下の
ような制約をつける必要がある
edge := {(＋,＋),(－,－),(→,←),(←,→)}
問題の解法（２）
辺の制約はFig2.13において具体的には
以下の９つ
edge(AB, BA), edge(AC, CA),
edge(CD, DC), edge(BD, DB),
edge(AE, EA), edge(EF, FE),
edge(BF, FB), edge(FG, GF),
edge(DG, GD)
問題の解法（２）
あとはこの２要素（edge、L）ないしは３要素
（fork、T、arrow）の制約を組み合わせて
解いていけばよい。
解答
2.6 制約最適化問題
関数objと制約から最適解を見つけ出す
一般性を保持するために我々は最適解を
最大解と意味付けする
制約最適化問題の扱う領域は広い！（こ
の問題に関する本もたくさん書かれてい
る）
よってここでは３つの例に限定する
例2.12 ナップザック問題
n個の物があって、それぞれが重さと価値
をもっている
ナップザックはある一定の容量が決まって
いる
価値が一番高くなるような物の組み合わせ
はどれかを求める
解法
n個の物の重さをそれぞれa1,…,an、価値を
b1,… , bn、ナップザックの容量をvとする
さらに、n個の値x1 ,…, xn∈｛0,1｝を定義す
る
解法（２）
ナップザックの容量から、以下の制約が設けられ
る
最適解は、上記の制約の元で以下の式
が最大値をとるようなものである
よってこの式が関数objである
例2.13 コイン問題
1,2,5,10,20,50ユーロセントのコインがあ
るとき、1ユーロ未満の料金を払うのにど
のように払えばコインの枚数が一番少なく
なるか？
解法
99セントを払うときのコインの枚数をそれ
ぞれx1, x2, x5, x10, x20, x50、とする（ ただし
x1 ∈[0…99], x2 ∈[0…49], x5 ∈[0…19],
x10 ∈[0…9], x20 ∈[0…4], x50 ∈[0…1] ）
解法（２）
合計を表す文字i∈[1…99]、iユーロを払う
ときに使ったコインの枚数を表す文字i1, i2,
i5, i10, i20, i50、を次のような制約の元で定義
する
∃i1 ∈[0… x1 ], ∃i2 ∈[0… x2 ], ∃i5 ∈[0…
x5 ], ∃i10 ∈[0… x10 ], ∃i20 ∈[0… x20 ], ∃i50
∈[0… x50 ]に対して
i1+ i2+ i5+ i10+ i20+ i50 = I
解法（３）
このとき、全部で９９個（iの種類分）の制約
ができる
解はx1+ x2+ x5+ x10+ x20+ x50の最小値と
して得られる
しかしここでは最大値問題にするため、関
数objとして以下の式を用いる
-(x1+ x2+ x5+ x10+ x20+ x50)
この解法の欠点
この解法には制約の中に変数が存在する
という欠点がある
このような問題は解くのが難しい
→異なる表現を用いて制約を単純化！
新たな解法
今まで使っていたx1, x2, x5, x10, x20, x50,
に加えて
を用いる
（ i∈[1…99] ）
そうすると制約は次の式で書き換えられる
ただし
（ i∈[1…99] , j∈{1,2,5,10,20,50} ）
新たな解法（２）
このようにすると最適解を求めやすい
ちなみに関数objは前述の物と同じ物を用
いる
例2.14 ゴロム定規
要素数m個のゴロム定規とは、m個の中
のどの２つの間の距離を測ってもすべて異
なるような要素の列のことを言う
例えば0,1,4,9,11などは要素数５個のゴロ
ム定規である
・1個とびの要素の差：1,3,5,2
・2個とびの要素の差：4,8,7
・3個とびの要素の差：9,10
・4個とびの要素の差：11
m要素ゴロム定規の解法
1≦i<j≦mである自然数i,j
different((i, j), (k, l))⇔((i≠j)∪(k≠l))
disjoint((i, j), (k, l))⇔((i≠j)∩(k≠l))
ゴロム定規の要素をそれぞれx1, x2,…, xm
と定める
m要素ゴロム定規の解法（２）
このとき以下の制約が生じる
・xi,< xi+1 ( i∈[1,…,m-1])
・xj- xi ≠xl – xk (different((i, j), (k, l)))
このとき関数objは-xm
m要素ゴロム定規の解法（3）
xi ≠xk (i,k<j)のときxj- xi ≠xl – xk
xj ≠xl (i<j,l)のときxj- xi ≠xl – xiより
・xj- xi ≠xl – xk (disjoint((i, j), (k, l)))
と書き換えられる
m要素ゴロム定規の解法（４）
zi,j = xj- xi とおくと
zi,j ≠zk,l (different((i, j), (k, l)))
という正の整数のみの制約というふうにも
考えられる
ゴロム定規について（豆知識）
ゴロム定規は符号理論、X線結晶学、回路
設計、電波天文学などの分野に応用され
ている
今まで発見された最長のゴロム定規は21
要素で長さは333
© Copyright 2024 ExpyDoc
