1
計算機科学入門
(アプリケーション)
九州大学大学院システム情報科学研究院
情報学部門
横尾 真
E-mail:
[email protected]
http://agent.inf.kyushu-u.ac.jp/~yokoo/
2自己紹介
• 1986年東京大学大学院工学系研究科
電気工学専門課程 修士課程修了
• 同年 日本電信電話株式会社 (NTT) 入社
• NTT情報通信処理研究所 (神奈川県横須賀市)，
NTTコミュニケーション科学基礎研究所 (京都
府相楽郡) 等に勤務
• 人工知能，マルチエージェントシステムに関する
研究に従事
• 1995年 博士 (工学)，東京大学工学系研究科
電子情報工学専攻
• 2004年４月より九州大学システム情報科学研
究院 教授，2012年より主幹教授
3講義全体の概要
• アプリケーション – 担当： 横尾 – 日程： 4/11, 4/18, 4/25, 5/2 (小テスト) • 5/9は火曜日の講義日 • ソフトウェア – 担当： 櫻井 幸一 教授 – 日程： 5/16, 5/23, 5/30, 6/6, 6/13 • アーキテクチャ – 担当： 村上 和彰 教授 – 日程： 6/20, 6/27, 7/4, 7/11, 7/18 4成績に関して
• 定期試験は行わない
• 三名の評価の合計
• 評価方法はそれぞれ異なる（かも知
れない）
–出席／レポート／小テスト等
5講義の目的
目的：
計算機科学に興味を持ってもらう
背景：
卒業研究を始めるまでは，基礎的な
勉強が主で，そこで学んだことがどう役
に立つのか，何か面白いことができるの
かが分かりにくい
方針：
計算機科学の面白いアプリケーショ
ンを紹介する
– 人工知能／探索
6講義について
• パワーポイントのスライドを用いる
• スライドは後日ホームページで公開
•
http://agent.inf.kyushu-u.ac.jp/~yokoo/
– Makoto Yokooで検索すれば出てくる
• 詳細なノートを取る必要はない (話の内容
に集中!)
• 演習等を交える
• 方針： 早めに終わる (短時間に集中!)
7
成績に関して
(横尾担当分)
• 出席＋小テストの成績 (5/2に予定)
8探索とは?
• 探索とは様々な人工知能における問
題解決のテクニックを総称する用語
– 解を求めるために必要な行動の系列が分
かっていない
– 可能な候補に関する試行錯誤的な評価が
不可避
9探索とは? (続き)
• テクニックの中身は特に“知的”という
わけでもない （普通のアルゴリズム）．
• 人工知能に限らず，広く色々な問題に
適用可能
• 面白い！
– プログラム自体は比較的シンプル
– 問題によって多彩な動作
10内容
• 制約充足
• ゲーム木探索
•
経路探索
11アウトライン
• 制約充足問題
– 問題の定義
– 例題・適用領域
– アルゴリズム
12例題: 8-queens
• チェスの盤面に，
8つのクイーンを
互いに取り合わ
ないように置く
13
例題: 色塗り問題
• 領域を赤・青・白の三色で，隣接する領域が
異なる色となるように塗り分ける
14問題の性質
• 与えられた条件 (制約) を満たすような
組み合わせ的な構造を求める．
– queen1の位置，queen2の位置，...
– 領域1の色，領域2の色,...
様々な応用分野
(資源割当て，診断・解
釈，設計，プランニング) で，このような
問題を解くことが必要とされる．
15問題の形式的な定義
定義： • 有限で離散的な領域 D1, D2, ..., Dnから値を取る 変数の集合x1, x2, ..., xn – 例: 4-queens, 各列に一つしか置けないことは自明， 各列のqueenの位置を一つの変数として表す． 領域は{1, 2, 3, 4} • 制約の集合，制約は変数を引数とする述語として記述される – 例: p12(x1, x2) : x1≠x2 and |x1 ー x2| ≠1 目標： • すべての制約を満足する変数の値の組合せを求める (NP完全) Q Q Q Q x1 x2 x3 x4 {blue, yellow} {red, blue} {yellow}{red, blue, yellow} x1 x2 x3 x4 16
例題：覆面算
• 変数，領域は?
• 探索空間の大きさは?
• 制約は?
SEND
+MORE
MONEY
17例題：論理パズル
• 男性（こうじ，てつや，ひろし）と女性（さおり，みゆ
き，まゆみ）が一人ずつペアになっている
• 各ペアに得意な料理（カレー，天ぷら，とんかつ）
が一つずつある
• ヒント
– こうじとさおりはペア – みゆきの得意料理はカレー – てつやの得意料理は天ぷら• ヒントを満たすペア，得意料理を見つける
• 制約充足問題として定式化するには?
18案1
• 各女性に対して，ペアの男性，料理に対応する変数を考える • 例： さおり：ペア， 変数の領域は｛こうじ，てつや，ひろし｝ • 例： まゆみ：料理， 変数の領域は｛カレー，天ぷら，とんかつ｝ • 変数は6, 変数の領域は3, 探索空間は3^6=729 • 制約は さおり：ペア≠みゆき：ペア 等 • ヒント1: さおり:ペア=こうじ • ヒント2: みゆき:料理=カレー • ヒント3: てつやの得意料理は天ぷら – 制約として表現するのはちょっと面倒， – if x：ペア=てつや then x：料理=天ぷら19
論理パズル
変数：
さおり：ペア｛こうじ，てつや，ひろし｝
みゆき：ペア｛こうじ，てつや，ひろし｝
まゆみ：ペア ｛こうじ，てつや，ひろし｝
さおり：料理 ｛カレー，天ぷら，とんかつ｝
みゆき：料理 ｛カレー，天ぷら，とんかつ｝
まゆみ：料理 ｛カレー，天ぷら，とんかつ｝
ヒント1: さおり:ペア=こうじ
ヒント2: みゆき:料理=カレー
ヒント3: てつやの得意料理は天ぷら
制約として表現するのはちょっと面倒， if x：ペア=てつや then x：料理=天ぷら解いてみよう！
20案1（続き）
• さおり：ペア=こうじ
• みゆき：料理＝カレー
• 値の決まっていない変数
– みゆき：ペア {てつや，ひろし} – まゆみ：ペア {てつや，ひろし} – さおり：料理 {天ぷら，とんかつ} – まゆみ：料理 {天ぷら，とんかつ}• 実質的には残る組合せは4通り
• てつやのペアの得意料理は天ぷらであると
いう制約を満たすのは一つだけ
21例題：クロスワードパズル
• 利用可能な (すべて使う
わけではない) 単語の候
補が与えられている
• 二文字以上の縦／横のつ
ながりが単語となる配置を
求める
• 単語は一回しか使えない
1 2 3 4 6 5 7 8候補：
AFT, ALE, LEE, EEL, TIE
LINE, HEEL, HIKE, KEEL, KNOT
HOSES, LASER, SAILS, SHEET, STEER
22
案1
• 各白マス (22個) を変数
• 領域はアルファベット
26文字
• 探索空間は 26
22≒10
31 1 2 3 4 6 5 7 8 23案2
• 変数は1横，縦2等の連続したマ ス(8個) • 変数の領域は，文字数の一致 した単語1ACROSS: HOSES, LASER, SAILS, SHEET, STEER
2DOWN: HOSES, LASER, SAILS, SHEET, STEER
3DOWN: HOSES, LASER, SAILS, SHEET, STEER
4ACROSS: LINE, HEEL, HIKE, KEEL, KNOT
5DOWN: LINE, HEEL, HIKE, KEEL, KNOT
6DOWN: AFT, ALE, LEE, EEL, TIE 7ACROSS: AFT, ALE, LEE, EEL, TIE 8ACROSS: HOSES, LASER, SAILS,
SHEET, STEER • 探索空間は58=390625 1 2 3 4 6 5 7 8 24
NP完全な問題とは
•
クラス
NP :
解かどうかのチェックは高速に
(変数の
個数nに関する多項式時間で) できる問題の集合
•
クラスNP完全:
クラスNPの中で最も難しい問題の
集合
– これのいずれかが多項式時間で解ける (クラスPに属す る) としたら，クラスNPのすべての問題は多項式時間で 解ける – (多分) 多項式時間では解けず，最悪ケースの計算時間 はnに関して指数的 (ただしP≠NPの証明は未解決) – 直接 解を求めるような方法は一般には存在しない – 試行錯誤的な探索が不可欠最悪ケースが指数的になるのはあきらめて，平均的
に速く解ける方法を考えることが研究課題
25
鼠算の恐ろしさ
計算時間
(e.g., チェックすべき組合わせの数) が
2のn乗とすると，一秒に一億回の計算／チェッ
クができる計算機を用いた場合の計算時間
• n= 10 : 10万分の1秒
• n= 20 : 100分の1秒
• n= 30 : 11秒
• n= 40 : 3時間
• n= 50 : 130日
• n= 60 : 365年
• n= 70 : 37万年
• n= 80 : 4億年
• …
26制約充足問題の応用例
移動体通信の周波数割当て
channels channels channels 27制約充足問題の応用例
• 線画の解釈
+: 凸 - : 凹 → : 他の面が隠れている + -+ + -+ + + - -- -- ++ + + -+ + -28制約充足問題の応用例
• 論理回路／ソフトウェアの検証
• ロボット等の行動計画の作成
• 資源割当問題
• スケジューリング
• タイムテーブル作成
• ...
29制約充足アルゴリズム
• 部分解構成法 （バックトラッキング）
• 反復改善法
• ハイブリッド
• consistencyアルゴリズム
30部分解構成法
基本的なアイデア
• 変数の個数をn, 各変数の領域の大きさをmとす
ると，解の候補はm
n個，これを網羅的にチェック
すると鼠算
• 部分的な問題の解 (部分解) を求めて，それを
拡張していくことにより，元の問題の解を得る
• 部分解でなければ，絶対に元の問題の解には
ならない
x1 x2 x3 x4 x1 x2 x3 x431
バックトラッキング
• 部分解に変数を一つ一つ追加することにより部分解 を拡張 • ある変数に関して，部分解と制約を満足する値が存 在しない場合，直前に部分解に加えられた変数の値 を変更 (バックトラッキング) x1 x2 x3 x4
32演習：7-queens
• バックトラッ
キングで解
いてみよう
33バックトラッキングのための
ヒューリスティックス
バックトラッキングは単純な深さ 優先の木探索であるが，効率 を改善するためには多くの工 夫が必要 – 変数／値の決定順序 – 重複した計算の削減 – 行き詰まり（デッドエンド） の早期発見 – デッドエンドの真の原因へ のバックトラッキング – ......
x1 x2 x3 x4 34制約違反最少化バックトラッキング
(Minton,
et al. AIJ-
92)
• 各変数は暫定的な初期値を持つ • 変数を部分解に加える際に，以下のように初期値を変更： – 部分解との間の制約をすべて満足 – まだ部分解に入っていない暫定的な初期値との制約をで きる限り多く満足（制約違反最少化ヒューリスティック） アルゴリズムの完全性は保証されるが，悪い部分解を 作ってしまうと遅い x1 x2 x3 x4 35
アルゴリズムの完全性
• 解が存在するなら必ず解を得ることがで
きる
• 解が存在しないならないことを発見する
多くの場合，完全性を保証するためには系
統的な探索を行うか，膨大な履歴を持つ
必要がある．
366-queens
• 制約違反最小
化バックトラッ
キングで解い
てみよう
37
