制約プログラミング
目次
- 制約プログラミング
- 例 − 8クイーン問題
- 制約解消システム
- 局所制約伝播
- 値域付き変数
- 制約の簡略化
電子情報工学特別実験のページへ戻る
制約充足問題をプログラミングパラダイムとして扱う方法論は
制約プログラミングと呼ばれています.
制約プログラミングの基本要素は,
- オブジェクトの集合 X
- 状態の集合 S
- 制約の集合 C
です.
各オブジェクトは状態集合Sで規定された状態をとることができます.
ただし,Cで記述されたすべての制約を満足するような状態割り当てでないといけません.
この考え方は,ちょうど連立方程式に似ています.
連立方程式の各式が「制約」です.
少し身近な例で考えてみましょう.
例えば,「太郎の所持金と花子の所持金はあわせて1000円だ.」という文は,
- 二つのモノ=「オブジェクト」,すなわち,
「太郎の所持金」,「花子の所持金」 について述べている.
- 「太郎の所持金」と「花子の所持金」の間には,
「合計で1000円である」という関係=「制約」がある.
という情報を表しています.
「太郎の所持金」,「花子の所持金」はそれぞれ「お金の量」ですから,
円を単位とした0を含めた自然数を値=「状態」として持つことになります.
これはどのように形式的に表現したらよいでしょうか?
オブジェクト「太郎の所持金」,「花子の所持金」
を変数として表し,その状態を変数の値として次のように表すのが自然でしょう.
ただし,「太郎の所持金」を変数X,「花子の所持金」を変数Yとします.
X + Y = 1000
この式だけでは値を決めることができませんが,
この式はXとYの間の関係を表しており,
XならびにYの値を決めるための一つの情報になります.
また,
XとYについてはどちらが主でどちらが従であるかという優先順位は全くないということに注意して下さい.
Xの値が決まればYの値がきまるし,
逆に,Yの値が先に決まればXの値がきまるでしょう.
つまり,関係=制約には方向性はありません.
ここで,さらに,
別の制約「太郎の所持金は花子の所持金より200円多い」が得られたとすると,
X,Yは
X + Y = 1000
X = Y + 200
という二つの関係を同時に満足する値となります.
これはまさに連立方程式です.
制約が重なることにより,
X=600,Y=400というようにオブジェクトの状態が決定されます.
以上述べたように,制約プログラミングでは基本要素を次のように表す場合が多いようです.
- オブジェクト
- 変数
- オブジェクトの状態
- 変数の値
- 制約
- 変数の値の間で成り立つ関係
今の例では,変数の間の関係は(加減算を含む)「等値関係」でしたが,
これ以外にもさまざまな関係を考えることができます.
そのような例として,一種のパズルであり,
制約充足問題の一つである「8クイーン問題」をみてみましょう.
「8クイーン」は
チェスの盤面上に8個のクイーンを互いに効き筋にならないように配置する問題です.
次図は解の1つを表しております.
□□Q□□□□□
□□□□□Q□□
□□□Q□□□□
□Q□□□□□□
□□□□□□□Q
□□□□Q□□□
□□□□□□Q□
Q□□□□□□□
図 8クイーン問題の解の1例
この8クイーン問題を先ほどの枠組に当てはめると以下のようになります.
- オブジェクト
8 x 8の盤面上のマスの集合 = 8 x 8 個の変数
- 状態
それぞれのマスについて「クイーンが配置されている」
「クイーンが配置されていない」の二通り = 各変数の値
- 制約
各オブジェクトに対して状態を割り当てるときの条件,
つまり,「ルール」である.
「クイーンの効き筋は縦・横・斜めである」,
「クイーンの数は8個である」,
「あるクイーンは他の全てのクイーンの効き筋の上にない」,
「クイーンは全て盤の上にある」など個々の制約の集合となる.
いまここでは,各制約を直観的な言葉で書きましたが,
実際に形式的に記述する時には,
これら制約を各オブジェクト(の状態)の間の関係として詳細化する必要があります.
ここでは詳しくは触れませんが,
一般に,パズルを解くプログラムの場合には,
各制約がルールとしてすでに与えられていますので,
逆に,それら制約を詳細化しやすいように「状態」や「オブジェクト」の選択,
つまり,データ構造の設計を行ないます.
制約プログラミングにおいて上記の制約を解く処理系は制約解消システムと呼ばれます.
制約解消システムはその名が示す通り,全ての制約を充足する解を見つけることです.
つまり,充足できる場合はその解を,できない場合はできないことを示します.
一般に制約解消システムの動作は次ようになります.
- 制約を集める.
- 制約の充足可能性を判定する.
- 適切な形式で解を提示する.
制約充足可能性を判定するアルゴリズムとして最も単純なものの一つは,
バックトラック(Backtrack,後戻り)による生成・検査型のアルゴリズムです.
例えば,二つの制約A,Bを同時に満足する解を求めるためには,
- 制約Aから生成可能な解を一つ求める.
- その解がもう一方の制約Bを満足するかを検査する.
- 満足する場合は充足可能なので終了.
- 満足しない場合は制約Aから別の解を生成する.
別の解が生成できないのであれば,充足不能である.
生成できる場合はStep 2 へ行く.
とします.
制約が複数存在する場合にはこの手続きを組み合わせて対応します.
しかし,このバックトラックアルゴリズムをそのまま用いると,
効率が非常に悪くなります.
値を生成するための制約と生成された値を検査する制約に分類し,
制約を使用する方向を最初から固定しているためです.
さらに,解の生成段階では必ず成立すべき解を生成しているのではなく,
解の候補の1つを「仮に」解として用いるために,
無秩序な後戻りを繰り返す可能性があります.
効率の良くない生成・検査型アルゴリズムに代わる方式として
代表的なものには,以下のものがあります.
いずれも,制約の使用する方向を特定しないための工夫がなされています.
- 局所制約伝搬を用いる方法
- 変数に値域を付加する方法
- 制約の簡略化による方法
各制約について以下の手続きを繰り返します.
すでに値の決まっている変数の値に基づいて
制約が満たされるかどうかをチェックする.
- 満足しない場合
制約を充足することはできないので,「解なし」
- 満足する場合
まだ値の決まっていない変数の値を調べ,
「その制約を満たすためにはある特定の値である必要がある」
変数があれば,その変数の値をその値にする.
(例えば,X + Y = 1000 という制約において,
Y = 400 であることがわかったならば,
その制約を満足するためには,X = 600 でなければならない.)
この方法では,順次変数の値が決定していきます.
これは解き方というよりも,データ構造の一つと考えるほうがいいでしょう.
この方法では,変数に値域を付加します.
有限集合を値域に持つ変数を導入することにより,
= や \= (not equal) などの基本的制約を効率良く実行できます.
値域に相当する集合がただ一つの要素からなる集合になったときに,
その変数の値が決定されたと考えます.
制約の簡略化による方法では,
制約を順次簡略化していくことを制約を解くことと見なします.
先に述べた二つの方法では解を変数に対する値の割当としていましたが,
制約の簡略化による方法では,
変数に対する値の割当は制約の簡略化による副産物であると考えます.
制約の簡略化の方法には局所制約伝播と同様な方法により変数の値を具体化するものや,
プログラム変換による制約の書き換えによるものなどがあります.