人工知能概論 2000 Introduction to Artificial Intelligence 2000 |
2000, Sep. 5th, updated
凡例 ○………箇条書きの先頭に使われる白丸 ●………箇条書きの先頭に使われる黒丸 < >……板書における黄色の文字 [ ]……板書における下線が引かれた文字 + |- , +-…中かっこ("}"のこと) + + 2.2 AIで対象とする問題 ○ゲームやパズル 1)AIの古典的問題…どのように解くか? 最適解(正解)を導き出す ⇒全ての可能性をしらみつぶしに調べる < ↓ > < 探索(search) > 2)現在の研究テーマ ○いかに[効率よく]解くか? 人間のやり方のように←→全てを調べるのは計算量から 不可能(クラスN[P]) ○パズルの創作 ↓ ex.詰め将棋の問題作成 多項式時間 P.26 2.3 問題の定式化法 2.3.1 状態空間法 状態とオペレータによる問題の定式化 1)状態…………対象とする問題の中で[とりうる]値 (ex.パズルのルールで許された) 2)オペレータ…状態間のとりうる遷移を区別する/表す操作/記号 1.状態空間集合 Q1. 8パズルのとりうる状態の数を全て求めよ。 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の8パズルの木を[Qi]から2レベル展開せよ。 `→レベル0 但し、レベルnとはQiからオペレータをn回適用した状態を表す。 Q3. レベル2で(重複を除いた/含む)状態の数はいくらか? (Q4. レベルnで(重複を除いた/含む)状態の数はいくらかを見積もりたい) ( レベルk→k+1の場合の状態の数の増え方を説明せよ。 ) Q5. Q2.で求めた木を用いてQiから2レベル先までの状態遷移グラフを求めよ。 」 -------------------------------------------------------------------------