-------------------------------------------------------------
9/6(水)はれ、ノート:不殿（松尾研）

・9月以降の講義予定
	１章当たり2〜3回

・3章　探索（serch）pp.36〜43

1.今日のポイント
	Q.1 "サーチ"とは何か？	…何をするための概念（考え方）か？
				　どう役に立つのか？
	　　　〃　という考え方のイメージをつかむ。
	Q.2 どうやってプログラムで実現するのか？　…サーチのアルゴリズム(*3)

	例　RPGの基本要素（日本の一本道RPG）
		1) 迷路探索	…必要なアイテム・フラグ・ボスキャラ・
						終了、脱出方法を見つける
		2) フラグ立て	…フラグを立てると次のイベント（シナリオ）へ進む
		3) レベル上げ	…ボスキャラに勝てる確率が上がる

		1),2)で"サーチ"の概念が有効
			移動可能な範囲(世界)の中で(*1)
			　いかに無駄	…同じ所を２度探す		┐
			　　　見落とし	…まだ探してない(*2)場所がある	┘(*4)
					なく、探し物(ex.石板) を見つけるか？
	Q.1では"サーチ"とは何か？ P36.L3
	　状態空間(*1)の全ての状態(*2)を予め決められた順序(*3)に従い，
		系統的(*4)に探索（訪問）していく。

		・さがし物	…目標状態(goal state)
		・場所		…状態(グラフのノード)
		・移動		…遷移(　〃　のアーク)
		・世界		…状態（状態遷移グラフ）→ see P37 図3.1

3.1 ブラインド探索
	　全ての状態をある順序に従って網羅的（しらみつぶし）に訪れる。

3.1.1 たて型サーチ
	迷路サーチでの左手法	　壁沿い行動(wall following)→P98,P101, 図5.18

  問１　図3.1について P.38 DFS のアルゴリズムを用いて、
	リストL1,L2の内容の変化をstepごとに求めよ。

	|ループ回数| step  |    　L1	|  　L2    |	初期値φ（空集合）
	|　　０　　|   1   |   　[S]	|   φ=[]  |
	|　　　　　|   2   |     〃	|    〃    |	 ↑
	|　　　　　|   3   |    φ=[]	|  　[S]   |	先頭
	|　　　　　|   4   |     〃	|    〃    |
	|　　　　　|   5   |  　[a,b]	|    〃    |
	|　　１　　|   2   |     〃	|    〃    |
	|　　　　　|   3   |    　[b]	| 　[a,S]  |
	|　　　　　|   4   |     〃	|    〃    |
	|　　　　　|   5   |　[c,d,b]	|    〃    |

		
  問２　3.1.2の横型サーチについて問１と同じ表を作成せよ。

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

---

図，縦型サーチの順序

---

yamaguch@info.nara-k.ac.jp

---

人工知能概論 2000 のページへ戻る (back to AI lecture 2000 index page)

---

山口の担当講義のページへ戻る (back to tomo's lectures page)

---

Tomo's Top Page へ戻る