総合科目「計算と知能の科学」　森下真一

Lecture

講義名：総合科目「計算と知能の科学」
教官：森下真一
教養学部
日時：平成１２年度夏学期　５月９日・２３日・３０日・６月６日
火曜日午後４時２０分～６時２０分
場所：駒場教養学部 572号室（講義）
情報教育南棟大演習室１（演習）
備考：萩谷先生と西田先生との共同
萩谷先生の講義ページ
西田先生の講義ページ

６月１３日（火）からは西田先生が担当です。
最初の講義は５７２号室　です。

講義内容（５月９日・２３日）

基本的なデータ構造であるリスト構造、スタック、キューをＪａｖａでプログラミングします。基本的な技術をマスターしたら、探索して解を求める問題、特にパズル問題への応用を紹介します。次に、高速に解を求めるための工夫を解説します。また、簡単なプログラムから出発して、プログラムを徐々に成長させてゆく過程でオブジェクト指向的考え方が役立つことを学びます。

リスト構造スタックキュー

プログラム
有向グラフの幅優先探索(breadth-first search)･
深さ優先探索（depth-first search）

プログラム
８パズルの幅優先探索(Breadth-First Search)･
深さ優先探索（Depth-First Search）による解法

プログラム
優先度付きキューと Best-First Search
８パズルの解法

プログラム

演習の課題　（５月３０日・６月６日）

１６パズルの実装
８パズルのプログラムを改良して１６パズルを解きます。
Priority Queue にどのぐらいのノードが enqueue されるかも観察します。

例題

6	2	3	4
1	10	7	8
5	9	14	0
13	15	11	12

Bin Packing 問題

いろいろな大きさのコップに、その容積一杯に水が入っているとする。各コップ u の容積は正の整数 s(u) とするとき、コップの集合を U とする。

一方、容積がどれも正の整数 B であるビンが K 個あるとする。

各コップの水はどれか一つのビンに注ぐとするとき、各ビンがこぼれないように注ぐ方法はあるか？

すなわち U を互いに交わりのないＫ個の部分集合 U1, U2, ..., UK に分割し、しかも各部分集合 Ui のコップの容積の和がビンの容積 B 以下となるように分割することができるか？

例題　

コップの容積　（同じ容積のコップが複数ある）	ビンの容積	ビンの数
4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3	10	4
8, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2	14	6
8, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2	14	7
6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2	14	6

Bin Packing 問題の工夫

データ構造

最適化問題と近似アルゴリズム First Fit

weight の検討

レポートの提出

問題：　Bin Packing 問題

〆切：　６月３０日

送り先：　moris@is.s.u-tokyo.ac.jp (森下真一まで)

　Subject の欄に　「総合科目計算と知能の科学」　と書くこと
　以下のような点について記述および考察をすることが望ましい
　データ構造をどのように定義したか？
　無駄な探索をどのように排除したか？
　weight をどのように工夫したか？
　各例題を解くまでに Priority Queue のどれだけのノードを登録したか？
　自分で難しい例題を考え、自分のプログラムはどのぐらいの性能で動作するか観察する.

６月１３日（火）からは西田先生が担当です。 最初の講義は ５７２号室 です。

６月１３日（火）からは西田先生が担当です。
最初の講義は５７２号室　です。