制约充足问题.PPT

* 　クロスワードパズルもCSPである．ただし，これは雑誌等でよく見られるような「タテのカギ」とか「ヨコのカギ」と呼ばれるヒントがないものとする．（そういう自然言語を理解するのはまだAI の研究途上のテーマである．）そのかわりに，候補となる単語が辞書の中に数多くリストとして列挙されているものとする． 　この問題がCSPであることを確認するために，単語が入るべきタテあるいはヨコの一つながりの枠を各変数に対応付ける．その枠の長さに合った文字数の単語のすべてを集めて，対応する変数の領域とする．たとえば，「ヨコの１」を変数x1とすると，その領域D1は５文字からなる単語の集合となる．「タテの２」，「タテの３」，「ヨコの８」を表す変数の領域も，文字数５なのでこれと同じものとなる． 　タテ，ヨコの２つの枠が交差するような２つの変数の間には，交差部での１文字が一致することを制約として記述する．この図では，x1,x2間の制約は，「x1の３文字目とx2の１文字目が等しい」ことを表すもので，その組合せを列挙すると， 　C12={(HOSES,SAILS),(HOSES,SHEET),(HOSES,STEER), 　　　　(LASER,SAILS),(LASER,SHEET),(LASER,STEER)} となる．もちろん，２つの文字列x1，x2を引数として「x1の３文字目とx2の１文字目が等しい」ことを判定する論理関数を実装したプログラムによって制約を表現してもよい． * 　グラフ彩色問題は，頂点の集合Ｖと辺の集合ＥからなるグラフＧ＝（Ｖ，Ｅ）と整数ｃ（色の数）が与えられたとき，Ｖの各頂点のそれぞれに１からｃまでのどれかの値（色）を対応づける問題である．制約として，辺で結ばれた（隣接した）ノードを互いに異なる色とすることが求められる． * 　グラフ彩色問題は，地図の塗り分け問題と直接の対応関係がある．この問題は，地図上の隣接した地域に異なる色を塗る問題である．地域をグラフの頂点とし，隣接した地域を表す２つの頂点を辺で結んだグラフを考えると，そのグラフの彩色問題は，もとの地図塗り分け問題と等価な問題となる． * 　グラフ彩色問題が確かにCSPであることを，このスライドで確認してほしい． * 　グラフ彩色問題は，携帯電話の基地局（アンテナ）への周波数割当て問題とも関係がある． 　近接した基地局に同一の周波数を割り当てると，電波が干渉し合って混信の原因となるので，異なる周波数帯（チャネル）を割り当てる必要がある． 　そこで，基地局をグラフの頂点とし，異なるチャネルを割り当てるべき近くの基地局どうしは辺で結ぶ．各チャネルを色とみなせば，これはグラフ彩色問題となる． * 　線画解釈の問題は，CSPを一躍有名にした問題である．この問題には，入力として，２次元平面上に線分で描かれた線画が与えられる．これは利用者が直接描いた線画かもしれないし，カメラで撮影した画像から色や濃淡の変化を検出する画像処理によって辺（エッジ）を抽出したものかもしれない．線画解釈とは，このような線画を３次元空間内の立体として解釈する問題である． * 　３次元での解釈は，具体的には，線画に現れる線分に，＋，－，←，→のいずれかのラベルを割り付けることによって表現される． 　各ラベルの意味は，スライドに示してある通りである．「＋」ラベルの辺の両側には物体の表面が見え，その辺自体は前方（見ている側，手前）に凸になっている．「－」ラベルの辺もやはり両側に物体の表面が見えるが，その辺自体は前方に凹（後方に凸）になっている点が異なる． 矢印（←，→）の辺は，その進行方向の右側だけに物体の表面が見えており，左側は空間になっている．（ただし，スライドの３つめの例は，空間中に浮いている立体とする．無限に広い平面上に置いてある立体と解釈するときには， 矢印が割り当てられている辺のラベルは「－」となる．） 　すべての辺にこのようなラベルを正しく割り付けることができれば，それで線画を立体として解釈したものとみなす． * 　線画を構成している線分が互いに端点で接しているパターンをジャンクションという．ジャンクションには，V, W, Y, T という４種類がある．Vは２本の線分が結合したものである．W, Y, T は３本の線分の結合であるが，各線分間の角度が鋭角か鈍角か（90度との大小）による違いにより，分類されている． 　この応用を考えた研究者が綿密に分析した結果，ジャンクションを３次元立体の辺の交わりと解釈するには，各線分のラベル付けは，このスライドに示される少数個のパターンのいずれかでなければならないことに気がついた．つまり，ラベル付けにはこのような制約があるのである．したがって，線分に変数を対応