FIT2019 第18回情報科学技術フォーラム

イベント企画

グラフアルゴリズムの新潮流：組合せ遷移とその応用

9月3日(火) 9:30-12:00
第3イベント会場（一般教育棟 A棟 A41）

【セッション概要】組合せ遷移は、持続的システムやパズルといった動的な状態遷移を数理モデル化し、そのアルゴリズムを解析する研究である。近年、グラフアルゴリズムを中心に盛んな研究が行われており、世界的な新しい研究潮流を生み出しつつある。本企画では、組合せ遷移に関する4件のチュートリアル講演を行う。はじめに、組合せ遷移の理論フレームワークを解説し、研究動向を概観する。続く2件では、伝統的な離散数学やパズル・ゲームを組合せ遷移の観点から見直す。これらの事例をモデルとして、様々な研究へ組合せ遷移の視点を導入する契機となれば幸いである。最後に、組合せ遷移に関する産学共同研究の一例として、配電系統の切替手順について解説する。

9:30-10:15 講演(1) 組合せ遷移への招待
伊藤　健洋（東北大学大学院情報科学研究科准教授）
【概要】本講演では、組合せ遷移の様々な研究背景を紹介しながら、それらを数理モデル化した理論研究の枠組を導入する。組合せ遷移の枠組は、大まかに言えば、「初期状態」からスタートし、「許された変更操作」を繰り返し適用しながら、「目標状態」に遷移できるか？を問うものである。ここでいう「状態」とは「基となる探索問題の実行可能解」を意味しており、したがって組合せ遷移は、実行可能解によって形成される解空間の到達可能性を問う研究といえる。組合せ遷移は、様々な分野で研究されてきた。特に近年では、独立点集合や点彩色、マッチングなどグラフに関する組合せ遷移問題に対して、アルゴリズム開発や計算困難性の解析が進められている。本講演では、これらグラフに関する組合せ遷移問題を中心に最近の研究動向を概観するとともに、組合せ遷移におけるアルゴリズム開発の難しさ・面白さをお伝えしたい。
	【略歴】 2006年東北大学大学院情報科学研究科博士課程後期3年の課程修了。博士（情報科学）。同年より東北大学大学院情報科学研究科助手、助教を経て、2012年より准教授。アルゴリズムの理論研究に従事し、特にグラフに関連する問題の研究に取り組む。2018年度科学技術分野の文部科学大臣表彰若手科学者賞、船井情報科学振興財団第17回船井学術賞、国際会議ISAAC 2008 Best Paper Award等、受賞。
10:15-10:45 講演(2) 組合せ遷移と離散構造
岡本　吉央（電気通信大学大学院情報理工学研究科教授）
【概要】本講演は「組合せ遷移は、離散数学において伝統的に研究されてきた」という立場で、離散数学においてどのような組合せ遷移問題が考えられてきたか、紹介する。また、その文脈において、最近勃興してきた計算理論的側面も含めて、講演者自身の共同研究成果と未解決問題も述べる。その際に、鍵となる概念は、有限束のハッセ図、凸多面体の1骨格、および、有限群のケーリーグラフである。これらの概念を、まず、コンピュータ・サイエンスにおける基本的な問題であるソーティングを例として、説明する。そして、カタラン構造、線形計画法、置換群のような離散数学における概念と組合せ遷移がどのように関係しているのか、紹介する。
	【略歴】 2005年スイス連邦工科大学チューリッヒ校にてPh.D.を取得。2005年豊橋技術科学大学工学部助手、2007年同助教、2007年東京工業大学大学院情報理工学研究科特任准教授、2010年北陸先端科学技術大学院大学大学院教育イニシアティブセンター特任准教授、2012年電気通信大学大学院情報理工学研究科准教授を経て、2017年より同教授。2013年より理化学研究所客員研究員を兼務。専門は離散数学、離散アルゴリズム、離散最適化。訳書に「凸多面体の数学」（共訳、丸善出版）、「離散幾何学講義」（丸善出版）、「離散体積計算による組合せ数学入門」（丸善出版）。
10:45-11:15 講演(3) 組合せ遷移とパズル・ゲーム
上原　隆平（北陸先端科学技術大学院大学先端科学技術研究科教授）
【概要】アルゴリズムとは基本演算の組合せであり、どんな基本演算を用いるかによって、効率が大きく変わってしまう。さて、ある種のパズルを楽しんでいるとき、人は基本操作をうまく組み合わせて目標を達成する。これはアルゴリズムの開発に他ならない。こうした意味で、パズルは計算量クラスについての新たな知見を与えてくれる。実際、ある種のパズルやゲームは、計算量クラスについて妥当性のある特徴づけを与えてくれる。最もよく知られた例は、１５パズルであろう。このパズルの初期状態から目標状態への到達可能性は、パリティを調べれば即座に判定できる。具体的な手順も簡単に計算できる。ところが最短手数を求める問題はNP完全であり、より一般的なスライディングブロックパズルは、到達可能性を判定するだけでもPSPACE完全である。本講演では、こうしたパズルと計算量クラスの関係の歴史を紹介し、計算量クラスに新しい着眼点を与えることを目指す。
	【略歴】 1998年電気通信大学電気通信学部情報工学科で論文博士（理学）。キヤノン（株）情報システム研究所研究員(1991-1993)、東京女子大学情報処理センター助手(1993-1998)、駒澤大学文学部自然科学教室(1998-2004)を経て2004年より北陸先端科学技術大学院大学情報科学研究科助教授（のち准教授に変更）を経て2011年より同大学教授。計算量の理論やグラフアルゴリズムの研究に従事。特に計算折り紙やパズル・ゲームの計算量を中心に研究。情報処理学会、電子情報通信学会、EATCS日本支部長など。
11:15-11:45 講演(4) 組合せ遷移の応用：配電系統の切替手順
杉村　修平（（株）明電舎電力・エネルギー事業部担当）
【概要】配電系統は多数の開閉器（スイッチ）を有しており、その開閉状態を制御することで、系統構成（電力の供給経路）を決定している。系統構成は、停電を生じさせないのはもちろんのこと、許容電流や適正電圧など種々の制約条件を満たさなければならない。また、配電にかかる電力損失をはじめ、系統構成の良し悪しはその時々で変わる。配電系統の切替手順とは、現状の系統構成から目的の系統構成へと切り替える開閉器の操作手順であり、その遷移の過程においても制約条件を満たす必要がある。本研究では、配電にかかる電力損失を最小化する系統構成を求めるだけでなく、その切替手順も合わせて算出するアルゴリズムを開発した。開発したアルゴリズムは、実験的にも高い性能を示している。また本講演では、分散型電源の大量化による電力潮流の変化など、配電系統を取り巻く状況の変化と課題を解説し、アルゴリズムの理論を配電系統へ応用する可能性についても模索したい。
	【略歴】 2015年名古屋大学大学院工学研究科電子情報システム専攻修士課程修了。同年4月（株）明電舎に入社。主に配電系統の運用管理に関する研究開発に従事。