-------------------------------------------------------------
２００１年　７月１１日 (水) 講義ノート (by 山口研  中尾友圭子)

3.2 ヒューリスティックサーチ(その１)，heuristic
	配布資料 2000,9/20 AI		→成功経験に基づく知識

	h(x)：ゴールと現状態とのキョリ(近さ)を見積もる関数
	      小さい程ゴールに近い

3.2.1 山登り法(hill climbing)
	・h1(x):山頂(ゴール)と現地点との高さの差
	・h2(x):ゴール地点と	〃      直線距離

     Q.なぜh(x)は’見積もり’(estimation)なのか？
	ゴールへ至るpathの正確なキョリ／コスト(cost)ではなく

     Q2.山登り法はブラインドサーチでいうとたて型，よこ型？
	その理由は？
		たて型，(step5で未展開ノードリストL1に
			展開する)ノードを一つ入れているから(by竹村)

3.2.2 best first search(と山登り法との比較)
	＜ちがい＞ step5 1)次に展開するノードのL1への加え方
			 2)	      〃       選び方

		山登り法			  best first search
	1)展開した子ノード集合nこのうち		展開した全てのノード
	  min(h(x))となる一つのノード
	2)		〃                      未展開ノード集合L1を
						h(x)でソートした先頭

     Q4. p.47図3.4で各サーチ法で次に展開されるノードを
	マークせよ

     Q5.best first search法の特徴は？
	・横型，全サーチ+h(x)
	・ 〃 なのでたて型に比べると多くのメモリが必要

3.2.3 A*アルゴリズム(A star)
	pathのコストの評価関数(ノードnにおける)
		f'(n)=g'(n)+h'(x)
			↓   ↓
			↓   nからゴールまでのpathコストの見積もり
		      スタートからnまでのpathコスト

	h'(x)≦h(x):過小評価
		    真の値より小さめに見積もる