06 2020/07 08
28293001020304
05060708091011
12131415161718
19202122232425
26272829303101
Click セミナー

過去のセミナー

開催日2019年5月23日(木曜日)
開催時間16時30分-17時30分
発表者鈴木 浩史 
発表者の紹介富士通研究所
タイトルZDD上での集合パッキングの高速な探索 
発表の概要
与えられた集合族から互いに素な集合をいくつか選び出すことを集合パッキングと呼ぶ。
集合パッキングに帰着される事例として、ネットワーク中で複数の辺素パスを構成することや、
選挙区割のような分割を構成することなどがあげられる。
このような事例において、指定の基準で最適な集合パッキングを構成することは実用的に重要とされている。
例えば、総経路長や最大経路長が短い辺素パスや、人口格差の少ない区割りなどがしばしば必要とされる。

本発表では、集合族がZDDによる圧縮表現で与えられることを前提とし、
線形な目的関数で最適な集合パッキングを高速に探索する手法を提案する。
さらに、他の目的関数でも類似した手法を適用できないか議論する。
提案手法の前提となるZDDを構築するアルゴリズムは、
パスや連結成分をはじめとする様々な集合族に対して考案されている。
そのため、提案手法は前述の事例を含む様々な課題を実際に扱うことが期待できる。
開催場所VBL301B
接続サイト神田ラボ,京大ラボ
開催時間17時30分-18時30分
発表者堀山 貴史 
発表者の紹介埼玉大学
タイトル列挙アルゴリズムの合成による列挙 
発表の概要
列挙問題においてすべての解を効率的に求める手法として、
二分決定グラフ (BDD; Binary Decision Diagrams) や
零抑制型二分決定グラフ (ZDD; Zero-suppressed Binary
Decision Diagrams) を利用する方法が知られている。
BDD/ZDD を利用することで、解集合同士の演算が
容易に定義でき、かつ効率的に実行できる。このため、
BDD/ZDD の構築アルゴリズムを設計する際には、
問題の解が満たすべき必要十分条件を複数の制約条件に
分解し、そのそれぞれを満たす解を表す BDD/ZDD の
構築法を個別に設計するアプローチを取られることも多い。
本講演では、オイラー路の列挙などを例にとりながら、
このアプローチの拡張について議論する。
開催場所VBL301B
接続サイト神田ラボ,京大ラボ