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