== 人工知能 2.3 2013-10-08 ==

=== 問題解決 ===

* 方程式を解く
 * x + y = 12
 * 100x + 50x = 850

* 最小公倍数を求める

このような`P`な問題は人工知能にとってはどうでもいい

人工知能は、''試行錯誤をしながら''求める

* 迷路を抜ける
* パズル
* チェスをプレイする

人工知能によるボートゲームの実装

* 盤とコマの表示
* ユーザの入力を受け付ける
* 禁則処理 (≒ルール違反のチェック)
* 入力の反映
* コンピュータが手を考える
 * 取りうる手をリストアップ→一つ選ぶ
 * 次どうなるか予測
* 最適な手を実行

------

=== 組み合わせ爆発 ===

* 適当にさぼってまあまあの解を得る
 * 問題の特徴によって、optimizationの実装が異なる

 巡回セールスマン問題::
  いくつかのノードを全て結ぶ最短の線を算出する

 ナップザック問題::
  大きさ・重さ・価値などのattributesが異なるアイテムを、ナップザックの容量や耐荷重の制約のもとできるだけ詰め込む

 迷路::
  木構造で表現し、(縦型|横型)探索で解く

----

計算機で表現する (定式化)

* 状態 `(x, y) // 4Lの水差しに入っている水の量, 3Lの水差しに入っている水の量`
* 初期状態 `(0, 0)`
* 目標状態 `(2, y)`
* 定義域 `{ (x, y) | x = {0, 1, 2, 3, 4}, y = {0, 1, 2, 3} }`

1. 操作をいくつか定義する
2. 状態遷移図(グラフ)で、ルールにのっとったパスを列挙する
3. 実行