基盤(S) 離散構造処理系プロジェクト 紹介
プロジェクトの近況と今後の展望
平成29年12月25日

研究代表者 湊 真一
（北海道大学 情報科学研究科）

ERATO/基盤(S)の活動経過と今後のロードマップ
2009.10 2010.4 2010.10 2011.4 2011.10 2012.4 2012.10 2013.4 2013.10 2014.4 2014.10 2015.4

後継プロジェクト

(4年目)
(5年目)
(0年目)
(1年目)
(3年目)
(2年目)
採択
初夏の 秋の
春の 秋の初夏の 秋の初夏の 秋のキック 秋の
閉所式
合宿
WS
WS 合宿
合宿
合宿
WS
WS
合宿
GL委嘱 オフFIT2010
通信
情処 講究録FIT2013
NTT研 ALSIP
WS
講究録 公開NII
交渉企画 企画 出版
学会
シンポ審査
講演 RC 特別セミナ
出版 シンポ
講演
シンポ シンポ 各種研究会企画
2014
研究員 Knuth邸
報告会
AI学会未来館
最終
ALSIP
RM 北大博物館
スカウト 訪問 各種研究会 CMU 共催 シンポ
展示
特集号
報告会
2014
ALSIP
訪問 ALSIP電力網
2013 展示
国際会議共催札幌科学未来館
東工大
オフィス選定 民間企業との共同研究 2011
新検定法
2012
報道発表
館展示 再展示
集中講義
内装工事
報道発表
研究員出向交渉
北大連携講座2015.4 2015.10 2016.4 2016.10 2017.4 2017.10 2018.4 2018.10 2019.4 2019.10 2020.4(2年目)(6年目/1年目)
基盤S
合同 神田ラボ 合同
キックオフ WS
採択
WS
初夏の 秋の
初夏の秋の
WS
合宿
WS 合宿
ISMVL
専門書 未来館
講演 統計応用
出版
再展示
報道発表
WS
企画 最終
AI学会
シンポ 評価 オフィス
講演
移転

(4年目)
(3年目)
研究 JSPS
初夏の進捗書 進捗
WS
秋の
SoCS
提出 評価
合宿
講演
ヒアリング／IFCS Dag現地調査？
講演 stuhl
講演
FPAI EPFL
共催 講演
さきがけ 合同WS
合同WS
2017.12.25

(5年目)
最終
評価

東京
五輪

2

基盤（S）「離散構造処理系」の研究構想
Art層の周辺部では後継プロジェクトへの発展に成功しつつある．
ボトムアップな科研費でArt層のコア部分に研究者が集まる「場」を継続的に提供し，競争力の源泉となるアイデアを醸成し続けるシステム最適化・
形式的検証

知識発見・
データマイニング

統計解析・
モデリング

応用技術
(Engineering)

応用技術(Engineering)

応用技術(Engineering)

個別の工学的応用に特化した技術領域

本研究が扱う技術領域

離散構造処理系（実装技術，“Art”）- 概念・理論だけでなく処理系実装を重視- 技術基盤としての簡潔さ・汎用性を重視

分野横断的な計算理論の領域（概念的・理論的）

計算理論(Computer science / 数学)

2017.12.25

3

基盤（S）「離散構造処理系」の研究構想
Art層の周辺部では後継プロジェクトへの発展に成功しつつある．
ボトムアップな科研費でArt層のコア部分に研究者が集まる「場」を継続的に提供し，競争力の源泉となるアイデアを醸成し続けるシステム最適化・
形式的検証

知識発見・
データマイニング

統計解析・
モデリング

応用技術
(Engineering)

応用技術(Engineering)

応用技術(Engineering)

個別の工学的応用に特化した技術領域

電力系
CREST

産総研
AI研究センタ

本研究が扱う技術領域- 概念・理論だけでなく処理系実装を重視- 技術基盤としての簡潔さ・汎用性を重視

分野横断的な計算理論の領域（概念的・理論的）

離散構造処理系（実装技術，“Art”）

ビッグデータCREST/
さきがけ
理研AIPセンタ

河原林ERATO
新学術「計算限界」

計算理論(Computer science / 数学)

2017.12.25

4

基盤（S）申請書（抜粋）
予算規模はERATOの10分の１
 ERATOと同じことはできない5

基盤（S）申請書（抜粋）
予算規模はERATOの10分の１
 ERATOと同じことはできない
Art層の周辺領域については、
連携プロジェクトに研究開発を任せ、Art層のコア部分で競争力の源泉となるアイデアを醸成する場を継続的に提供

6

基盤（S）「離散構造処理系」の主要研究課題
 離散構造処理系の基盤アルゴリズム技術の確立とソフトウェアの整備
 電力・道路・鉄道・通信，避難所割り当て，選挙区割りなどの社会インフラ問題への応用に必要な基盤アルゴリズムの研究開発
 BDD/ZDDの新しい派生形とその処理系の研究開発・ツール化

 離散構造処理系による効果的な探索法および列挙索引化法の開発
 ERATOでの研究成果を受けつぎ，
新しい探索・列挙索引化アルゴリズムの研究開発を継続して進める．

 Art層コミュニティの維持発展、および国家プロジェクトとの連携
 セミナ、ワークショップ、学会共催イベント、国際ワークショップ開催，学会誌・単行本の執筆、アウトリーチ活動を積極的に行う．
 ビッグデータCREST/さきがけ，電力CREST、河原林ERATO，
新学術「計算限界」, 海外研究機関との情報交流や研究者交流7

基盤（S）「離散構造処理系」の実施体制
分担者：

代表者：

湊 真一（北大）
・基盤アルゴリズムの研究開発
・SeqBDD、πDD処理系の開発
・ワークショップ・セミナ開催
・研究計画全体の推進マネジメント

津田 宏治（東大）
・統計多重検定(LAMP)への応用
・CREST「離散構造統計学」との連携

鷲尾 隆（阪大）
・機械学習と統計モデリングへの応用
・劣モジュラ解析・データ次元の解析

研究協力者：

宇野 毅明（NII）

渡辺治（東工大） - 新学術「計算限界」
河原林健一（NII） - ERATO「巨大グラフ」
林泰弘（早稲田大） - 電力CREST最強チーム
加藤直樹、羽室行信（関学大）- CREST「革新アルゴリズム」
佐久間淳（筑波大）- CREST「セキュリティ」
竹田正幸（九大） - サイバーフィジカル
伊藤公人（北大） - 人獣共通感染症
R.Raman（レスター大） - 簡潔データ構造
A.Darwiche(UCLA) - 確率グラフィカルモデル

・超高速列挙アルゴリズム技法
・CREST「データ粒子化」との連携

有村 博紀（北大）
・超高速な半構造マイニングへの応用
・グラフ列挙と索引化の基礎技法

堀山 貴史（埼玉大）
・種々の離散構造モデルへの拡張
・新学術「計算限界解明」との連携
8

プロジェクトメンバ構成
基盤(S)北大メンバ

湊 真一
研究代表者

渡辺 幸恵
北大事務補助員

東京・神田ラボ
和佐 州洋(CREST
博士研究員)
岩崎さん桑田さん
宇野先生 (CREST (事務（サテラボ 技術員) 補助員)
リーダ）

Hei Chan
石畠 正和
博士研究員
北大 特任助教（2016.04～ （NEC共同研究）（2016.04～）
NTT CS研より出向）

北大・大学院生RA 14人体制
9プロジェクトメンバ構成
基盤(S)北大メンバ

湊 真一
研究代表者

渡辺 幸恵
北大事務補助員

東京・神田ラボ

和佐 州洋(CREST
博士研究員)
岩崎さん桑田さん
Hei Chan石畠 正和
宇野先生 (CREST (事務北大拠点の地理的特長を生かす
博士研究員
北大 特任助教（サテラボ 技術員) 補助員)
「ポスドク短期滞在プログラム」で（2016.04～ （NEC共同研究）
リーダ）（2016.04～） 中心的な役割
NTT CS研より出向）

北大・大学院生RA 14人体制
10プロジェクトメンバ構成
基盤(S)北大メンバ

湊 真一
研究代表者

東京・神田ラボ

他の情報系プロジェクトとの
Hei Chan石畠 正和
連携拠点として有効に機能
博士研究員
北大 特任助教（絶妙なロケーション）（2016.04～ （NEC共同研究）

渡辺 幸恵
北大事務補助員（2016.04～）
NTT CS研
新幹線駅ホームから10分以内
より出向）
NIIおよび理研AIPから徒歩圏

北大・大学院生RA 14人体制
11

和佐 州洋
(CREST
博士研究員)
岩崎さん桑田さん
宇野先生 (CREST (事務（サテラボ 技術員) 補助員)
リーダ）

神田サテライトラボ© google map

NII 東京都心（JR神田駅・徒歩3分）に関連研究者が情報交換を行うための「連携研究拠点」を設置。

神田駅
神田ラボ

 民間オフィスビル・１フロア約80m2
 新幹線から10分圏内。NIIから徒歩圏
首都圏の多くの大学から好アクセス。 大手町
 賃料割安な地区
 基盤（S)予算で賃料を負担。分担者の宇野先生が現地責任者（NIIが借主） 情報系研究者の交流拠点として提供中

理研
AIP
東京駅

 正式名称：
国立情報学研究所 離散構造処理系プロジェクト
神田サテライトラボ
12ポスドク短期滞在プログラム
 優秀なPD研究者を採用するのは最近は難しい
 河原林ERATOなどが根こそぎ持って行ってしまっている。
 産総研AIセンタや理研AIPセンタなど、PD需要は今後も旺盛で、良い人を引っ張ってくるのはたいへん。
 基盤(S)の予算だと呼べても高々1～2人

 年単位の雇用はあきらめて、よそのPDを出張で招聘して10日～2週間くらい滞在してもらうのなら割と簡単
 来訪直後に最近やっている研究の話をしてもらって、帰る前に、滞在中に共同研究したことを話してもらう 年間５０週あるので、２５人呼べば、常に誰かいることになる。
（もちろん同時に複数重なっても構わない）
 同じ人がずっといるより面白いかも。
旅費滞在費サポートしても雇用費と大差ない13

ポスドク短期滞在プログラム
 優秀なPD研究者を採用するのは最近は難しい
 河原林ERATOなどが根こそぎ持って行ってしまっている。
 産総研AIセンタや理研AIPセンタなど、PD需要は今後も旺盛で、
今年度これまでに短期滞在された方々:
良い人を引っ張ってくるのはたいへん。
坂上さん（NTT）、井上武さん（NTT）、R.Grossi先生（Pisa大）、基盤(S)の予算だと呼べても高々1～2人
間野さん（NTT）、上原先生（JAIST）、岸本さん（IBMダブリン）
 年単位の雇用はあきらめて、よそのPDを出張で招聘して相馬さん（東大）、林さん（立命）、原さん（NII）、杉本さん（九大）、
小宮山さん（東大）、今泉さん（統数研）、吉川さん（千葉工大）、
10日～2週間くらい滞在してもらうのなら割と簡単
山口さん（阪大）、中畑さん（NAIST)、林さん（産総研）、

来訪直後に最近やっている研究の話をしてもらって、吉田さん（豊橋技科大）、松岡さん（東大）、吉成さん（東北大）。
帰る前に、滞在中に共同研究したことを話してもらう
藤井さん（東大）、南さん（東大）

年間５０週あるので、２５人呼べば、常に誰かいることになる。
 基盤(S)オフィスがたいへん活気づいています。（もう限界です！）（もちろん同時に複数重なっても構わない）（1月以降予定）
同じ人がずっといるより面白いかも。
江原さん（産総研）、Wiston先生（台湾大）、横井さん（東北大)
旅費滞在費サポートしても雇用費と大差ない14

ポスドク短期滞在プログラム
 優秀なPD研究者を採用するのは最近は難しい
 河原林ERATOなどが根こそぎ持って行ってしまっている。
 産総研AIセンタや理研AIPセンタなど、PD需要は今後も旺盛で、
今年度これまでに短期滞在された方々:
良い人を引っ張ってくるのはたいへん。
坂上さん（NTT）、井上武さん（NTT）、R.Grossi先生（Pisa大）、基盤(S)の予算だと呼べても高々1～2人
間野さん（NTT）、上原先生（JAIST）、岸本さん（IBMダブリン）
 年単位の雇用はあきらめて、よそのPDを出張で招聘して相馬さん（東大）、林さん（立命）、原さん（NII）、杉本さん（九大）、
小宮山さん（東大）、今泉さん（統数研）、吉川さん（千葉工大）、
10日～2週間くらい滞在してもらうのなら割と簡単
山口さん（阪大）、中畑さん（NAIST)、林さん（産総研）、

来訪直後に最近やっている研究の話をしてもらって、吉田さん（豊橋技科大）、松岡さん（東大）、吉成さん（東北大）。
帰る前に、滞在中に共同研究したことを話してもらう
藤井さん（東大）、南さん（東大）

年間５０週あるので、２５人呼べば、常に誰かいることになる。
昨年のWWW2017に続き、
 基盤(S)オフィスがたいへん活気づいています。（もう限界です！）（もちろん同時に複数重なっても構わない）
共同研究がAAAI2018に2件採択！
（1月以降予定）
同じ人がずっといるより面白いかも。
江原さん（産総研）、Wiston先生（台湾大）、横井さん（NII)
INFOCOM2018に1件、AISTATS2018に1件
旅費滞在費サポートしても雇用費と大差ない（湊 and/or 石畠さんと共著）
15

来年度のポスドク短期滞在プログラム計画
 これまでは主に石畠さんが若手に適当に声をかけて、好きな時期に2週間来てもらっていた。
 2週間×25人で年間スケジュールがほぼ埋まっていて、北大側の現地対応が限界に近い（うれしい悲鳴） 来年度はおそらく石畠さんが出向元に戻る見込みで、
北大オフィス常駐者が手薄に 来年度は、「集中セミナー週間」を毎月設定し、その時期に１週間滞在可能な人を３～５人程度で日程調整して開催
 今年度とほぼ同じ予算で年間40～50人くらいまで呼べます！
 月曜日は○○さんのセミナ発表、火曜日は○○さんの発表、
水曜日は北大RA学生の発表、…のようにして1週間開催
 毎月、基盤（S)関係者で当番（幹事）を決めて、その月に「コアとなる来訪者」１～２人を確定させアナウンスする。
 その他に自主的に参加したい人も歓迎
16夏以降の基盤(S)主要イベント実績
 JSTさきがけ「社会情報基盤」（総括・安浦先生/九大副学長）
合同ミニワークショップ（7月3日, 北大）
 講演者：湊、有村、瀧川

ポスター発表（北大メンバ）

 IFCS2017（国際分類学会,8月8～10日, 東京）
 特別セッション共催(Special Session on Enumeration Algorithm and Data Science) 人工知能学会SIG-FPAI（8月8～9日, 小樽）
 研究会共催、招待講演依頼（美添さん）

 Dagstuhl Seminar on Recent Trends in Knowledge
Compilation （9月17～22日、ドイツ)
 講演者：湊（招待参加）

 EPFL Workshop on Logic Synthesis and Emerging
Technologies （9月28-29日、スイスLausanne）
 講演者：湊（招待講演）

 基盤(S) 秋合宿（11月12～14日, 厚岸町）（50名参加 43件発表）
17夏以降の基盤(S)主要イベント実績
 JSTさきがけ「社会情報基盤」（総括・安浦先生/九大副学長）
合同ミニワークショップ（7月3日, 北大）
 講演者：湊、有村、瀧川

ポスター発表（北大メンバ）

 IFCS2017（国際分類学会,8月8～10日, 東京）
 特別セッション共催(Special Session on Enumeration Algorithm and Data Science) 人工知能学会SIG-FPAI（8月8～9日, 小樽）
 研究会共催、招待講演依頼（美添さん）

 Dagstuhl Seminar on Recent Trends in Knowledge
Compilation （9月17～22日、ドイツ)
 講演者：湊（招待参加）

 EPFL Workshop on Logic Synthesis and Emerging
Technologies （9月28-29日、スイスLausanne）
 講演者：湊（招待講演）

 基盤(S) 秋合宿（11月12～14日, 厚岸町）（50名参加 43件発表）
18

国際的に有名なホットスポット例題への適用
米国N.Carorina
州内100郡市の乳児突然死亡率
連結ブロックを全列挙する
ZDDの構築に成功（世界初）

192017.12.25

国際的に有名なホットスポット例題への適用
米国N.Carorina
州内100郡市の乳児突然死亡率
連結ブロックを全列挙する
ZDDの構築に成功（世界初）

ホットスポット＝内部と外部の尤度比最大の隣接ブロック
尤度比がある閾値αを超える隣接ブロックの全列挙：
 「ホットスポット」列挙問題（全列挙、極大のみ列挙）
日毎、月毎データベースに対するホット/コールドの変化を抽出
 時系列的特徴を持つホットスポット列挙問題
 統計学会の著名研究者（岡山大・栗原先生他）と共同研究
IFCS2017（国際分類学会,8月8～10日, 東京）で特別セッションを共催 20
2017.12.25

今年度のスケジュール
 「フカシギの数え方」北大祭で再展示（6/3-4, 北大）
 国際会議SoCS2017招待講演(6/16, ピッツバーグ)
 UCLA Darwiche研究室訪問
 CMU Bryant研究室訪問

 基盤(S) 初夏のワークショップ(6/23-24, 北大) さきがけ「社会情報基盤」合同WS（7/3, 北大）
 SIG-FPAI共催（8/8-9, 小樽） 国際会議IFCS2017・企画セッション共催（8/8-10, 東京）
 Dagstuhl WS参加（9月, ドイツ）
 国際会議AMBN2017（9月, 京都） EPFL WS招待講演（9月, スイス）
 基盤(S) 秋の合宿（11月, 厚岸） 情報系Winter Festa EP3（12/25,26, 東京）  今ココ
 AAAI2018発表（2月, 石畠さん他, New Orleans）
 来年度以降の基盤(S)プロジェクト体制を計画検討（～2月） 基盤(S)研究進捗報告書作成・提出（3月下旬）
21

今後の展望 あらゆる計算機応用の基盤技術であり、理論と応用の交差点（Art層）を形成している「離散構造処理系」に焦点を絞り、今後も研究を進める 「最適化と列挙は車の両輪」（©湊） 列挙アルゴリズムは確率統計とも相性が良い 列挙・圧縮・索引化・高速演算・検証検定 情報系の多分野に波及する重要基盤技術
 ERATOプロジェクトの成果を引継ぎ、理論研究者と応用分野の研究者が集まる「場」
をさらに発展強化させる
 関連する国家プロジェクトと連携し、基盤(S)成果の発展・実用化を目指す

22

ポスター概要説明

23

北海道⼤学⽯畠 正和

Decision Diagram Constraints• Decision Diagram (e.g., BDD, ZDD)•

論理関数、集合族のグラフ表現••「特定の性質を満たす部分グラフ集合」

f(x) = (x1∧x2) ∨ x3
x1

様々な論理演算・集合演算をサポート
例) 関数 f, g を表現する DD Δ(f), Δ(g) から、
例) 直接 f∧g を表現する DD Δ(f∧g) を構成• Decision Diagram Constraint

x2
x3
0

1

•

最適化や確率計算の制約が DD Δ で与えられると仮定•

⼀般には NP-hard な問題が O(poly(|Δ|)) で解ける！

北海道⼤学⽯畠 正和

Decision Diagram Constraints•••

問題設定： x ∈ {0,1}d•

⽬的関数 : f(x) = Σ{ wixi : i ∈ [d]}: 線形関数•確率分布 : p(x) = Π{θi : xi=1} Π{1-θi : xi=0}: 独⽴ベルヌーイ分布•

制約関数 : c(x) = 1:OK or 0:NG

: DD Δ(c)で与えられる

効率的に解けるタスクの例：⼀般的にはNP-hard•

制約付き最⼤化: x* = argmax{f(x) : c(x) = 1}•

制約充⾜確率: p(c) = Σ{p(x) : c(x)=1}•

制約付き期待値: Ep[f |c] = Σ f(x)p(x|c)

O(|Δ(c)|) 時間

応⽤例：•

論理に基づく確率モデリング [Ishihata+ ILP-08, 11]•

影響拡散度の厳密計算 [Maehara+ WWW-17]•

敵対的オンライン組合せ最適化 [Sakaue+ AISTATS-18]

応⽤求む！！

On the Problem of Accepting Virtual
Evidence in Arithmetic Circuits
Hei Chan 北海道大学+

Pr(A,B | Z)

0

0

0.1

0.1 * 6 = 0.6 -> 0.24

0

1

0.2

0.2 * 6 = 1.2 -> 0.48

1

0

0.3

0.3 * 1 = 0.3 -> 0.12

1

1

0.4

0.4 * 1 = 0.4 -> 0.16*λ(B=0)⅓

0

1¼

λ(A=0)

λ(B=1)
0*

Pr(A,B)

0

1

*

B

0.6

⅓

+

A

¼

+

●

0.4

*

●

*

●

Assume that an arithmetic circuit(AC) is decomposable and smooth
Upward pass computes marginal
probability (Choi et al., ICML17)
Downward pass computes marginal
probability of setting one morevariable (Chan, AMBN17)
We propose a procedure to accept
virtual evidnece (Pearl 88) directlyin AC (Chan, AMBN17)

0

*

0.1

●

AC

0.1

0
¾

⅓

λ(A=1)

⅔

1

Pr = 1Pr = 0.64

λ(A=0)⅓

*

λ(A=1)*

λ(B=0)*

λ(B=1)

2.4

1 0.7
¾

1

*

*
¼

0

+

+

1 0.3

0.6

+

+

λ(B=0)

*

1

*

1

0.4

⅔

¼

λ(A=0)

λ(B=1)

*

0.6

*

*

*

*

+

+

0.4

0.4
¾

⅓

λ(A=1)

⅔

劣モジュラ最大化に対する高速な最良優先探索坂上晋作 NTT コミュニケーション科学基礎研究所
石畠正和 北海道大学 大学院 情報科学研究科

1

概要
ナップサック制約付き単調劣モジュラ最大化
に対する最良優先探索の高速化
貪欲法の近似保証 (0.39 or 0.63) では不足な時もある
従来の最良優先探索は，𝛼-近似解 (∀𝛼 ∈ [0,1]) を出力するが実用上遅い
提案法• 新たなヒューリスティック関数の導入• 𝛼-近似検出処理により最良優先探索を高速化（最大約 103 倍速）

2確率的モデル検査によるユビキタスコンピューティングシナリオの信頼性解析○蓑田 玲緒奈・石畠 正和・湊 真一

北海道大学大学院情報科学研究科

扱う問題: ユビキタスコンピューティング(UC)シナリオの検証●UCシナリオ●(形式)検証

ユーザーはデバイスを持ち運び動き回る
ユーザーの場所に応じて様々なデバイス連携が発生

状態遷移モデルの性質を検証
モデルの性質は時相論理式で記述

ab{a,b,c}→{ab,c}c{ab,c}→{abc}状態: (ユーザーの場所, デバイスの連携状態)

2017-10-11 博士論文執筆計画
2 / 18
確率的モデル検査によるユビキタスコンピューティングシナリオの信頼性解析○蓑田 玲緒奈・石畠 正和・湊 真一

北海道大学大学院情報科学研究科

今日の話: UCシナリオの検証に確率を導入• UCシナリオ検証に確率を導入する動機 → 不確実性
• ユーザーが順路に従わないかもしれない🤔

• 連携が（様々な要因で）失敗するかもしれない🤔

• 形式検証: Deterministicな検証→性質を満たす or 満たさない

信頼性解析: 性質を満たす確率を計算→信頼性を測る指標

Separate Compilation of Bayesian
Network for Efficient Exact
Inference
高サン 石畠正和 湊真一
北海道大学情報科学研究科, 基盤(S)離散構造処理系プロジェクト

背景：ベイジアンネットワーク（BN）の確率推論を高速化するために、与えられたBN をZDD（Zero-suppressed BDD) にコンパイルして、ZDD上で高速に計算する技法が知られている。
問題：この方法により、コンパイル後のZDDサイズに比例する計算時間で高速に確率推論が可能となるが、中規模以上のBNに対してはZDDサイズが非常に大きくなり、現実的な計算時間や記憶量で処理できなくなる場合があった。

提案手法
Ø与えられたBNをいくつかの成分に分割し、それぞれの成分をZDDにコンパイルして確率推論計算を行い、最後に計算結果を合成する手法について述べる
d－分離

Xd

X1

X2

Xd

X1

Xd

X2

既存手法：

提案手法：

P( X1 , X d , X 2 )P( X 2 | X d ) P( X1 , X d )
ZDD

ZDD
0

1

0

ZDD
1

0

1

üTotal Table Joint Size(TTJS)を尺度としてd－分離を選ぶ
ü分割の回数と計算時間のトレードオフをユーザが適切に見積もるための手法を示す
ü確率推論計算のための計算時間や記憶量を、多くの例題において従来よりも大幅に改善できることが示された。

𝑘-ペア間最大距離最小化: Simpath の応用
北海道大学 鈴木 浩史
𝑘-ペア間最大距離最小化問題
有向・無向は入力問わない
グラフ
𝐺 = (𝑉, 𝐸)
ZDD形式
辺部分集合の族 𝒳 ⊆ 2𝐸
頂点ペア集合𝐶 = 𝑠1 , 𝑡1 , … , 𝑠𝑘 , 𝑡𝑘 ,𝑠𝑖 , 𝑡𝑖 ⊆ 𝑉 2 (𝑖 = 1, … , 𝑘)

出力𝒳 ∗ = arg min 𝑓(𝑋)
𝑋∈𝒳

部分グラフ
上での距離

𝑓 𝑋 = max 𝑑𝑠𝑡(𝐺 𝑋 ; 𝑠𝑖 , 𝑡𝑖 )𝑖=1,…,𝑘2017/12/25

WINTER FESTA 2017

𝐺 = (𝑉, 𝐸)

𝒳 ⊆ 2𝐸𝒳∗

𝑘-ペア間最大距離最小化問題をSimpathを利用して厳密に解く

最小直径シュタイナー木問題（既知のNP-困難問題）を含む

高速なパス列挙
アルゴリズム列挙結果をZDDで出力
考慮すべき
パスを列挙

Simpathで得たZDDと、ZDDが持つ集合演算・重み総和
最適化の機能を活用
最小直径シュタイナー木問題で実験

詳細・実験結果はポスターで2017/12/25…
WINTER FESTA 2017…