制約充足問題（つづき） (Constraint Satisfaction Problems)

Presentation on theme: "制約充足問題（つづき） (Constraint Satisfaction Problems)"— Presentation transcript:

1 制約充足問題（つづき） (Constraint Satisfaction Problems)
知能情報処理　制約充足（1） 制約をみたす意志決定をするエージェント 制約充足問題（つづき） (Constraint Satisfaction Problems) 　制約充足問題 　制約充足アルゴリズム 　バックトラック法 　フォワードチェック 　動的変数順序 　まず，前回の授業で説明した「制約充足問題」と「バックトラック法」を復習し，その後，時間がなく説明できなかった「フォワードチェック」と「動的変数順序」について学ぶ．その後，本来の今回の授業内容に入る． 　今回の授業では，制約充足問題と呼ばれる広い範囲に適用可能な問題群の定義とその実例をいろいろ学ぶ．また，そのような問題の解を求める基本的なアルゴリズムとしてバックトラック法を理解し，その効率を向上させるヒューリスティックな手法として，フォワードチェックと動的変数順序について学ぶ．

2 制約充足問題(CSP)とは x1 x2 … xn D1 D2 … Dn Cxy ={(a,b),(c,d),…}
変数(variable)の集合　 各変数の領域(domain) 変数間の制約(constraint)の集合 D1 D2 … Dn Cxy ={(a,b),(c,d),…} 変数 x-y 間で許される値の組 解 　制約充足問題（constraint satisfaction problem: ＣＳＰ）は，つぎの３項目 1) 変数の集合 2) 各変数の領域 3) 変数間の制約の集合 を具体的に示すことにより定義される． 　領域 Di は変数 xi の取りうる値の集合を表している (i=1,2,...,n)．領域に含まれる要素は有限個であると仮定する． 　制約とは複数の変数の間が満たすべき条件であり，取ることが許される値の組合せで表現される．たとえば， 　　　Cxy = {(a,b),(c,d)} という制約は，変数xとyの間の制約を表していて，(x=a,y=b)と(x=c,y=d)という値の組合せだけが許される． 　すべての制約を満たすように変数に値を割当てることを，「制約充足問題を解く」という．そのような割当てのことをその問題の解という． すべての制約を満たすような変数への値の割当て 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 バックトラック法 概要 a1 x1 a2 x2 a3 x3 a4 x4 a1 x1 a2 x2 a3 x3 a4 x4 x5 x1 x2
バックトラック法　概要 前　進 後　退 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)と呼ばれる状態においては，後退ステップを実行することになる．このステップでは，１つ前の変数の値を割り当てた時点に後戻りをして選択をやりなおす．すなわち，その変数にこれまで割り当てたのとは別な値を割り当て直して，再度，前進ステップを試みる． これまでの部分解との間に 制約違反がないように部分解を拡張 拡張できないときは， 後戻りをして最近の選択をやりなおす

5 バックトラック法(4)アルゴリズム /* メイン */ BACKTRACK( { } );
変数への割当て たとえば：{ x=3, y=2 } /* メイン */　 BACKTRACK( { } ); assignment BACKTRACK( assignment ) { 　if (全変数に値の割当てがある) return assignment; x ← 値の割当てがない変数； 　for each a in Dx { 　　　if ( x=a が制約違反を生じない) { x=a をassignment に追加する；　　　　　 　　　　　　result ← BACKTRACK( assignment ); 　　　　　　if (result ≠ null) return result; x=a をassignmentから削除する； 　　　 ｝ 　 ｝ 　 return null; } 解 前進 解 　バックトラック法のアルゴリズムの概略である． 　assignment は変数への割当て（部分解）を表すデータで，ここでは {x=3, y=2} などと抽象的に書いておくが，実際のプログラミングでは，配列などを用いて，適切に設計されているとする． 　メインプログラムは，再帰的な手続き BACKTRACK に空の割当て { } を渡して実行するだけである． 　BACKTRACK は，引数 assignment で与えられた部分解をありとあらゆる方法で拡張して解を探す責任をもっている手続きである．解を見つけたらそれを返し，解が見つからなければ「失敗」を表す特別な値 null を返すものとする． 　その具体的な処理手順をみておこう．まず，部分解 assignment を受け取ると，まだ値の割当てがない変数 x を１つ選び，それに x の領域 Dx から制約違反を生じないように選んだ値 a を割当てて部分解を拡張し，そこから先の問題を再帰的に BACKTRACK に丸投げして解いてもらう． 　その結果，解が見つかったら，それをそのまま戻して終了する． 　解が見つからなかったら，部分解のうちの x=a を削除し， for ループの機能を利用して，x に別な a ∈Dx を割当てて部分解を拡張する処理を繰り返す． 　x に領域 Dx のどの値を割当てても解を見つけることができなければ，null を返すことによって自分の責任範囲の探索を終了する．これが上位レベル（つまり，xより１つ前の変数の処理）へのバックトラック（後戻り）になっている． 後退

6 これ以降の変数の領域から 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 を選んだときには，すでに値を与えた変数との間で制約違反が決して生じていないことが保証されていることに注意しよう．バックトラック法はすでに決めた値と矛盾しないように制約を後ろ向きに（過去との関係で）チェックしているのに対し，フォワードチェックは今回決めようとしている値と矛盾しないように制約を前向きに（将来との関係で）チェックしているといえる．その意味で，前者は look back，後者は look forward という語句で特徴付けられることもある． すでにＯＫとなっている これ以降の変数の領域から a5と矛盾するすべての値を削除

7 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 に割り当てるべき単語の組合せを無駄に探索してしまう．

8 値の割当てがない変数の領域から x=a と矛盾する値を削除
フォワードチェック(3)アルゴリズム assignment BACKTRACKwithFC( assignment ) { 　if (全変数に値の割当てがある) return assignment; x ← 値の割当てがない変数； 　for each a in Dx { 　　　x=a をassignment に追加する； フォワードチェック; 　　　if (空の領域がない) { 　　result ← BACKTRACKwithFC( assignment ); 　　　 if (result ≠ null) return result; } 変数の領域をフォワードチェック前の状態に戻す； x=a をassignmentから削除する; } 　 return null; } 値の割当てがない変数の領域から x=a と矛盾する値を削除 　バックトラック法にフォワードチェックを組み込んだのがこのアルゴリズムである． 　x=a を assignment に追加することと，それに続くフォワードチェックはセットになった一体の処理なので，後戻りする前にその両者の効果を打ち消す処理をおこなっている．

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

10 動的変数順序(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 　バックトラック法（ＢＴ）＋フォワードチェック（ＦＣ）＋動的変数順序（ＤＶＯ）の動作を，簡単なグラフ彩色問題（色の数＝３）で示している（アニメーション）． 領域=3 制約=2 領域=2 制約=2 R G B 領域=3 制約=2

11 実験による性能比較 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 数値は制約のチェック回数

12 局所整合と局所探索 (Local Consistency and Local Search)
知能情報処理　制約充足(2) 制約をみたす意志決定をするエージェント 局所整合と局所探索 (Local Consistency and Local Search) 　局所整合アルゴリズム 　局所探索アルゴリズム

13 局所的に制約違反を修復し，バックトラックをしない
局所整合と局所探索 制約をすべて（大域的に）満たすのは困難 global 局所的に満たしながら大域に拡大する local 　局所整合アルゴリズム local consistency 局所的にバックトラック不要になるように不適切な値を事前に削除 backtrack-free 　局所探索アルゴリズム 　一般に，制約をすべて（大域的に）満たすのは計算量的に困難（NP困難：最悪のケースは指数オーダーの計算時間となる）なので，何らかの意味で局所的に制約を満たしながら，それを大域的に拡大する方法をとる． 　その方法は，基本的につぎの２つに大別できる． 　局所整合アルゴリズムは，制約グラフの局所的な制約違反を事前に解消するために，変数の領域から明らかに不適切な値を削除して，局所的にバックトラック不要になるように問題を変換する． 　局所探索アルゴリズムは，局所的に制約違反を修復し，バックトラックを（する必要があっても）しないで，すべての制約を満たすことを目指す．その結果，解があってもそれを発見する保証（完全性）は失われる．しかし，たとえ理論的には完全性があっても，事実上は実用的な時間内で解を発見できないような非常に難しい問題において，（いちかばちか）実用的な時間内で解を発見する可能性を追求する． local search 局所的に制約違反を修復し，バックトラックをしない repair

14 局所整合アルゴリズム (Local Consistency Algorithms)
1. アーク整合 arc consistency 2. 制約伝播 constraint propagation

15 制約ネットワークと制約グラフ x y z x z y 制約ネットワーク 制約グラフ 1 constraint network
constraint graph 1 x y z 許された値の組を辺で結ぶ 制約ネットワーク x z y 制約のある変数ノードを辺で結ぶ 制約グラフ 　X,D,Cからなる制約充足問題（CSP)をこのスライドのような図で表現した場合に，それを制約ネットワークと呼ぶことにしよう．すなわち，各変数の取りうる値をグラフのノードとし，変数はその領域の要素全体を包含するスーパーノードとして表現する．さらに，制約の記述によって，同時に値を取りうる要素どうしはグラフの辺で結ぶこととする． 　制約グラフとは，変数をノードとし，制約のある変数ノードを辺で結ぶことによって得られるグラフである．制約ネットワークよりも大まかにCSP全体の構造を把握するのに役立つ．

16 １．アーク整合(1) y x Dx Dy x=c は y にサポートをもたない ■ 値 x=a は y にサポートをもつ x=a のサポート
arc consistency ■ 値 x=a は y にサポートをもつ support y x x=a のサポート a c a' Dx Dy 　変数 x,y 間に制約 Cxy があるものとする．x への値の割当て x=a に対して，y=b が整合する（制約違反とならない）とき，y=b を「y における x=a のサポート」と呼ぶ．そのような y=b が y の領域に存在するとき，「値 x=a は y にサポートをもつ」という． 　このスライドの状況では，値 x=a および x=a' は y にサポートをもつ． 　しかし， x=c は y にサポートをもたないので，x=c がCSPの解に含まれることはあり得ない．yの値が何であっても制約違反となるからである．したがって，x=c を x の領域から削除してよい．その処理を行うのが，アーク整合アルゴリズムである． x=c は y にサポートをもたない (アーク整合アルゴリズム) Dx から値c を削除

17 アーク整合(2) y x Dx Dy ■ アーク (x, y) はアーク整合 している ＝すべての x=a が y にサポートをもつ a
arc consistent ＝すべての x=a が y にサポートをもつ y x a 　(x, y) が制約グラフのアーク（有向辺）であるとする． 　x の領域に含まれるすべての x=a が y にサポートをもつとき，「アーク (x, y)はアーク整合 している」という． 　アークには向きがあるので，アーク (x, y)はアーク整合 していることと，その逆向きのアーク(y, x)はアーク整合していることは別である．このスライドの状況では， (x, y)はアーク整合 しているが， (y, x) はアーク整合 していない． Dx Dy (y, x) はアーク整合 していない

18 アーク(x, y)の整合アルゴリズム boolean REVISE(x, y) { changed ← false; for each a in Dx { if (x=a が y にサポートをもたない) { Dx から a を除去する． changed ← true; } } return changed; } 値を１つでも除去したら true 　アーク(x, y)の整合アルゴリズムは，ここに示したとおりである．このアルゴリズムは，アーク (x,y)が与えられたとき，それがアーク整合するように，必要に応じて x の領域から値を削除する．戻り値は，値を１つでも除去したら true，１つも削除しなければ false である． 　手続きは，すでに学んだアーク整合の定義のとおりである．各 x=a について， x=a が y にサポートをもつかどうかを判定し，サポートをもたなければ x=a を領域から除去する．サポートをもてば，単にその x=a をスキップする． 　このアルゴリズムの計算量を考察しよう．ここでは，制約チェックの実行回数によって時間計算量を評価する．領域 Dx, Dy のサイズ（要素数）が高々 d だとしよう．たとえば，３色によるグラフ彩色問題では，色の数が３なので d=3 である． 　if 文の条件部でx=a が yにサポートをもつかどうかの判定には O(d)回の制約チェックが必要である．この if 文はO(d)回実行されるので，制約チェックの総回数はO(d^2) （ｄの２乗のオーダー）となる． 計算量（制約チェック回数） d は領域Dx,Dyの要素数の最大値

19 ＝すべてのアーク(x, y) がアーク整合 している
アーク整合(3) ■ 制約ネットワーク はアーク整合 している ＝すべてのアーク(x, y) がアーク整合 している ■ アーク整合アルゴリズム ＝アーク整合 していない制約ネットワークから 　　最小限の要素を削除してアーク整合させる． 　　空の領域が生じたら，ＣＳＰには解がない． x y z グラフ彩色（２色） アーク整合 していても解がないことがある 　さきほど学んだ「アーク整合する」の主語は「アーク」だったが，こんどは，主語が「制約ネットワーク」のときにも使える言葉として定義する． 　すべてのアーク(x, y) がアーク整合しているとき，「制約ネットワーク はアーク整合 している」という．アークには向きがあるので，制約グラフのそれぞれの無向辺 (x, y) ごとに，(x, y) と (y, x) のアークがあることに注意しよう． 　アーク整合アルゴリズム は，アーク整合していない制約ネットワークから最小限の要素を削除してアーク整合させる．その結果，空の領域が生じたら，ＣＳＰには解がないことがわかる． 　逆は，一般に成り立たない．ＣＳＰに解がなくても，空の領域が生じないことがあるからである．このスライドの２色のグラフ彩色問題はそのような例である．この例では，グラフに閉路が含まれていることに注意しよう．閉路が含まれていないときには，さきほどの「逆」が成り立つことを後に説明する． 制約グラフが閉路を含むとき

20 アーク整合アルゴリズムの動作例 Ｘ Ｘ 制約伝播 Ｘ Ｘ Ｘ Ｘ ① ③ constraint propagation ② ④ ⑤ ⑦ ⑥
　このスライドは，アーク整合アルゴリズムの動作例をアニメーションで示している． 　領域から要素を１つ削除したことの影響が，次々と隣接ノードに伝わっていく．これを制約伝播という． ⑦ Ｘ Ｘ ⑥

21 休憩

22 １か所だけ変化しても，全アークをスキャンしなおすので効率が悪い
アーク整合アルゴリズム　AC-1 AC-1(CSP G) { Q ← Gのすべての有向アークの集合. do { changed ← false; for each (x, y) in Q if ( REVISE(x, y) ) changed ← true; } while ( changed ); } 全アークをそれぞれ整合 　これは最も素朴なアーク整合アルゴリズムであり，ふつう，AC-1と呼ばれている． 　これはすべてのアーク (x, y) をスキャンしながら，すでに学んだ REVISE(x, y) によって，アークの整合をとる．すべてをスキャンしても全く変化がなかったら終了する． 　このアルゴリズムが非効率的なのは明らかである．スキャンのほとんどでは変化がなく，終わりの方で１つだけ変化があったとしよう．それでもこのアルゴリズムは，全アークをスキャンしなおすという不要な動作をしてしまう． １か所だけ変化しても，全アークをスキャンしなおすので効率が悪い

23 Qは First-In First-Out のキュー（待ち行列）
アーク整合アルゴリズム　AC-3 Qは First-In First-Out のキュー（待ち行列） AC-3(CSP G) { Q ← Gのすべての有向アークの集合. while ( Q が空でない ) { Qから先頭のアークを取り出し， (x, y) とする． if ( REVISE(x,y) ) for each z in y を除く xの隣接ノードのすべて｛ Qの末尾にアーク (z,x) を追加する． 　　　　｝ } } (x, y) の整合の結果，x の領域から要素が削除されたら 　x へ向かうすべての有向アーク (z, x) （ただし，ｚ≠ｙ）をＱに追加する． z x y 　AC-3 は，AC-1 の改良版で，１つの変更が周辺に影響を及ぼす制約伝播の様子を素直に表現したもので，じゅうぶんに実用的なアルゴリズムである．ポイントは，将来に整合性をチェックすべきアークを待ち行列Qに保持しておくことである． 　最初は，全アークをQに保持する．アルゴリズムのメインループは，Qからアーク (x, y) を取り出し，REVISE(x, y) で整合させる．もし，x の領域に変化がなければ，スキップ． 　もし，x の領域から値が削除されたなら，その影響を受ける可能性のあるアーク (z, x) をQに追加する．これによって，整合性をチェックする必要性のあるアークのみがQに保持され，順々に取り出されてはチェックされることになる． 　このアルゴリズムの計算量を考察してみよう．ここでは，制約チェックの回数によって時間計算量を評価する．このアルゴリズムで制約チェックが行われるのは，REVISE(x, y) の実行の中だけである．すでに学んだように，その計算量はO(d^2) なので，あとは，REVISEが最大で何回実行されるかを求めて，両者の掛け算をすればよい． 　REVISEの実行回数は，その直前に，Qからアークを取り出す回数と一致する．アルゴリズムが終了するときにはQは空なので，その回数は，Qにアークを追加する回数と一致する． 　これを求めよう．まず，初期設定のときに，Qに 2e 本のアークを追加している．（アークは向きが２通りあるので２倍している．）つぎに，特定のアーク (z, x) について考えると，これがQに追加されるのは高々 d 回である．なぜなら，x の領域（要素数は高々 d）から値を１個削除するときに限って追加されるからである．これは他の2e本のすべてのアークについても当てはまる． 　以上から，Qに追加されるアーク数は，高々 2e+d*2e = O(de) となる．したがって，制約チェックの総数は，O(d^d)*O(de) = O(d^3 e) となる．d が定数のときには，アーク数に比例した線形時間で制約ネットワーク全体のアーク整合が完了することになる． 計算量（制約チェック回数） Ｘ Ｘ d は領域の要素数の最大値 e は制約グラフのアーク数 高々 d 回Ｑに追加

24 バックトラック法で，変数の値を選択したときに， フォワードチェックのかわりに使う
アーク整合の利用法 前処理 バックトラック法で，変数の値を選択したときに， フォワードチェックのかわりに使う x y z この例では，ｚ の２つの値を削除して，失敗を早期に検知できる Ｘ Ｘ Ｘ Ｘ 制約グラフが木のときに， バックトラックなしで解を求める backtrack-free 　アーク整合は，単独で用いるより，他のアルゴリズムの補助として用いられることが多い．CSPは一般にＮＰ完全問題であるため，それを解くアルゴリズムの計算量は最悪で指数オーダーである．したがって，線形オーダーで処理の済むアーク整合は，効率を改善するための補助手段として手軽である． 　まず，いかなる制約充足アルゴリズムを使うにしても，アーク整合をその前処理に使うのが得策である．簡単な問題の場合には，この処理だけで空の領域が生じて「解なし」と判定できることもある． 　また，バックトラック法で，変数の値を選択したときに，フォワードチェックのかわりに使うこともできる．このスライドの図では，ｘの値を選択したときに，他のｘの値を領域から削除し，アーク整合アルゴリズムを実行した様子である．ｘ－ｚ間に直接の制約はないので，フォワードチェックだと，ｙの要素を削除できるが，ｚの要素は削除できない．しかし，フォワードチェックのかわりにアーク整合を使うと，zの値をすべて削除することができるので，ｘの値の選択が間違いであることがすぐにわかる． 　ただし，フォワードチェックは，アーク整合よりもさらに軽い処理なので，どちらが性能向上に寄与するかは一概に判断はできない． 　特別な場合として，制約グラフが木（閉路をもたないグラフ）のときには，アーク整合アルゴリズムを単独で用いて解が求められる場合がある．アーク整合の後に空の領域が生じていなければ，任意の変数を１つ選び，その領域から任意の値を１つ選ぶ．この変数を根とする木を作る感じで，選択された値のサポートを次々とたどっていけば，アーク整合の定義により，バックトラックなし(backtrack-free)で，O(e)の時間ですべての変数の値を制約違反なしで決定することができる．したがって，制約グラフが木であるＣＳＰはアーク数についての線形時間で解けることがわかる． 制約グラフが木であるＣＳＰは アーク数についての線形時間 で解くことができる

25 局所探索アルゴリズム (Local Search Algorithms)
1. 山登り法 hill climbing 2. 制約違反最小化 min-conflicts 3. 焼きなまし法 simulated annealing

26 反復改良の考え方 Q Q すべての変数に （ランダムに） 初期値を設定 改良をくりかえす （後戻りはしない） Q 一般には 完全性がない
iterateive improvement Q Q すべての変数に （ランダムに） 初期値を設定 改良をくりかえす （後戻りはしない） Q 　局所探索(local search)アルゴリズムに共通した考え方は，反復改良というものである．バックトラック法のように変数への割当てが部分的にしか決まっていない状態を考えるのではなく，制約違反があってもよいから，すべての変数に値を割り当てる． 　ふつうは，初期状態として，すべての変数にランダムな初期値を設定する． 　それを反復的に改良していくプロセスがそのアルゴリズムである．そのプロセスではバックトラックを行わない． 　そのため，特別なメカニズムを用意しない限りは，基本的に，反復改良アルゴリズムには完全性はない．すなわち，解があっても見つける保証はない．また，解がない場合でも，そのことを判定できず，限りなく反復が継続するか，または，それ以上の改良ができない状態で止まってしまう． 　しかし，非常に難しい問題で，かつ，必ず解が存在するような問題では，バックトラック法やそれを多少改善したものよりも効率よく解が求められることが多い． 一般には 完全性がない

27 z y x 評価関数 z=f(x,y) の山を登る 最適解 最適化問題 局所最適解 局所最適解からの 脱出
　反復的に「改良」するということは，数学的には，現在の状態（仮に (x, y) とする）の良さを表す評価関数 z =f(x, y) が与えられており，(x, y) を少しずつ変更しながら，z の最大値を探す問題となる． 　このような問題は一般に最適化問題と呼ばれている． 　このような問題を解くときの難しさは，局所最適解の存在である．これは最大値ではない，いわゆる，極大値のことで，局所的なピークを形成しているものである．その近傍では z の値が相対的に小さくなっているので， (x, y)を少し改善したくらいでは，zの値は現在より大きくならないので，改良が難しい状態になっている． 　局所最適解からいかに脱出するかが，アルゴリズム設計のポイントとなる． x 最適化問題

28 1. 山登り法 近傍の状態のうち評価値が最大の状態に進む． 決して下り坂を降りない． 近傍 neighborhood
hill climbing 近傍の状態のうち評価値が最大の状態に進む． 決して下り坂を降りない． 近傍 neighborhood 　山登り法は，（何らかの意味での）「近傍」の状態のうち評価値が最大の状態に進む．決して下り坂を降りることはしない．

29 山登り法の欠点 局所最適解で停止する． 対策：ランダムな初期状態から再出発する ( random restart) など．
それにもかかわらず 有効なことがある 山登り法の欠点 高原 局所最適 局所最適解で停止する． 　対策：ランダムな初期状態から再出発する 　　　　　( random restart) など． 高原では進むべき方向を判断できない． 　山登り法には，局所最適解で停止したり，評価値が一定の「高原」と呼ばれる広い範囲においては進むべき方向を判断できないというような欠点がある． 　しかし，それにもかかわらず，ランダム再出発（random restart）などと組み合わせて，非常に難しい問題の解を求められることがある．

30 山登り法により制約違反を反復的に改善する
2. ヒューリスティック修復法 heuristic repair 山登り法により制約違反を反復的に改善する 許される値の組 現在の状態 　ヒューリスティック修復法は，山登り法の一般的な考え方を制約充足問題に適用したもので，ただ１つの変数の値を変えることにより制約違反を反復的に改善する．

31 制約違反最小化ヒューリスティック 制約違反＝２ 制約違反＝２ 制約違反＝１ min-conflicts これを 選ぶ
変数は，ランダムに選ぶ． 値は，制約違反の数が最小のものを選ぶ． 　ヒューリスティック修復法で良く用いられるのが，制約違反最小化ヒューリスティック（min-conflicts）である． 　この方法は，変数を１つランダムに選び，その値として，制約違反の数が最小となるものを選ぶ．

32 制約違反最小化の実績 百万クイーン問題： 平均５０ｽﾃｯﾌﾟ ハッブル天体望遠鏡の観察スケジュール ３週間から１０分に短縮
百万クイーン問題：　平均５０ｽﾃｯﾌﾟ ハッブル天体望遠鏡の観察スケジュール ３週間から１０分に短縮 　簡単なヒューリスティックであるにもかかわらず，制約違反最小化ヒューリスティックの実績には，このスライドに書かれているように，目をみはるものがある．

33 Simulated Annealing (SA)
3. 焼きなまし法 Simulated Annealing (SA) 近傍の状態から次の状態をランダムに選ぶ． エネルギが減少するなら，必ずそこに進む． エネルギが増加するなら，温度に応じた確率でそこに進む． 最小化すべき関数をエネルギと呼ぶ エネルギ 局所解を ある確率で脱出できる 　焼きなまし法は，粒子の分子運動のような物理学のモデルからの類推によって設計されたアルゴリズムである．鋼などの固い金属を作るために，金属が溶解している状態から徐々に温度を冷やして固化させていく「焼きなまし（annealing）」という技術がある．それのシミュレーションから発想されたアルゴリズムなので，simulated annealing (SA) と呼ばれている． 　焼きなまし法の慣例では，評価関数による評価値は「エネルギ」と呼ばれ，これを最小化する最適化問題になっている． 　山登り法との違いは，まず，近傍の状態から１つをランダムに選ぶことである． 　さらに，選んだ状態へ進むかどうかは，現在の状態とのエネルギー差に依存する． 　エネルギが減少するときには，必ずそこに進む．これは山登り法の考え方に通じている． 　特徴的なのは，このアルゴリズムは温度と呼ばれるパラメータを持っており，次状態でエネルギが増加するなら，温度に応じた確率でそこに進むことである．これによって，局所最適解でストップすることなく，そこからの脱出をはかっている． 局所最適解 最適解

34 熱的なノイズによるランダムな揺れの表現 確率＝ 温度 ΔE 確率 大 エネルギ 増加分ΔE 小 温度 T 大 エネルギ 確率＝１
　 ΔE＞０のときには，物理学（熱力学）で知られている結果からの類推から定義された確率 exp(－ΔE／Ｔ)でその状態に進む．その状態に進まないときには，再度近傍から状態を選び直す． 　（ここで， exp(－ΔE／Ｔ)という式は，自然対数の底 e= の－ΔE／Ｔ乗という意味だが，eであることは重要ではなく，かわりに２を用いてもよい．） 　この遷移確率は，エネルギー差ΔEが小さいほど大きい．また，温度Tが大きいほど大きい．それは物理学では，温度が高いほど粒子の運動エネルギーが大きく，活発に運動しており，運動エネルギーを多少減少させることによって位置エネルギーの増大する方向に飛び跳ねる確率が大きいからである． 温度はじょじょに 下げていく

35 k T = schedule (k), k=1,2,… 冷却スケジュール：徐々に冷やしていく 線形冷却 指数冷却 T 対数冷却
　そこで，計算の初期段階では温度を高くしておき，時間とともに，温度を徐々に低くしていく制御がなされる．その具体的な方法を冷却スケジュールとしい，代表的にはこのスライドで示したようなものがある．よく使われるのは指数冷却である． k

36 温度T を十分ゆっくり下げるならば，確率１で大域的最適解を見つける．
焼きなまし法の最適性 温度T を十分ゆっくり下げるならば，確率１で大域的最適解を見つける． 対数冷却 Tk=c/log(k+1) はこの条件を満たすが，収束時間はO(n!)より長い． 　驚くべきことに，ある条件のもとで，焼きなまし法には最適性がある．つまり，大域的な最適解があれば，必ずそれを見つけることができる． 　その条件は，温度T を十分ゆっくり下げるということである．これは数学的にあいまいな表現だが，前のスライドで示した対数冷却はそのような条件を満たすことが知られている． 　しかし，残念なことに対数冷却は温度が十分に下がるまでの収束時間は指数関数的に長いものであり，実用的ではない．ふつうは，指数冷却の範囲でなるべくゆっくり冷却し，最適性をあきらめる． 温度はすごくゆっくり 下げていく