木探索によるＣＳＰの解法 (Tree search algorithms for solving CSPs) 認知システム論 制約充足（ 2 ） 制約をみたす組合せを探すエージェント バックトラック法 フォワードチェック 動的変数順序

制約充足問題 (CSP) とは（復 習） 変数 (variable) の集合 各変数の領域 (domain) 変数間の制約 (constraint) の集合 CSP すべての制約を満たすよう な変数への値の割当て 解 x 1 x 2 … x n D 1 D 2 … D n C ij ={(a,b),(c,d),…} 変数 x i -x j 間で許される値の組の集合． 与えられた組 (u,v) が許されるか否か を判定する関数 allowed(i,j,u,v) でも良 い． x 1 = a 1 x 2 = a 2 … x n = a n

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

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

バックトラック法 (1) 深さ優先探索 各レベルで１つの変数の 値を選択する 解となる可能性のない経 路を早めに検出して後戻 り (backtrack) する フォワードチェック (forward checking) 動的な変数順序付け (dynamic variable ordering) などと組み 合わせると 効果的 Backtracking

バックトラック法 (2) 概要 前進 これまでの部分解との間に 制約違反がないように部分解を拡張 後退 a1a1 x1x1 a2a2 x2x2 a3a3 x3x3 a4a4 x4x4 部分解 a1a1 x1x1 a2a2 x2x2 a3a3 x3x3 a’ 4 x4x4 x1x1 x2x2 x3x3 x4x4 x5x5 a1a1 a2a2 a3a3 a4a4 a5a5 Ｏ Ｋ！ 拡張できないときは， 後戻りをして直前の選択をやりなおす 前 進後 退 a1a1 x1x1 a2a2 x2x2 a3a3 x3x3 a4a4 x4x4 x5x5

バックトラック法 (3) ４クイーンでの動作 Ｑ Ｑ Ｑ Ｑ Ｑ Ｑ １２３４ Ｑ 解 １２３４ １２３４ １２３４ x1x1 x2x2 x3x3 x4x4

バックトラック法 (4) アルゴリズ ム /* メイン */ すべての変数 x[ i ] の値を⊥（未設定）にする． BACKTRACK( 1 ); boolean BACKTRACK(int depth) { if( すべての i について x[ i ] ≠ ⊥ ) return true; int j ← x[j]= ⊥であるような変数番号 j から任意の１ つ；... x1x1 x2x2 x3x3 x4x4 x5x5 a1a1 a2a2 a7a7 a4a4 ⊥ x6x6 ⊥ x7x7 ⊥ x8x8 ⊥ j = 5

バックトラック法 (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

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 の順序で値を割り当てていく． x1x1 x2x2 x3x3 x4x4 x5x5 a1a1 a2a2 a3a3 a4a4 ⊥ x6x6 ⊥ x7x7 ⊥ x8x8 ⊥ j = depth = 5

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

フォワードチェック (1) a1a1 x1x1 a2a2 x2x2 a3a3 x3x3 a4a4 x4x4 部分解 前進 部分解を拡張 すでにＯＫと なっている これ以降の変数の領域から a 5 と矛盾するすべての値を削除 a1a1 x1x1 a2a2 x2x2 a3a3 x3x3 a4a4 x4x4 a5a5 x5x5 x6x6 x7x7 xnxn いずれかの領域が 空になったら 後戻り 先読みにより前方をチェック する Forward Checking

フォワードチェック (2) うまくいく例 AFT ALE EEL HEEL HIKE HOSES KEEL KNOT LASER LEE LINE SAILS SHEET STEER TIE x1x1 x2x2 x 8 に入 る 単語が ない！ HOSE E E T H S

フォワードチェック (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

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

動的変数順序 (1) Dynamic Variable Ordering boolean BACKTRACK-FC(int depth) { if ( 全変数に値の割当てがある ) return true; int j ← x[j]= ⊥であるような変数番号 j から任意の１ つ； どの変数を選んだらよいか？ 最小領域ヒューリスティック 領域に含まれる値の個数が最小である変数を選ぶ 最大制約ヒューリスティック まだ値の割当てられていない変数との間の制約の個 数が最大である変数を選ぶ １ ２ タイブレイク（引き分けの とき）

動的変数順序 (2) グラフ彩色の例（３ 色） RGB 領域 =3 制約 =2 RGB RGB RGB RGB 領域 =3 制約 =4 領域 =3 制約 =3 領域 =3 制約 =4 領域 =2 制約 =1 RGB 領域 =3 制約 =2 領域 =2 制約 =2 領域 =2 制約 =3 領域 =3 制約 =2

実験による性能比較 ProblemBTBT+DVOBT+FCBT +FC +DVO USA>1,000,000 2,00060 n-Queens>40,000,00013,500,00040,000,000817,000 Zebra3,859,0001,00035, Random 1415,0003,00026,0002,000 Random 2942,00027,00077,00015,000 BT=backtracking FC=forward checking DVO=dynamic variable ordering 数値は制約のチェック回数