木探索によるＣＳＰの解法 (Tree search algorithms for solving CSPs)

Presentation on theme: "木探索によるＣＳＰの解法 (Tree search algorithms for solving CSPs)"— Presentation transcript:

1 木探索によるＣＳＰの解法 (Tree search algorithms for solving CSPs)
認知システム論　制約充足（2） 制約をみたす組合せを探すエージェント 木探索によるＣＳＰの解法 (Tree search algorithms for solving CSPs) 　バックトラック法 　フォワードチェック 　動的変数順序 　今回の授業では，制約充足問題（CSP）を解くアルゴリズムを学ぶ．そのアルゴリズムは，基本的にはすでに学んだ探索木を利用したアルゴリズムの一種であるが，CSP特有の問題設定を利用して，効率化がはかられている．このようなアルゴリズム（あるいはそれを実装したプログラム）は，制約解消器あるいは制約ソルバー(constraint solver)と呼ばれることもある．今回は，その基礎となる深さ優先探索アルゴリズムの一種であるバックトラック法(backtracking) を学ぶ．また，バックトラック法と組み合わせてさらに効率を向上させるための手法として，フォワードチェック(forward checking) 及び動的変数順序(dynamic variable ordering) について学ぶ．

2 制約充足問題(CSP)とは（復習） x1 x2 … xn D1 D2 … Dn Cij ={(a,b),(c,d),…}
変数(variable)の集合　 各変数の領域(domain) 変数間の制約(constraint)の集合 D1 D2 … Dn Cij ={(a,b),(c,d),…} 変数 xi-xj 間で許される値の組の集合． 与えられた組(u,v)が許されるか否かを判定する関数 allowed(i,j,u,v)でも良い． 解 　制約充足問題（constraint satisfaction problem: CSP）は，つぎの３項目 1) 変数の集合 2) 各変数の領域 3) 変数間の制約の集合 を具体的に示すことにより定義される． 　領域 Di は変数 xi の取りうる値の集合を表している (i=1,2,...,n)．領域に含まれる要素は有限個であると仮定する． 　制約とは，変数の値の組合せが満たすべき条件であり，取ることが許される値の組合せの集合で表現される．たとえば， 　　　Cij = {(a,b),(c,d)} という制約は，変数xiとxjの間の制約を表していて，(xi=a, xj=b)と(xi=c, xj=d)という値の組合せだけが許される． 　制約は，組(xi=u, xj=v)が許されるとき真，そうでないとき偽を返すような関数 allowed( i, j, u, v ) として表現されてもよい．たとえば，変数x1,x2間とx2,x3間にだけ 　　　C12={ (a, b), (c, d) }，C23={ (b, c) } という制約があり，他の変数間に制約がないときは， 　　　allowed( i, j, u, v ) = if ( i==1 && j==2) return ((u==a && v==b) || (u==c && v==d)); else if ( i==2 && j==3) return (u==b && v==c); else true 　制約充足問題では，一般に，そのような制約が複数個与えられる．それらすべての制約を満たすように変数に値を割当てることを，「制約充足問題を解く」という．そのような割当てのことをその問題の解という．制約充足問題の解を求めるプログラムは，制約解消器あるいは制約ソルバー(constraint solver)と呼ばれることもある． すべての制約を満たすような変数への値の割当て x1=a1 x2=a2 … xn=an

3 n クイーン問題 (n queens problem)
制約充足問題の例（復習） n クイーン問題 (n queens problem) クロスワードパズル(crossword puzzles) グラフ彩色問題 (graph coloring) 線画解釈 (interpretation of line drawings) レイアウト (layout) スケジューリング (scheduling) （復習） 　ＣＳＰの例を６つ紹介する．

4 制約充足アルゴリズム (Constraint Solving)
　バックトラック法 　＋ フォワードチェック 　＋ 動的変数順序

5 バックトラック法(1) Backtracking 深さ優先探索 各レベルで１つの変数の値を選択する
　CSPを解くための最も基本的なアルゴリズムはバックトラック法(backtracking)である．これは基本的には深さ優先探索と同じであるが，CSPの場合には，つぎの２つの点でやや特殊化され，効率が改善されている． 　（１）各レベル毎に値を割当てるべき変数を１つに決めている．たとえば，第１レベルではx1に値を割り当てるとして決めてしまい，このレベルでx2などの他の変数に値を割り当てるような探索はしない．その理由は，CSPでは変数に値を割り当てる順序は任意だからである．変数が n 個あれば，値を１つずつ割り当てていく順序は n! 通りもあるのだが，そのうち１通りだけ試せば十分である．今回の授業では，後に述べる「動的な変数順序付け」のときを除き，変数の順序は，x1, x2, x3, …, xn であるとする． 　（２）解となる可能性のない経路を早めに検知して後戻りする．これは，全変数に値を割り当てなくても，それ以前に部分的に割り当てた時点で１つでも制約違反が生じていれば，そこから先にはゴールがないことがわかるからである．たとえば，最初の２つの変数x1, x2に値を割り当てた時点で，それがこの両変数間の制約C12に違反していれば，残りの変数x3, …, xn に値を割り当てなくても，この割当ては失敗であることがわかる． 　深さ優先探索自体が空間計算量が小さい（必要とするメモリの量は探索木の深さに比例する量で抑えられる）ことに加えて，上記の工夫により，バックトラック法はかなり効率的で実用的である． 　しかし，それでも難しいＮＰ困難問題には歯がたたないこともある．そのようなときには，後に述べるフォワードチェックや動的変数順序という工夫を組み合わせると効果的である． フォワードチェック (forward checking) 動的な変数順序付け (dynamic variable ordering) などと組み合わせると 効果的

6 バックトラック法(2) 概要 a1 x1 a2 x2 a3 x3 a4 x4 a1 x1 a2 x2 a3 x3 a4 x4 x5 x1
バックトラック法(2)　概要 前　進 後　退 a1 x1 a2 x2 a3 x3 a4 x4 部分解 a1 x1 a2 x2 a3 x3 a4 x4 x5 前進 後退 x1 x2 x3 x4 x5 a1 a2 a3 a4 a5 ＯＫ！ a1 x1 a2 x2 a3 x3 a’4 x4 　前のスライドでは，探索木を深さ優先でたどるという観点からバックトラック法の概要を説明したが，このスライドでは，具体的にアルゴリズムを記述することを目標として，もう少し細かく見ておく． 　バックトラック法は，前進と後退の２つのステップを適切に織り交ぜて実行する． 　前進ステップでは，すべての変数にまだ値が割り当てられていない初期状態から探索をスタートして，各変数に１つの値を選択して割り当てていく．その結果，一部の変数には値が割り当てられているが，他の変数には値が未設定という状態が生じるが，そのような部分的な割り当てのことを部分解という．前進ステップでは，現在の部分解との間に制約違反がないように，値が未設定である１つの変数に値を割り当てて，部分解を拡張する．この過程が最後まで続き，最終的にすべての変数に値を割り当てることができれば，その時点での部分解がCSPの（完全な）解となる． 　しかし，変数にどの値を割り当てても制約違反が生じ，それ以上前進できない行き止まり(dead end)と呼ばれる状態になったときは，後退ステップを実行することになる．このステップでは，１つ前の変数の値を割り当てた時点に後戻りをして選択をやりなおす．すなわち，その変数にこれまで割り当てたのとは別な値を割り当て直して，再度，前進ステップを試みる．この後退ステップのことを，バックトラッキング(backtracking)と呼んでいる． これまでの部分解との間に 制約違反がないように部分解を拡張 拡張できないときは， 後戻りをして直前の選択をやりなおす

7 解 バックトラック法(3) ４クイーンでの動作 x1 x2 x3 x4 Ｑ Ｑ Ｑ Ｑ Ｑ Ｑ Ｑ １ ２ ３ ４ １ ２ ３ ４ １ ２
　バックトラック法を４クイーン問題に適用したときの動作をアニメーションで表現している．

8 バックトラック法(4)アルゴリズム j = 5 x1 x2 x3 x4 x5 x6 x7 x8 a1 a2 ⊥ a4 ⊥ ⊥ a7 ⊥
/* メイン */　 すべての変数 x[ i ] の値を⊥（未設定）にする． 　　　　　　　　 BACKTRACK( 1 ); boolean BACKTRACK(int depth) { 　 if(すべての i についてx[ i ] ≠⊥) return true; int j ← x[j]=⊥であるような変数番号jから任意の１つ； ...　 j = 5 x1 x2 x3 x4 x5 x6 x7 x8 　バックトラック法を記述した再帰的なアルゴリズムの概略である． 　x は変数への値の設定（部分解）を表す配列である． i 番目の変数の値が a であるとき，x[ i ]=a とする．この変数に値が設定されていないときには，それを示す特別な値（ここでは⊥と表記している）を格納して，x[ i ]= ⊥とする． 　メインプログラムでは，すべての変数の値を⊥として，再帰的関数BACKTRACKを，探索のスタート地点の深さ＝1を引数として呼び出す． BACKTRACK(1)からの戻り値が true のときは，xに解が得られている．解がないときには， BACKTRACK(1)は戻り値として falseを返す． 　一般に，BACKTRACK (depth) は，探索木において，探索のスタート地点の深さ＝depth より深い部分の探索すべてを担当する機能を持ち，この手続きが呼び出された時点（現時点）での x で与えられた部分解をありとあらゆる方法で拡張して最終的な解を探す責任をもっている．現時点での x には制約違反が含まれていないことを前提としている． 　BACKTRACK (depth) は，解を見つけたら論理値 trueを返す．その場合，xには解が格納されている．解が見つからない場合は，論理値falseを返す．その場合，xにはBACKTRACK (depth)を呼び出した時点の割り当てがそのまま格納されている． 　 BACKTRACK (depth) の内容を検討していこう．まず，すべての変数に非⊥（⊥でない値）が設定されているときは，現時点の x に全制約を満たす割当て（解）が得られていることになるので，trueを返して終了する． 　「すべての変数に非⊥が設定されている」かどうかは，一般には，反復を含む判定処理が必要となる．しかし，もっとも基本的なバックトラック法は，ここを単純な方法で設計している．これについては後に述べる． a1 a2 ⊥ a4 ⊥ ⊥ a7 ⊥

9 バックトラック法(5)アルゴリズム（続き）
boolean BACKTRACK(int depth) { 　 if(すべての i についてx[ i ] ≠⊥) return true; int j ← x[j]=⊥であるような変数番号jから任意の１つ； 　 for each b in list D[j] { 　　　 if(x[j]=b と現在のxの設定間に制約違反がない) { 　　　　 x[j]←b；　　　　　 　　　　　 if(BACKTRACK(depth+1)) return true; 　　 x[j]←⊥; 　　　 ｝ 　 ｝ 　 return false; } LOOK BACK 　値が未設定の変数がある場合，それらの変数のうちから任意に選んだ変数の番号を j とする． BACKTRACK (depth)は，拡張されたfor文(for each文）を用いて， look back 処理，すなわち，x[ j ] の取り得る値のリスト（領域 ）D[ j ] から， bの候補を１つずつ選び， 制約違反がないかどうかの検査をする．制約違反がなければ，x[ j ]←b によって部分解を拡張し，そこから先の問題を再帰的に BACKTRACK(depth+1) に丸投げして解いてもらう．これが「前進ステップ」である． 　ここで実行するlook back処理は一般に反復的な処理となるが，このアルゴリズムでは詳細を省略している．基本的には，x[ i ]=a, x[ j ]=b という２変数への割り当てが許される（制約に違反しない）かどうかを調べる論理関数 allowed (i, j, a, b)を定義しておき，すでに値が設定されている x[ i ]=a 毎にx[ j ]=bとの組合せが許されるかどうかをチェックすることになるだろう．許されない組合せが１つでもあれば「制約違反あり」と判定する． 　さて，再帰的に呼び出した BACKTRACK(depth+1)が true を戻してきたら，解が見つかったということなので，BACKTRACK (depth) も trueを戻して終了する．この場合，x に解が格納されている． 　 BACKTRACK(depth+1)が false を戻してきたら，解が見つからなかったということなので， x←⊥によって設定 x=b を解除し， for ループの機能を利用して，x[ j ] に別な b ∈D[ j ] を割り当てて，部分解を拡張する前進ステップを続行する． 　x[ j ] に領域 D[ j ] のどの値を割当てても解を見つけることができなければ，forループは最後まで回って正常に終了する．このとき， BACKTRACK (depth) は，false を戻すことによって自分の責任範囲の探索を「失敗(false)」という報告とともに終了する．これが上位レベル（つまり，x[ j ]より１つ前の変数の処理）への「後退ステップ」，すなわち，バックトラック（後戻り）になっている．

10 X1，X2, … ， Xn の順序で値を割り当てていく．
boolean BACKTRACK(int depth) { 　 if(depth > n) return true; int j ← depth； for each b in list D[j] { 　　　 OK ←true; for i ← 1 to j－1 { 　　　　　　if(!allowed(i,j,x[i],b)) { OK ←　false; break; } } if(OK){ x[j]←b；　　　　　 if(BACKTRACK(depth+1)) return true; 　　 x[j]←⊥; 　　　 ｝ 　 ｝ 　 return false; } LOOK BACK 　最も基本的なバックトラック法は，変数に値を設定する順番を，あらかじめ x[ 1 ], x[ 2 ], ..., x[ n ] に固定しておく．その場合には，未設定を表す⊥は必要なく，深さ depthのBACKTRACKでは，x[ 1 ], x[ 2 ], ... , x[ depth - 1 ] までが設定済み，x[ depth ], ..., x[ n ]が未設定となるように実装すればよい． 　この場合，BACKTRACKが最初の if 文で判定する「すべての変数に非⊥が設定されている」かどうかは， depth > nによって簡単に判定できる．もし，depth≦nならば，j←depth とすればよい． 　また，２つめの if 文で判定する「x[ j ]=b と現在のxの設定間に制約違反がない」かどうかは，このスライドのように，内側の forループを用いて，x[ j ]=b という設定がこれまでのx[ 1 ], x[ 2 ], ..., x[ j-1 ]の設定との関係で制約違反とならないかどうかを，制約を表現する allowed 関数でチェックし，制約違反が生じなければ OKの値を true，１つでも制約違反が生じれば OK の値をfalseとすればよい． x1 x2 x3 x4 x5 a1 a2 a3 a4 ⊥ x6 x7 x8 j = depth = 5 X1，X2, … ， Xn の順序で値を割り当てていく．

11 制約充足アルゴリズム (Constraint Solvers)
　バックトラック法 　＋ フォワードチェック 　＋ 動的変数順序

12 これ以降の変数の領域から a5と矛盾するすべての値を削除
フォワードチェック(1) 先読みにより前方をチェックする Forward Checking a1 x1 a2 x2 a3 x3 a4 x4 部分解 いずれかの領域が 空になったら 後戻り 部分解を拡張 前進 a1 x1 a2 x2 a3 x3 a4 x4 a5 x5 x6 x7 xn 　フォワードチェック(forward checking，前方検査)は，バックトラック法と組み合わされて使用されるテクニックである．これは，先読みによって前方（まだ値を割り当てていない変数群）をチェックし，早い時点で失敗を検知して後戻りをすることを意図している． 　スライドの図は，いま変数 x5 に値 a5 を割り当てようとしている状況を表している．以下では x5, a5 を一般的に x, a として考え方を説明する． 　変数 x に値 a を与えると，その先の各変数の領域から，この x=a と矛盾するすべての値を事前に削除する．そのとき，いずれかの領域が空になったら，（それ以上前進しても解には到達できず，x=a は失敗だったことがわかるので，）後戻りする．そして，x には別な値を割り当てて再度前進することとする． 　一方，その先のどの変数の領域も空にならなかったときは，（解を発見するチャンスが残されているので，）x=aを採択して前進することにする． 　このような事前の制約チェックを変数 x1,x2,x3,x4,…に値を設定するごとに行っていく．その結果，x5の値を決めようとする時点では，x5の領域内のどの値も，すでに値を与えた変数 x1,x2,x3,x4 の値との間では，制約違反が決して生じていないことが保証されている．バックトラック法はすでに決めた値と矛盾しないように制約を後ろ向きに（過去との関係で）チェックしているのに対し，フォワードチェックは今回決めようとしている値と矛盾しないように制約を前向きに（未来との関係で）チェックしているわけである．その意味で，前者は look back，後者は look forward という語句で特徴付けられることもある． すでにＯＫとなっている これ以降の変数の領域から a5と矛盾するすべての値を削除

13 x1 x2 x8に入る 単語が ない！ フォワードチェック(2) うまくいく例 1 2 3 4 5 6 7 8 H O S E S H E
AFT ALE EEL HEEL HIKE HOSES KEEL KNOT LASER LEE LINE SAILS SHEET STEER TIE H O S E S x2 H E x8に入る 単語が ない！ E T 　フォワードチェックが有効にはたらく例として，クロスワードパズルの例を示す．この例では，x1,x2 に単語を選んだ時点で，x8 に入る単語がない．フォワードチェックは，x8 の領域が空になることによって，このことをこの時点で検出できる． 　ふつうのバックトラック法では，これができず，アルゴリズムは x3,x4,x5,x6,x7 に割り当てるべき単語の多くの組合せを無駄に探索してしまう．

14 フォワードチェック(3)アルゴリズム boolean BACKTRACK-FC(int depth) { 　 if(すべての i についてx[i] ≠⊥) return true; int j ← x[j]=⊥であるような変数番号jから任意の１つ； 　 for each b in list D[j] { 　　　 x[i] =⊥であるすべての変数x[i] の領域 D[i] から x[j] = b と矛盾する値を削除する; if(空の領域が生じなかった) { 　　　　 x[j]←b；　　　　　 　　　　　 if(BACKTRACK-FC(depth+1)) return true; 　　 x[j]←⊥; 　　　 ｝ 変数の領域を，値の削除前の状態に戻す； 　 ｝ 　 return false; } LOOK FORWARD 　バックトラック法にフォワードチェックを組み込んだのがこのアルゴリズムBACKTRACK-FCである． 　変数x[ j ]の領域 D[ j ]から，割り当てる値の候補 b を選ぶと，未割当てのすべての変数 x[ i ] の領域 D[ i ] から x[ j ]=b との組合せが許されない値を削除する． 　このとき，空の領域が１つでも生じたら，変数の領域を値の削除前の状態に戻し，forループの機能で別な b を選び直す． 　空の領域が生じなかったら， x[ j ]=b を割り当てて，BACKTRACK-FCを再帰的に呼び出し，残りの部分の割当てを求めさせる． BACKTRACK-FCが true を返したら，このアルゴリズムは true を返して終了する． 一方，BACKTRACK-FCが false を返したら， x[ j ]=bの設定を取り消し，変数の領域をもとに戻し，forループの機能で別な b を選び直す． 　どのbを選んでも解が見つからなければ，このアルゴリズムは false を返して終了する． 　このアルゴリズムを実装するためには，「変数の領域を，値の削除前の状態に戻す」ことができるように，変数の領域から値を削除する工夫が必要である．基本的には，各領域毎に（後入れ先出し型(Last-In First-Out)のデータ構造）スタックを用意して，領域を復元するために必要な情報を保存しておく．たとえば，領域そのもののコピーをスタックに push して保存すれば，復元するときには pop して領域として再設定すればよい．

15 制約充足アルゴリズム (Constraint Solvers)
　バックトラック法 　＋ フォワードチェック 　＋ 動的変数順序

16 Dynamic Variable Ordering
動的変数順序(1) Dynamic Variable Ordering boolean BACKTRACK-FC(int depth) { 　if (全変数に値の割当てがある) return true; int j ← x[j]=⊥であるような変数番号jから任意の１つ； 　 どの変数を選んだらよいか？ １ 最小領域ヒューリスティック 　　領域に含まれる値の個数が最小である変数を選ぶ タイブレイク（引き分けのとき） 　これまで見たアルゴリズムでは，値の割当てがない変数から１つを選んで x[ j ] としている．そのような変数は一般に複数個あるのだが，アルゴリズムでは特にどれにするかは指定していない．つまり，どれでも良いとしている． 　これまでの実行例では暗黙に，変数は x1,x2,x3,... の順番で選ぶことにしていたが，実際にはその必要はない．むしろ，これをうまく選ぶことにより，効率が大きく改善されることが多いのである． 　では，どのような順番に変数を選んだらよいのだろうか？ 　このように実行時に動的に変数の順序を決定する方法を，動的な変数順序付け(dynamic variable ordering, DVO)と呼んでいる． 　お勧めは，つぎの戦略である． 　１．最小領域ヒューリスティック：領域に含まれる値の個数が最小である変数を選ぶ．領域に含まれる値の個数が多いと，探索木の分岐の数がその数と同じだけ多くなり，探索木が大きくなりがちだからである．領域に含まれる値の個数が少ない方が，探索木が小さくなりそうである．特に，領域に含まれる値がただ１個なら，選択の余地なくそれを選ぶしかないことを考えれば，このヒューリスティックの妥当性が納得できるだろう． 　そのような変数が複数あるときには，つぎの方法でタイブレイク（引き分けを解消）する． 　２．最大制約ヒューリスティック：まだ値の割当てられていない変数との間の制約の個数が最大である変数を選ぶ．そのような変数 x の値を決めれば，制約を通して x と結ばれる多くの変数の領域から，フォワードチェックが値を削除し，上記の１の基準をより良く満たす変数をより多く作り出す可能性が高いからである． ２ 最大制約ヒューリスティック 　　まだ値の割当てられていない変数との間の制約の個数が最大である変数を選ぶ

17 動的変数順序(2) グラフ彩色の例（３色） 領域=3 制約=2 R G B 領域=2 制約=1 領域=3 制約=3 R G B
領域=3 制約=2 R G B 領域=2 制約=1 領域=3 制約=3 R G B 領域=2 制約=2 領域=3 制約=4 R G B 領域=3 制約=4 R G B 領域=2 制約=3 領域=3 制約=3 R G B 　バックトラック法（ＢＴ）＋フォワードチェック（ＦＣ）＋動的変数順序（ＤＶＯ）の動作を，簡単なグラフ彩色問題（色の数＝３）で示している（アニメーション）．この例では，バックトラックをせずに解を求めることができている． 　この例題の場合，もしx1,x2,x3,…の番号順に色を決めていくとして，x1=R, x2=R, x3=G, x4=B と進んでくると，x5 で制約違反が生じ，バックトラックする必要が生じてしまうことを確認してほしい．バックトラックして x3=Bに修正し，x1=R, x2=R, x3=B, x4=Gと進むと，またもやx5 で制約違反が生じ，バックトラックする必要が生じる． 領域=3 制約=2 領域=2 制約=2 R G B 領域=3 制約=2

18 実験による性能比較 Problem BT BT+DVO BT+FC BT +FC +DVO USA >1,000,000 2,000
60 n-Queens >40,000,000 13,500,000 40,000,000 817,000 Zebra 3,859,000 1,000 35,000 500 Random 1 415,000 3,000 26,000 Random 2 942,000 27,000 77,000 15,000 　５種類のテスト問題を用いた実験によって，ＢＴ，ＦＣ，ＤＶＯの組合せの実行時間を評価している．表の数値は「制約のチェック回数」であり，特定のコンピュータやプログラミング言語に依存せず，かつ，実際のＣＰＵ時間にほぼ比例する値である．すべての問題において，ＢＴ＋ＦＣ＋ＤＶＯが最優秀であることがわかる．ＵＳＡという問題を除くと，その次に良いのは，ＢＴ＋ＤＶＯの組合せとなっている．ＦＣは領域の削除や復元に手間がかかり，プログラミングもやや面倒だが，その場合にはＦＣを採用せずにＢＴ＋ＤＶＯだけでも，ＢＴ単体よりは，はるかに良い． BT=backtracking FC=forward checking DVO=dynamic variable ordering 数値は制約のチェック回数