-------------------------------------------------------------


9/13 （水）
今日のポイント
１．横型サーチと縦型サーチとのアルゴリズムの比較
２．横型サーチと縦型サーチの比較　→ 3.1.3　縦型　vs 横型
３．3.1.4　反復深化サーチ
４．ヒューリスティク（サーチ）とは？ → 9/20 の講義内容

3.1.2　横型サーチ
	横型サーチのアルゴリズム
	・縦型サーチとの違い
	　　step5 展開して加える子節点のリストL1への追加の位置
		if 先頭に加える　→縦型　（LIFO → stack)
		   末尾に加える　→横型　（FIFO → quaue)
	Q.1  リストL1,L2に名前をつけるとしたら？
	　   リストL1,L2の役割はなにか？

3.1.3　縦型　vs 横型
	１．計算量の比較（p41)
	　（１）空間計算量　（領域　or メモリ）
	　　　アルゴリズムが用いるメモリの最大値
　	　	max L1・・・リストL1の最大値　←こちらに注目
		max L2・・・全ノード数（各ノードを１度ずつ展開するので）
		　縦型のＬ１・・・（深さ）×（各深さでの展開ノード数−１）＋１
		　横型のＬ１・・・ｂ・exp(d-1)
          （２）時間計算量
　　　　　　　各アルゴリズムがサーチする（総）ノード数
	　　　全サーチ木が深さｄ、幅ｂだとすると O(b・exp(d)) (縦型＝横型）
　　　　　　　　注）以上の話は木を探索する場合。
　　　　　　　　　　グラフを探索する場合は同一ノードを複数回展開する場合が生じる。
	　（３）縦型と横型との比較
	　　　ex.ネットサーフィン/ネット（で）検索
	　　　縦型・・・メモリ量が少なくてよい
　			どんどん深みにはまるリスクあり
	　　　横型・・・メモリ量大
　　　　　　　　　　　　深さより（調べる）幅の広さを重視
	　　　初心者は縦型, 
	　　　エキスパートは横型の傾向 

3.1.4 反復深化サーチ
	特徴）・ブラインドサーチの１つ→最終的には全検索
　　　　　　　・縦型と横型との組み合わせサーチ
　　　　　　　　　縦型の調べる深さ(→cut offパラメータ）を制限
　　　　　　　　　その範囲で全探索を行う
	　case   cut off=1　→横型サーチ
　　　　　　　　 cut off=∞　→縦型サーチ
　　　　　　　　 cut off=n>1 →サーチ木のうち深さｎまでを縦型に全探索

§課題
　　p.37 図３．１のサーチ木に対してp.42のアルゴリズムを用いて
    リストＬ１，Ｌ２,cut offの変化をstepごとに表に書け。（cut off=2→3になるまで）
-------------------------------------------------------------------------