アルゴリズム教育研究分野 (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 (増田)
© Copyright 2024 ExpyDoc