凡例　 ○………箇条書きの先頭に使われる白丸
　　　 ●………箇条書きの先頭に使われる黒丸
　　　<   >……板書における黄色の文字
　　　[   ]……板書における下線が引かれた文字
　　　+
　　　|- , +-…中かっこ("}"のこと)
　　　+    +


2.2　AIで対象とする問題
　○ゲームやパズル
　　1)AIの古典的問題…どのように解くか？
　　　　　　　　　　　最適解(正解)を導き出す
　　　　　　　　　　　　⇒全ての可能性をしらみつぶしに調べる
　　　　　　　　　　　　　　　<　 ↓　 >
　　　　　　　　　　　　　　　< 探索(search) >
　　2)現在の研究テーマ
　　　○いかに[効率よく]解くか？
　　　　　　　人間のやり方のように←→全てを調べるのは計算量から
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　不可能(クラスN[P])
　　　○パズルの創作　　　　　　　　　　　　　　　　　　　　 　　　　　 ↓
　　　　　ex.詰め将棋の問題作成　　　　　　　　　　　　　　　　　　多項式時間
　　　　　


P.26  2.3　問題の定式化法
　2.3.1　状態空間法
　　　状態とオペレータによる問題の定式化
　　　　　1)状態…………対象とする問題の中で[とりうる]値
　　　　　　　　　　　　　　　　 (ex.パズルのルールで許された)
　　　　　2)オペレータ…状態間のとりうる遷移を区別する/表す操作/記号
　　　1.状態空間集合
　　　　Q1. ８パズルのとりうる状態の数を全て求めよ。
　　　　　　　　9!＝3.6×10^5　 16!＝2.0×10^13
　　　　　　　　　　　　　　　　　 ＝20T =========⇒メモリ、HD上ともに全てを展開
　　　　　　　　　　　　　　　　　　　　　　　　　　するのは不可能
　　　2.オペレータ集合→P.28〜29　　　　　　+
　　　　　オペレータ…状態を変化させるもの　|-ゲームのルール(コマの動かし方)
　　　3.状態遷移関数　　　　　　　　　　　　+
　　　4.初期状態　+
　　　5.最終状態　+-ゲームの問題

　　　○状態空間法による解の求め方 < (古典的プランニング) >
　　　　1)ある状態から(出発して)適用可能なオペレータに適用して遷移可能な状態を次々と求めていく
　　　　2)[初期状態]から出発し、[最終状態に]遷移すれば終了。
　　　　3)初期状態から出発し、最終状態に至る< オペレータ系列 >が求められる解である。
　　　○状態空間は
　　　　状態をノード、オペレータをアークとする[有効]状態遷移グラフで表される。


＜来来週までの課題＞

　　　Q2. テキストP.30 図2.6の８パズルの木を[Ｑi]から2レベル展開せよ。
　　　　　　　　　　　　　　　　　　　　　　　`→レベル0
　　　　　但し、レベルnとはＱiからオペレータをn回適用した状態を表す。

　　　Q3. レベル2で(重複を除いた/含む)状態の数はいくらか？

　　 (Q4. レベルnで(重複を除いた/含む)状態の数はいくらかを見積もりたい)
　　 (　　レベルk→k+1の場合の状態の数の増え方を説明せよ。            )

　　　Q5. Q2.で求めた木を用いてＱiから2レベル先までの状態遷移グラフを求めよ。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　」
-------------------------------------------------------------------------