null

現在このイメージを表示できません。
認知科学
思考のコンピュータシミュレーション（２）
２０１６年１月２１日（木）
ヒューリスティクス
(heuristics)
どのようにしてよいかわからない場合に，うまくゆくという保
証はないが，以前の経験に頼って役に立ちそうなことをやっ
てみるという方略．将棋や碁，チェスなどの問題解決に多い．
人間は複雑な問題解決場面においては，しばしば
ヒューリスティクスを暗黙に用いている．
ヒューリスティクスによって生じる認識上の偏りを認知
バイアスと呼ぶ．
日常の多くの問題は不良定義問題（解法が存在しな
い）が大半なため，ヒューリスティクスが有効な問題解
決の方法になることが多い．
アルゴリズム
(algorithm)
実行すれば必ず回答に到達する手続き方略
初期状態，目標状態，操作子が明確にされている良定
義問題では有効に働く．
８４，６０，４８の最大公約数を求めよ．
２｜８４６０４８
２｜４２３０２４
３｜２１１５１２
ーーーーーーーーー
７
５
４
解決アルゴリズム
1. 共通な因数で割っていって，
割り切れなくなるまで続ける．
2. 式に出てきたこれらの数字を
全部掛ける．
２ × ２ × ３＝１２
思考と問題空間の探索
1. 思考（≠白昼夢）とは，知識を系統立てて問題を解決す
る認知的過程である．
2. 系統立てて処理すること
→情報処理過程として捉えることが可能
3. 問題解決の手掛かりとなる使える情報（知識）を利用し
て，スタート地点からゴール地点まで空間を系統立て
て移動すること
→探索
ヒューリスティクスが使われる状況
問題の解法があらかじめ定まっていない場合．
→世の中のほとんどは正しい解があるとは言えない．
複数の解法が存在し，いずれの方法でもゴールに到達
する可能性がある場合（ゴールに到達できるとは限ら
ない）．
人間の場合，過去の成功事例を踏襲することが多い．
保守主義もこのようなバイアスの具体例といえるかも．
ヒューリスティック探索
探索すべき状態空間を削減する方法の１つに，そ
の問題に関するさまざまなこの情報（知識）をうまく
利用する方法を考える．
展開した子の状態をなんらかの評価基準で優先順
位をつけ，その順序で調べていくことで探索効率を
向上させることができる．
場合によっては解の探索に失敗する可能性がある
ものの，多くの場合探索効率を向上させることが期
待できる．
探索における経験的知識を表現するためのヒュー
リスティック関数を利用する．
山登り法
(hill climbing)
勾配降下法
(gradient
descent)
1.
山頂（谷底）を目指す登山（谷くだり？）をイメージ．
2.
ある地点に立ったとき，次の一歩はその周囲で一番
高い（低い）地点に踏み出す．
3.
これを繰り返すと，次の一歩が選択できない地点に至
る→山頂（谷底）に到達
探索の方法
８
ヒューリスティック関数
→山頂との高さの差
局所的最小値(local minima)
に陥る可能性がある
６
５
高原(plateau)のような状態に
なると，進む方向を見失ってし
まう
７
４
３
４
local minima
plateau
８
５
例題：迷路問題
1. 迷路の交差点を自然数の座標の組（ｘ，ｙ）で表す
ことにする．
P →
↓
入口 (s)
2. 交差点ｑ＝（ｘ，ｙ）と出口ｇ＝（ａ，ｂ）の距離
ｄ（ｑ，ｇ）を次のように定義する．
ｄ（ｑ，ｇ）＝｜ａーｘ｜＋｜ｂ－ｙ｜
出口 (g)
3. このとき経験的知識として
「ある状態ｑを展開したとき，距離ｄ（ｑ，ｇ）が最小
となる子の状態ｑについてのみ，次の展開を行う」
を用いる．
上の図の迷路に対して，入口sか
ら迷路に入った人間Pが出口gに
到達するための解を求めよ．
s
4. このときのヒューリスティック関数は２で定義した
式を用いる．
（ｓ→１→２→５→８→ｇ），（ｓ→１→４→８→ｇ）
状態１を展開した状態２と状態４は同じヒューリスティック関数をもつので，どちらを選ぶかはランダムに決める．
1
2
3
4
5
6
8
g
7
最良優先探索
(best first search)
山登り法が第３ステップで，{7,8}か
ら最小値を選択する．
８
最良優先探索は未探索の前節点
集合{6,7,8}から最小値を選択する．
適切なヒューリスティック関数を定
めることが可能なら，方向性を有す
る探索なので，ブラインド探索より
効率よく目標状態を探索できる．
未探索節点の格納なのに多くのメ
モリ量が必要となってしまう．
６
９
５
６
３
７
２
８
局所的最小値からの脱出
山登り法のように，局所的最小値に
至っても，それを回避し，目標状態に
向かうことができる．
しかし，得られた経路が最良の経路であ
ることは保証されない．
ヒューリスティック関数がうまく定義できれ
ば，多くの場合，妥当な精度の解を高速
で探索可能．
局所的最小値
ｙ
３
２
４
３
ｇ
２
１
３
２
[1,1]
ｓ
過去の経路の情報を記憶しているた
め，ある状態において次に移動すべ
き状態を探すときに，そのときにはあ
まり有望に思えなかった状態も選択
の対象とする．
[4,3]
ｘ
○の中は評価関数（ヒューリス
ティック関数） f(n) の値．ただし，
n の座標を[x,y]とすると，
f(n) = (4-x) + (3-y)
制約条件を用いた探索
の効率化
解の探索に制約を加える手法
→解の探索範囲を減らすことで探索効率を向上
問題の表現において定義される状態を「許容状態」「禁止状
態」に分離する．
探索の過程で禁止状態に移る作用素は適用しない条件を設
ける．
弱く定義
探索しなければならない領域は増加するた
め探索効率は低下する．
「禁止状態」を定義す
る「制約条件」
トレードオフ関係
強く定義
探索しなければならない領域は減少するが，
「禁止状態」の中に目標状態が含まれてし
まい，解が見つからなくなる可能性が生じる．
制約条件とバックトラックを用いた
探索
宣教師と人喰い人種問題（ＭＣ問題）
３人の宣教師(missionaries)と３人の人喰い人種(cannibals)
が，左岸から右岸に２人乗りのボートで川を渡ろうとしている．
川の両岸，あるいはボートの上で宣教師の数より人喰い人種
の数が多くなったとき，宣教師は人喰い人種に食べられてしま
うものとする．このとき宣教師が食べられてしまうことなく，
ボートを使って川を渡る手順を考えよ．
現
現
現
現
現
現
ＭＣ問題の状態空間の表現
定義
時刻ｔに，左岸Ｌにいる宣教師の数：
Ｍ（ｔ）
人喰い人種の数：Ｃ（ｔ）
時刻ｔでボートが右岸Ｒに接岸している状態：Ｄ（ｔ）＝Ｒ
左岸Ｌに接岸している状態：Ｄ（ｔ）＝Ｌ
ボートが岸に着いたときすべての人間は一旦ボートを降りる．
状態空間の表現
状態ｓ（ｔ）＝＜Ｍ（ｔ），Ｃ（ｔ），Ｄ（ｔ）＞
ただし，０≦Ｍ（ｔ）≦３，０≦Ｃ（ｔ）≦３
｜Ｍ（ｔ）－Ｍ（ｔ＋１）｜＋｜Ｃ（ｔ）－Ｃ（ｔ＋１）｜≦２
初期状態ｓ０＝＜３，３，Ｌ＞
目標状態ｓｇ＝＜０，０，Ｒ＞
ＭＣ問題の禁止状態と
許容状態
禁止状態（右岸か左岸で人喰い人種が宣教師の数より多くな
る状態のすべて）
ＳＦ＝｛＜Ｍ（ｔ），Ｃ（ｔ），Ｄ（ｔ）＞｜Ｍ（ｔ）＜Ｃ（ｔ）ま
たは３－Ｍ（ｔ）＜３－Ｃ（ｔ）｝
SF={<2,3,D>, <1,3,D>, <1,2,D>, <2,1,D>, <2,0,D>, <1,0,D>}
ただし，ＤはＲまたはＬ．
全状態集合をＳで表し，許容状態をＳＧで表す
と，
ＳＧ＝Ｓ－ＳＦ
SG={<0,0,R>, <0,3,D>, <0,2,D>, <0,1,D>, <1,1,D>, <2,2,D>,
<3,0,D>, <3,1,D>, <3,2,D>, <3,3,L>}
解の探索
縦型探索を用いる．
禁止状態を行き止まり状態と見なして，バックト
ラック（前の状態に戻る）する．
適用する作用素（N1～N10の１０個）
1. if ((D(t)=L) && (M(t)≧1) then
M(t+1)←M(t)-1, C(t+1)←C(t), D(t+1)←R
2. if ((D(t)=L) && (M(t)≧2) then
M(t+1)←M(t)-2, C(t+1)←C(t), D(t+1)←R
3. if ((D(t)=L) && (C(t)≧1) then
M(t+1)←M(t), C(t+1)←C(t)-1, D(t+1)←R
縦型（深さ優先）探索 (DFS)
初期状態から離れた状態を
優先的に調べる探索方法．
行き止まり状態になると，解
を探索するために，それまで
の経路を次の探索を再開で
きる状態まで後戻りする（バッ
クトラック）．
バックトラックを効率よく制御
するために，スタックが用いら
れる．
１
２
３
５
４
６
７
８
９
１０
１１
課題（１）
N4～N10を記述せよ
ヒント
N5
if ((D(t)=L) && (M(t)≧1) && (C(t)≧1) then
M(t+1)←M(t)-1, C(t+1)←C(t)-1, D(t+1)←R
N10
if ((D(t)=R) && (M(t)≦2) && (C(t)≦2) then
M(t+1)←M(t)+1, C(t+1)←C(t)+1, D(t+1)←L
許容状態を満たす条件と
移動方法
M(t)≧C(t) かつ 3-M(t)≧3-C(t) を満たす状態
⇒任意のｔに対して，
M(t)=0 または M(t)=3 または M(t)=C(t)
M(t)=3 or M(t)=0
→ 宣教師はボートに乗らない，または
M(t+1)=C(t+1) になるように移動させる．
M(t)=C(t)
→ M(t+1)=3 または M(t+1)=0 になる移動を行う，
あるいは，宣教師と人喰い人種を１人ずつ移動させる．
課題（２）
ＭＣ問題の状態空間を生成し，完成させよ．
<2,3,R>
<3,3,L>
<2,2,R>
<2,1,L>
<2,3,R>
<3,1,R>
<3,2,L>
<3,0,R>
<3,2,R>
<1,3,R>
<3,1,L>
来週の予定（最終日）
「創造性」について
授業のまとめ
最終課題レポートについて
アンケート

Download Report