知能工学　提出用ノート

電子情報工学専攻　　京兼研究室　　A２１０番　中村　昌樹

（*印については、黄色で書かれたものとして表示）
（図についての使用ソフトはVisio technical 4.1J で作成したものであり
その図をビットマップ形式にし貼り付けたもの）


１．適切な表現とは何か？

（１）４近傍が隣り合う２つのマス目
　　（平面において上下左右）

（２）ｎ×ｎの正方形のマス目平面に対し
　　（１）の制約をどう｛反映｝させるか？　
　　　　　　　　　　　　｛表現｝
ボードに市松模様と付けてみる
→では、何に注目するのか？
　それぞれの色（黒・白）のマス目の数を数えてみる。

Ｐ.２６　
２．３　問題の定式化法とは？

形式的な表現と操作の繰り返しで解が求まるような形にすること

（例１）８パズル
　　　　１〜８のタイルと１つの空白を計９個のマス目の置き方を
　　　　いろいろ変えて遊ぶ道具
　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　

（１）状態　：　パズルの中のタイルと空白のそれぞれの位置の組み合わせ
　　　*Ｑｔ　　　　９！=　９×８×７×６×５×４×３×２×１　
　
（２）オペレータ　：　パズルのルールに従って状態間の遷移を行う操作
　　　*Ｑｋ　　　　　　　　　　　　　　　　　　　　　　（コマの移動）　　
　
　　８パズルの場合　空白を（４近傍で）隣り合う
　　　　　　　　　　　　　コマの移動が可能

　　*ｎot　どのコマを動かすのか？
　　*ｂuｔ　空白が４近傍のどちらかへ動くのか？
　　　　⇒オペレータの数は４通り（P.P２８-２９）　　　　　　　　

（３）状態空間・・・・問題のすべての状態とそれらの間の可能な
　　　　　　　　　　　遷移を表した*状態遷移グラフ

　　状態遷移関数            　¢→  Q×０→Q
                                      　　　Qi×Qｇ→Qj

　　　Qではパズルを解くとは？
　　　ある初期状態Qiから目標状態Qｇへ至る。
　　　（状態遷移系列を表す）オペレータ系列を求めること。


*GIVEN　：　状態空間法　＜Q、０、¢、Qi、Qｇ＞　
　　　　　　　　Q　　　　：　状態集合
　　　　　　　　０、¢　：　状態遷移を定義
　　　　　　　　Qi、Qｇ　：　問題を定義

*SOLVE　：　Q１、Q２・・・Qｎ　：　オペレータ（操作）系列＝*PLAN
　
　　　Qでは状態をどのように表現すれば良いか？
　　　適切な状態の表現とは何か？

（１）全ての状態の数え上げについて
　　　もれなく、重複がなく、余計な状態を含まず

（２）できる限り、規則的に数え上げる
　　　→プログラミングの実装上、アクセス問題
　　　　（配列で表した時のインデックス計算）

（例２）　オセロの状態表現
　　　　　ｎ×ｎの正方マス目平面に
　　　　　白、黒、+空白　=　計３種のマス目状態を配置する問題

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