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

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

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

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

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

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

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

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

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

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

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

10 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

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

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

13 フォワードチェック (2) うまくいく例 123 45 67 8 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

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

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

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

17 動的変数順序 (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

18 実験による性能比較 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,000500 Random 1415,0003,00026,0002,000 Random 2942,00027,00077,00015,000 BT=backtracking FC=forward checking DVO=dynamic variable ordering 数値は制約のチェック回数