平成27年度研究テーマ紹介

アルゴリズム教育研究分野
(ES4)
研究室紹介
研究室の教職員,大学院生
教授
准教授
助教
技術職員
修士2年生
修士1年生
増田
山口
斎藤
山中
5名
5名
研究分野(キーワード)
アルゴリズム
データ構造,データ検索
組合せ最適化
グラフ・ネットワーク
パターン情報処理
配属定員と卒研テーマ分類
配属定員10名
A 情報表示のためのアルゴリズム
4名
B 組合せ最適化問題の解法とその
応用
3名
C 列挙アルゴリズム
3名
A 情報表示のためのアルゴリズム
複雑な情報を,人間にとって分かりやすく
表示するためのアルゴリズム
・ グラフで表現できる構造や関係の描画
・ 図中への文字列の配置(ラベル配置)
A1 有向グラフの階層描画アルゴリズム
階層描画の例
科目間関係図
科目 (頂点)
科目間の
関係 (辺)
辺交差数
1282
A1 有向グラフの階層描画アルゴリズム
複雑な有向グラフを
見やすく自動描画
する方法の開発
辺の描き方を
工夫
辺交差数
59
A2 デフォルメ路線図作成アルゴリズム
大阪市営地下鉄
グラフ描画の手法を応用した結果
路線の形状をより簡潔にしたい ⇒ 新しい方法の開発
A3, A4 地図ラベル配置アルゴリズム
アルゴリズムの実行時間 vs ラベル配置の質の高さ
A3では実行時間を,A4では解の質を重視
B 組合せ最適化問題の
解法とその応用
• 問題の効率的な解法を設計する.
• 解法の性能を実験などにより評価する.
1. 最大重みクリーク問題
2. クラス編成問題
B1 最大重みクリーク抽出
• クリーク=辺で繋がっ
ている頂点の集まり
• 右図の正解は2,5,7
– 1,2,8
– 2,3,8
– 4,8
5
7
• 応用は極めて多い
– 製造,通信,金融…
3
2
1
8
4
– 賞金1億円 (クレイ数学研究所)
• 受賞など:
KJCEE 優秀論文発表賞(2011), 奨励賞(2012)
ACS 2013 (selected 30%) : 世界最速の手法
B2 クラス編成問題
• 学生を研究室に配属
• 多くの学生の希望通り
に割り当てたい
– どうなれば幸せ?
– 割り当ての計算方法?
• 多岐にわたる応用
– 資源の有効割り当て
– 輸送計画
– 製造ラインの効率化
C 列挙アルゴリズムに関する研究
• 列挙とは:目的とする対象をすべて出力(格納)すること
• 列挙の目的
– データの特徴抽出(データマイニング)
• 例:紙おむつとビールを一緒に買う人が多い
– 列挙したものから良い解の検索
• 複雑な目的関数・制約条件に対応
• 良い評価値を持つ例をたくさん見たい
高速な列挙アルゴリズムが必要!
1. 集合分割問題に対する高速なアルゴリズムの開発
2. 組合せゲーム・パズルの完全解析
C1 集合分割問題に対する高速なアルゴリズムの開発
• 集合分割問題
入力:0と1からなる行列
出力:すべての列でちょうど1回
ずつ 1 が現れる行の集合
• 右の例の解:{a, e}, {b, c, e}, {b, d}
• 領域分割への応用
– 避難所割当,選挙区割りなど
京都市上京区の
避難所割当例
☆:避難所
1
2
3
4
5
a
1
1
1
0
0
b
1
1
0
0
0
c
0
0
1
0
0
d
0
0
1
1
1
e
0
0
0
1
1
C2 組合せゲーム・パズルの解析
• 組合せゲーム・パズル
–
–
–
–
–
ペンシルパズル(数独,スリザーリンク,ナンバーリンクなど)
ボードゲーム(将棋,オセロなど)
落ちゲー(ぷよぷよ,テトリスなど)
詰め込みパズル(ペントミノ,DeeCubeなど)
陣取りゲーム(ボロノイゲームなど)
どのゲーム・パズルも組合せ爆発が起こる!
• 研究テーマ
–
–
–
–
高速なパズルソルバー
ゲーム・パズルの完全解析
パズル問題の自動生成
ゲームAIの作成
年間スケジュール
5月
4月
研
究
テ
ー
マ
説
明
研
究
室
配
属
研
究
環
境
の
整
備
グ
ル
ー
プ
分
け
7月
8月
1月
2月
卒
業
論
文
執
筆
卒
論
提
出
・
発
表
卒業研究
院試勉強
本読みゼミ
プレゼン
プログラミング課題
・アルゴリズム技法の習得
1. プログラミング課題
2. 本読み(AHUゼミ)
中
間
発
表
(
数
回
)
正しく動作する効率の
よいプログラムの開発
充実した1年を過ごせます!!
期待する学生像
• プログラミングが好きな人
– 効率的なプログラムを書きたい!
– コンピュータで解きたい問題がある!
• 離散の世界が好きな人
– グラフが好き!
– パズル・ゲームが好き!
• やる気・元気のある人
研究室見学
2E-402
• 場所:4階 2E-402
(学科事務室の1階上)
• 日時:本日15時~17時
B-404
(山口)
B-402
(増田)
研究室見学
2E-402
• 場所:4階 2E-402
(学科事務室の1階上)
• 日時:本日15時~17時
• デモプログラムの展示
• 質疑応答
B-404
(山口)
B-402
(増田)