wiki:GB20301/2013-10-08

Version 4 (modified by chris, 10 years ago) (diff)

人工知能 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. 実行