コストを考えた探索

探索戦略

  • 情報利用性 (informedness)
    各探索戦略において，現在の状態から目標状態に至るステップ数や経路コストに関する情報(知識)を用いるか用いないかを識別する特性．
    • 情報(知識)を用いない探索(uninformed search):
      目標状態と非目標状態を区別するだけで，しらみつぶし[盲目的]探索(blind search)とも呼ばれる．
      • 幅優先、深さ優先、反復深化
      • 盲目的、しらみつぶし、系統的(systematic)、網羅的(exhaustive)

    • 情報(知識)を用いる探索(informed search):
      探索経路を選定する場合に，現在の状態から目標状態に至るステップ数や経路コストに関する情報(知識)を用いる．これは発見的探索(heuristic search)とも呼ばれる．

  • 完全性 (completeness)
    解が一つ存在するときに，それを見つけることが保証されているかどうかという特性．

  • 最適性 (optimality)
    いくつかの異なる解があるとき，戦略は最高品質の解を見つけることが出来るかどうかという特性．

  • 時間計算量 (time complexity)
    解を見つけるためにどのくらい時間がかかるかという尺度．

  • 空間計算量 (space complexity)
    探索を行うためにどのくらいメモリを必要とするかという尺度．


水がめ

５リットルと８リットル入りの壷がある。 ５リットル入りの壷にちょうど２リットル入れるにはどうすればよいか。 

問題表現：（５リットルの壷の水の量、８リットルの壷の水の量）
初期状態：（５，０）または（０，８）
	　　[または（０，０）または（５，８）]
目標状態：（２、Ｘ）

操作：　　（Ｘ，Ｙ）⇒（５、Ｙ）、（Ｘ，Ｙ）⇒（Ｘ，８）
　　　　　（Ｘ，Ｙ）⇒（０、Ｙ）、（Ｘ，Ｙ）⇒（Ｘ，０）
　　　　　（Ｘ，Ｙ）⇒（Ｘ−Ｚ、Ｙ＋Ｚ＝８）
　　　　　（Ｘ，Ｙ）⇒（Ｘ＋Ｚ＝５、ＹーＺ）

（５，０）⇒（０，５）⇒（５，５）⇒（２，８）



５×ｍ−８×ｎ＝２
⇒
　５　　
１０　　　８	　（ｍ＝２、ｎ＝１）
１５　
２０　　１６
２５　　２４
３０　
３５　　３２
４０　　４０
４５　
５０　　４８	　（ｍ＝１０、ｎ＝６）
　：　　　：	　　：


８×ｎ−５×ｍ＝２となった後、５を空にし８に入れる
⇒
　８　　　５
１６　　１５
２４　　２０
３２　　３０	　（ｎ＝４、ｍ＝６）
４０　　４０
４８　　４５
５６　　５５
６４　　６０
７２　　７０	　（ｎ＝９、ｍ＝１４）
　：　　　：	　　：




残った水の量＝Ａ×ｍ−Ｂ×ｎ
Ａ＝ｋ×Ａ１、Ｂ＝ｋ×Ｂ１とすると
残った水の量＝ｋ（Ａ１×ｍ−Ｂ１×ｎ）、ｋの倍数

　　　　　　⇒（４、Ｘ）？	５ｍ−８ｎ⇒ｍ＝４、ｎ＝２
　　　　　　⇒（１、Ｘ）？	５ｍ−８ｎ⇒ｍ＝５、ｎ＝３

目標状態に到着できる必要条件：最大公約数の倍数
	なぜ最大公約数か？

	　　ｍ回
	┃　　　┃
	┃　ｋ　┃ これはどのような状態か？
	┗━━━┛


	┃　　　┃　　┃　Ａ　┃
	┃　ｋ　┃　　┣━━━┫
	┣━━━┫　　┃　Ａ　┃
	┃　　　┃　　┣━━━┫
	┃　Ｂ　┃　　┃　Ａ　┃
	┣━━━┫　　┣━━━┫
	：　　　：　　：　　　：
	：　　　：　　┣━━━┫
	┣━━━┫　　┃　Ａ　┃
	┃　　　┃　　┣━━━┫
	┃　Ｂ　┃　　┃　Ａ　┃
	┗━━━┛　　┗━━━┛
	  ｋ＋Ｂ×ｎ＝Ａ×ｍ

父と息子とボート

複数の息子の体重は１００ポンド、父の体重は２００ポンドである。 ２００ポンドまで乗れるボートが一隻ある。どのようにしてこのボートで 川を渡ればよいか。 

問題表現：
　（渡ってない父の数、渡ってない息子の数、渡ってない船の数）
初期状態：（１，ｎ，１）
目標状態：（０，０，０）

（１，ｎ，１）⇒（１，ｎ−２，０）
　　　　　　　⇒（１，ｎ−１，１）⇒（０，ｎ−１，０）
　　　　　　　⇒（０，ｎ，１）⇒…

ｎの条件：ｎ≧２

経路問題 

最短のコストでＡからＩに行くにはどう行ったらいいか？





Ａ─┬─Ｂ（５）───Ｅ（８）×
　　├─Ｃ（３）─┬─Ｅ（６）─┬─Ｆ（１０）×
　　│　　　　　　│　　　　　　└─Ｈ（８）───Ｉ（１１）
　　│　　　　　　├─Ｆ（７）─┬─Ｇ（１０）
　　│　　　　　　│　　　　　　├─Ｈ（１１）×
　　│　　　　　　│　　　　　　└─Ｉ（１３）×
　　│　　　　　　└─Ｈ（１１）×
　　└─Ｄ（４）─┬─Ｆ（９）×
　　　　　　　　　└─Ｇ（１０）─┬─Ｆ（１７）×
　　　　　　　　　　　　　　　　　└─Ｉ（１４）×
  • コスト関数：初期状態から現在の状態までのコストを計算し、最小のコストを選択する。
  • 一般的には（開放系では）最小のコストを選択することはできない。
    　　　閉鎖系 vs. 開放系
  • 最短の経路が必ずしも最小コストではない。 

【最小コスト探索】

stack		S=[a,b,c]
		push_down(x,[a,b,c])=[x,a,b,c]
		pop_up([x,a,b,c])=x

	次に枝を伸ばすべきノードの集合
	各ノードはコストを属性としてもっており、
	スタック中のノードはコストの昇順に並べられてる。

past_list	L=[a,b,c]
		append(x,[a,b,c])=[x,a,b,c]
		car([x,a,b,c])=x, cdr([x,a,b,c])=[a,b,c], 
		tail([a,b,c])=c, x∈L

	過去に通ったノードの集合で、最小コストを記録する
	同じノードになったとき、
	展開する価値があるかどうか判断する

g(n)		nまでのコスト
g(n,n')		g(n)+(nからn'までのコスト)


	スタック　	順序組(タプル)	リスト
	┃　ａ　┃	　　┃　　	┏┻┓
	┃　ｂ　┃	┏━╋━┓	ａ┏┻┓
	┃　ｃ　┃	┃　┃　┃	　ｂ┏┻┓
	┗━━━┛	ａ　ｂ　ｃ	　　ｃ　[]


cost_mini_search(init,goal)=>cost:

	stack:=[];
	past_list:=[];
	stack:=push_down(init,stack);
	g(init):=0;

loop:	if stack=[] then goto fail;
	n:=pop_up(stack); stack:=cdr(stack);
	if n=goal then goto success;
	past_list:=append(n,past_list);

	for all ni:=next(n);
		g(n,ni):=g(n)+cost(n,ni);
	if ¬(ni∈past_list) 
		then do;
		     stack:=push_down(ni,stack);
		     g(ni):=g(n,ni);
		     od;
		else do;
		     if g(n,ni)＜g(ni)
			then g(ni):=g(n,ni);
	     	     od;
	sort stack increasingly by g(n).
	goto loop;

success:	cost:=g(n);

迷路問題 

　　０　１　２　３　４　５　６
　┏━━━━━━━━━┳━┳━┓
０　　　　　　　　　　┃　┃　　
　┃　┏━━━━━━━┛　┃　┃
１┃　┃　　　　　　　　　┃　┃
　┃　┃　━━┓　━━━━┫　┃
２┃　┃　　　┃　　　　　┃　┃
　┃　┗━━　┃　━━┳━┫　┃
３┃　　　　　┃　　　┃　┃　┃
　┃　┏━━━┛　┃　┃　┃　┃
４┃　┃　　　　　┃　　　　　┃
　┗━┻━━━━━┻━━━━━┛

初期状態 (0,0)　⇒　目標 (6,0)

予測コストの評価関数 h(x,y)=|x-6|+|y-0|=y-x+6

この関数は妥当か？

初期状態 (0,0)⇒副目標 (6,4)⇒目標 (6,0)
初期状態 (0,0)⇒副目標 (3,3)⇒副目標 (6,4)⇒目標 (6,0)
  • 目標：評価値の最小値
    　　　単調減少する評価関数が理想的

  • 現実：複数の極小値 　　　評価値が増大する道の選択

  • 評価関数：ヒュ−リスティクス、人の経験的知識


８パズルの評価関数

  • 例題 

【初期状態】　　　【目標状態】
┏━┳━┳━┓　　┏━┳━┳━┓
┃１┃５┃２┃　　┃１┃２┃３┃
┣━╋━╋━┫　　┣━╋━╋━┫
┃４┃　┃３┃　　┃４┃５┃６┃
┣━╋━╋━┫　　┣━╋━╋━┫
┃７┃８┃６┃　　┃７┃８┃　┃
┗━┻━┻━┛　　┗━┻━┻━┛

【問題表現】




 x1  x2  x3 


x4x5x6


x7x8x9



[x1,x2,x3,x4,x5,x6,x7,x8,x9]

【操作】

[S,x2,x3,x4,x5,x6,x7,x8,x9]→[x2,S,x3,x4,x5,x6,x7,x8,x9]
			　 →[x4,x2,x3,S,x5,x6,x7,x8,x9]

[x1,S,x3,x4,x5,x6,x7,x8,x9]→[S,x1,x3,x4,x5,x6,x7,x8,x9]
			　 →[x1,x3,S,x4,x5,x6,x7,x8,x9]
			　 →[x1,x5,x3,x4,S,x6,x7,x8,x9]

[x1,x2,x3,x4,S,x6,x7,x8,x9]→[x1,S,x3,x4,x2,x6,x7,x8,x9]
			　 →[x1,x2,x3,S,x4,x6,x7,x8,x9]
			　 →[x1,x2,x3,x4,x6,S,x7,x8,x9]
			　 →[x1,x2,x3,x8,x6,x6,x7,S,x9]
  • 盲目的探索

  • 順序(位置)による評価関数＆探索木


    
評価値が不適切な例
┏━┳━┳━┓
┃　┃２┃３┃
┣━╋━╋━┫
┃４┃５┃６┃
┣━╋━╋━┫
┃７┃８┃１┃
┗━┻━┻━┛

  • 移動量による評価関数＆探索木

  • 山登り法
    各ノードで選択可能なノードの評価関数の最小のものを選ぶ。


    　　　　　　

    {S(0,6)}→{B(3,3),A(2,5)}→{C(4,2),D(7,7)}→{G(6,0),E(7,5)}

    {S(0,6)}→{A(2,5),B(3,6)}→{C(5,2)}→{G(7,0),E(8,5)}

    駄目だった場合
    • 初期状態に戻り他の枝を探す
    • 直前の非選択枝を捜す（バックトラック）

　　　 山登り法：
{S(0,7)}
→{B(2,5),A(3,7)}
→{C(3,4),D(4,5)}
→{E(4,1),F(8,2)}
→{A(5,7)}
→{C(8,4)}
→…
最良優先探索：選択されなかった節点を残し、一番良い節点を選択する
{S(0,7)}
→{B(2,5),A(3,7)}
→{C(3,4),D(4,5),A(3,7)}
→{E(4,1),F(8,2),D(4,5),A(3,7)}
→{F(8,2),D(4,5),A(3,7)}　×A(5,7)
→{G(10,0),D(4,5),A(3,7)}


A*アルゴリズム

  • A アルゴリズム

    • 初期状態から現在地点までのコスト関数 g(p)
    • 現在地点から目標までの評価関数 h(p)

    の両方考える：f(p)=g(p)+h(p)

    g と h が各ポイントで正確にわかっていたら必ず目標まで最適経路をたどることができる。 しかし一般的には g と h は推定値 g',h' であるので試行錯誤の探索が必要となる。 
    
　　　f'(p)=g'(p)+h'(p)
    A アルゴリズムは目標までの経路を探索することは保証されているが、 それが最適解である保証はない。

  • A* アルゴリズム 

    　　　　h'=8　　　　　　　　　　　　　　h'=7
    　　　　初期　　　    　　　    　　　　初期　　　    
 　g=3┏━━┻━━┓g=5　 　　　 　g=3┏━━┻━━┓g=5　 
    　┃　　　　　┃　    　　　    　┃　　　　　┃　    
h'=4　Ａ　　　　　Ｂ　h'=5　　　h'=5　Ａ　　　　　Ｂ　h'=2
    　┃　　　　　┃　    　　　    　┃　　　　　┃　    
 　g=6┗━━┳━━┛g=3　 　　　 　g=6┗━━┳━━┛g=3　 
    　　　　目標　　　    　　　    　　　　目標　　　    

ＡとＢのどちらを経由すべきか？
各地点における推定評価値 h'(p) と評価値 h(p) の間に

h'(p)≦h(p)

が成り立つならば、A*アルゴリズムという。
探索グラフが無限の場合でも、出発点から目標までの経路が存在すれば、 A*アルゴリズムは最適解を与える。

h"(p)＜h'(p)≦h(p)

ならば h' は h" より知識が多いという。 (h" の方が探索範囲が広い。)