部分グラフ与えられたグラフの一部分からなるグラフ与えられたグラフ経路 ( パス ) や全域木などは部分グラフ部分グラフの例部分グラフ列挙与えられた条件を満たす部分グラフをすべて求める例 : からまでの同じ頂点を通らない経路は? - 経路 (- パス ) 全域木 5 6 部分グラフ列

Size: px

Start display at page:

Download "部分グラフ与えられたグラフの一部分からなるグラフ与えられたグラフ経路 ( パス ) や全域木などは部分グラフ部分グラフの例部分グラフ列挙与えられた条件を満たす部分グラフをすべて求める例 : からまでの同じ頂点を通らない経路は? - 経路 (- パス ) 全域木 5 6 部分グラフ列"

れんまおおかわち
6 years ago
Views:

1 graphillion - 莫大な数の部分グラフを扱う Pyhon ライブラリ奈良先端科学技術大学院大学川原純謝辞本スライドで使用している図の一部と全適用事例は発売予定の書籍超高速グラフ列挙アルゴリズム ( 仮題 ) のドラフト版から引用しています図の引用はと明示しています graphillion ライブラリの作者井上武さん, 岩下洋哲さん書籍の著者湊真一先生, 斎藤寿樹先生, 安田宜仁さん, 井上武さん, 羽室行信先生, 前川浩基さん, 丸橋弘明さん, 堀山貴史先生, その他の著者の皆様, JST ERATO 湊離散構造処理系プロジェクトメンバーの皆様に感謝いたします今日の内容 graphillion ライブラリの紹介 graphillion ライブラリでできること graphillion の内部データ構造 ZDD graphillion が使用しているアルゴリズムフロンティア法適用事例紹介 (), (2), (3) 2 graphillion とは部分グラフ列挙ツールグラフに関する様々な最適化問題を解く hp://graphillion.org NTT 研究所井上武氏作 graphillion とは部分グラフ列挙ツールグラフに関する様々な最適化問題を解くグラフとは hp://graphillion.org NTT 研究所井上武氏作頂点辺路線図地図 ( の隣接関係 ) グラフ 3 知り合い関係ものともののつながりを抽象化して表したもの 4

部分グラフ与えられたグラフの一部分からなるグラフ与えられたグラフ経路 ( パス )

与えられた条件を満たす部分グラフをすべて求める例 : 全体グラフ (univr) 部分グラフ

2 部分グラフ与えられたグラフの一部分からなるグラフ与えられたグラフ経路 ( パス ) や全域木などは部分グラフ部分グラフの例部分グラフ列挙与えられた条件を満たす部分グラフをすべて求める例 : からまでの同じ頂点を通らない経路は? - 経路 (- パス ) 全域木 5 6 部分グラフ列挙与えられた条件を満たす部分グラフをすべて求める例 : 全体グラフ (univr) 部分グラフからまでの同じ頂点を通らない経路は? 部分グラフ列挙与えられた条件を満たす部分グラフをすべて求める例 : 全体グラフ (univr) 列挙して何が嬉しいのか? 後述 7 8

3 graphillion を使ってみよう () インストール (Ma, Linux) $ ay_inall graphillion pyhon インタプリタを起動 $ pyhon ライブラリのインポート >>> from graphillion impor GraphS または hp://graphillion.org からダウンロードビルド 9 graphillion を使ってみよう (2) グラフの表現 nworkx ライブラリと同じ頂点 : オブジェクト ( 何でもよい ) 辺 : 頂点のタプル全体グラフの設定本講演では,2,3, (, 2) や (2, 3) など全体グラフ (univr) = グラフ : 辺のリスト [(, 2), (, 4), (2, 3), (2, 5), (3, 6), (4, 5), (4, 7), (5, 6), (5, 8), (6, 9), (7, 8), (8, 9)] = 9 >>> GraphS._univr( [(, 2), (, 4), (2, 3), (2, 5), (3, 6), (4, 5), (4, 7),(5, 6), (5, 8), (6, 9), (7, 8), (8, 9)] ) graphillion を使ってみよう (3) - 経路を列挙する全体グラフ (univr) 2 3 = = 9 >>> pah = GraphS.pah(, 9) 引数に始点と終点 pah 変数に部分グラフの集合が格納される graphillion でできること () 数のカウント各部分グラフに対する処理 >>> for p in pah: prin p >>> prin pah.ln() 2 全体グラフ (univr) 2 3 = = 9 2

4 graphillion でできること () 数のカウント >>> prin pah.ln() 2 各部分グラフに対する処理全体グラフ (univr) 2 3 = >>> for p in pah: prin p [(, 2), (2, 3), (3, 6), (4, 5), (4, 7), (5, 6), (7, 8), (8, 9)] [(, 2), (2, 3), (3, 6), (5, 6), (5, 8), (8, 9)] [(, 2), (2, 3), (3, 6), (6, 9)] [(, 2), (2, 5), (4, 5), (4, 7), (7, 8), (8, 9)] [(, 2), (2, 5), (5, 6), (6, 9)] [(, 2), (2, 5), (5, 8), (8, 9)] [(, 4), (2, 3), (2, 5), (3, 6), (4, 5), (6, 9)] [(, 4), (2, 3), (2, 5), (3, 6), (4, 7), (5, 8), (6, 9), (7, 8)] [(, 4), (4, 5), (5, 6), (6, 9)] [(, 4), (4, 5), (5, 8), (8, 9)] [(, 4), (4, 7), (5, 6), (5, 8), (6, 9), (7, 8)] [(, 4), (4, 7), (7, 8), (8, 9)] = 9 3 graphillion でできること (2) 経路の短い順に各部分グラフを処理全体グラフ (univr) 2 3 = >>> for p in pah.min_ir(): prin p [(, 4), (4, 7), (7, 8), (8, 9)] [(, 4), (4, 5), (5, 8), (8, 9)] [(, 4), (4, 5), (5, 6), (6, 9)] [(, 2), (2, 5), (5, 8), (8, 9)] [(, 2), (2, 5), (5, 6), (6, 9)] [(, 2), (2, 3), (3, 6), (6, 9)] [(, 4), (4, 7), (5, 6), (5, 8), (6, 9), (7, 8)] [(, 4), (2, 3), (2, 5), (3, 6), (4, 5), (6, 9)] [(, 2), (2, 5), (4, 5), (4, 7), (7, 8), (8, 9)] [(, 2), (2, 3), (3, 6), (5, 6), (5, 8), (8, 9)] [(, 4), (2, 3), (2, 5), (3, 6), (4, 7), (5, 8), (6, 9), (7, 8)] [(, 2), (2, 3), (3, 6), (4, 5), (4, 7), (5, 6), (7, 8), (8, 9)] 4 = 9 graphillion でできること (3) ( 一様 ) ランダムにつ抽出 >>> p = pah.hoi() >>> prin p 7 8 [(, 2), (2, 3), (3, 6), (4, 5), (4, 7), (5, 6), (7, 8), (8, 9)] 頂点 5 を通る経路のみを抽出全体グラフ (univr) 2 3 = = 9 graphillion でできること (4) さらに頂点 3 を通らない経路のみを抽出 >>> pah3 = pah2.xluding(3) 全体グラフ (univr) 2 3 = = 9 >>> pah2 = pah.inluding(5) 5 6

5 graphillion でできること (5) 辺に重みをつけて重みの和が最大最小の部分グラフを求める >>> wigh = {} >>> wigh[(, 2)] = 3.2 >>> wigh[(, 4)] =.7 # ( 略 ) >>> wigh[(8, 9)] = 6.2 >>> >>> ir = pah3.max_ir(wigh) >>> p = ir.nx() >>> p2 = ir.nx() 全体グラフ (univr) 2 3 = 一番長い経路二番目に長い経路辺の重みは辺をキー重みをバリューとするディクショナリで与える = graphillion の威力 () JR(Japan Railway) の路線図頂点数 : 4534, 辺数 : 4646 最北駅 ( 稚内 )~ 最南駅 ( 西大山 ) の経路 >>> GraphS._univr(jrmap) >>> wigh = rad_wigh() >>> >>> pah = GraphS.pah( 553, 932 ) >>> pah.ln() 計算時間 : 秒使用メモリ : 2.4 GB 経路は圧縮して保持されている Inl Xon E GHz データ取得 : 駅データ.jp hp://kidaa.jp 7 8 graphillion の威力 (2) JR(Japan Railway) の路線図頂点数 : 4534, 辺数 : 4646 最長経路を求める最北駅 ( 稚内 )~ 最南駅 ( 西大山 ) の経路 >>> max_pah = pah.max_ir(wigh).nx() >>> prin ln(max_pah) 265 >>> um =. >>> for dg in max_pah: um += wigh[dg] >>> prin um 駅数総距離最短経路も求まるがダイクストラ法などの既存アルゴリズムの方が速い 9 graphillion で扱える部分グラフの種類経路 - 経路ハミルトン経路 ( すべての頂点を通る ) サイクル ( 周して戻る ) 木森全域森木全域木連結成分マッチングクリーク ( 頂点同士がすべて結ばれている頂点集合 ) その他様々な制約を課した部分グラフ 2

6 今日の内容 graphillion ライブラリの紹介 graphillion ライブラリでできること graphillion の内部データ構造 ZDD graphillion が使用しているアルゴリズムフロンティア法適用事例紹介 (), (2), (3) 2 graphillion で用いられるデータ構造 Zro-upprd Binary Diion Diagram (ZDD) 集合族 ( 集合の集合 ) をコンパクトに効率良く記憶 {, 2, 5}, {, 3, 4, 7}, {, 5, 8, 2}, {3, 7, 9}, {2, 6, 7, 8, 9, }, {4}, {, 4, 6, 8}, {, 2, 5, 8}, {, 9, }, {4, 5, 9}, {, 3, 4, 5, 9, }, {6, 7}, {, 4, 5}, {, 5, 8, }, {2, 5, }, {5, 8, 9}, {2, 3, 7, 8}, {,, 2}, ゼロサプレス型二分決定グラフ特殊な形をしたグラフ ZDD [S.Minao 93] 22 ZDD の基本 ZDD の基本 roo 4 { { }, { }, { } { 4 }, { }, { } } 4 { { }, { }, { 4 } { 4 }, { }, { } } 4 集合族 : 終端 (-rminal) : 終端 (-rminal) それぞれつずつもつ ZDD 要素は {,,, 4, } の 5 種類で固定 ( 事前に固定する必要あり ) 23 i : ノード ~,,, の順序いずれかのラベル ZDD 24

7 ZDD の基本 ZDD の基本ノードは枝と枝をつずつもつ roo ノードは枝と枝をつずつもつ roo { { }, { }, { 4 } { 4 }, { }, { } } 4 { { }, { }, { 4 } { 4 }, { }, { } } 4 : 終端 (-rminal) : 終端 (-rminal) それぞれつずつもつつの集合が roo からまでの本のパスに対応 i : ノード ~,,, の順序いずれかのラベル ZDD 25 : -rminal : -rminal i : nod wih labl ~ ZDD 26 ZDD の基本 ZDD の基本ノードは枝と枝をつずつもつ roo ノードは枝と枝をつずつもつ roo { { }, { }, { 4 } { 4 }, { }, { } } 4 { { }, { }, { 4 } { 4 }, { }, { } } 4 つの集合が roo からまでの本のパスに対応つの集合が roo からまでの本のパスに対応 : -rminal ZDD : -rminal ZDD : -rminal i : nod wih labl ~ 27 : -rminal i : nod wih labl ~ 28

8 ZDD の基本 ZDD は2 分木を圧縮したものとみなすことができる { { }, { , 5 } { }, { } { 5 }, { } } = = ZDD の基本ノード共有ルール = = = = { } { } 他は 4 4 ZDD 29 2 種類のルールを繰り返し適用して圧縮 2 つの等価なノードは共有されるゼロサプレスルール i - 枝が -Trminal を指すノードは削除される 3 ZDD の演算 ZDD を用いると集合演算や要素の検索等様々な演算が効率良く行える {, 2, 5}, {, 4}, {, 3, 4, 7} {, 3, 4, 7} {, 2, 5}, {, 4} {, 3, 4, 7} {, 2, 5}, {, 4} {, 3, 4, 7} {, 4} {, 3, 4, 7} 和集合を求める (union) 要素の抽出 4 を含む集合を取り出す 3 アルゴリズムは省略今日の内容 graphillion ライブラリの紹介 graphillion ライブラリでできること graphillion の内部データ構造 ZDD graphillion が使用しているアルゴリズムフロンティア法適用事例紹介 (), (2), (3) - 経路を例に説明 32

9 - 経路は辺の集合で表現できる - 経路は辺の集合で表現できる 4 4 全ての - 経路を列挙して辺集合の集合で表す 4 4 {, 4 } {, } 4 4 {, 4 } {, } 4 4 {,, } {,, 4 } 4 4 {,, } {,, 4 } 経路は辺の集合で表現できる 4 全ての - 経路を列挙して辺集合の集合で表す全 - 経路の集合 = {{, 4 },{, },{,, },{,, 4 }} - 経路は辺の集合で表現できる 4 全ての - 経路を列挙して辺集合の集合で表すこれをZDDで表現する全 - 経路の集合 = {{, 4 },{, },{,, },{,, 4 }} 4 4 {, 4 } {, } 4 4 {, 4 } {, } 4 4 {,, } {,, 4 } 4 4 {,, } {,, 4 } 35 36

10 経路列挙 (ZDD 構築 ) アルゴリズム [Knuh 8] 経路列挙 (ZDD 構築 ) アルゴリズム [Knuh 8] 4. 辺に順番を付ける ( 例えばから幅優先 ) ( もっと良い方法もあり ) = = = = = = 4 4. 辺に順番を付ける ( 例えばから幅優先 ) ( もっと良い方法もあり ) = = = = = = 4 2. ZDD を構築辺,, の順に処理各辺変数 i に対し i = or を決めていく - pah 4 i = である辺が - 経路になっているか? ZDD を構築辺,, の順に処理各辺変数 i に対し i = or を決めていく - 経路でない - pah + 余分な辺 4 4 i = である辺が - 経路になっているか? 38 経路列挙 (ZDD 構築 ) アルゴリズム [Knuh 8] 4. 辺に順番を付ける ( 例えばから幅優先 ) ( もっと良い方法もあり ) = = = = = = 4 経路列挙 (ZDD 構築 ) アルゴリズム [Knuh 8] a 2 b ZDD を構築辺,, の順に処理他は各辺変数 i に対し i = or を決めていく 39 4

11 経路列挙 (ZDD 構築 ) アルゴリズム [Knuh 8] a 2 b 4 6 経路列挙 (ZDD 構築 ) アルゴリズム [Knuh 8] 処理済み辺未処理辺 f d d a a b f h b g d f g f d h フロンティア部分経路の反対側の端点を記憶しておきフロンティア上ですべて一致するなら 2 つは同じ状態とみなす 4 42 ZDD の形式で保存 ZDD が構築できれば経路の全列挙は簡単 op から - 終端までたどればよい構築した ZDD はコンパクトなのでそのまま保持可能 ZDD 演算を行うことで経路の条件付き検索が可能経路の数え上げ {, 2, 5}, {, 4} {, 3, 4, 7} {, 4} {,3, 4, 7} 4 を通る経路のみを取り出す 43 重み付き和の最大値最小値も同様の方法で行える 44

12 一様ランダムサンプリング b a a 3 b 確率 6 7 b 確率 7 3 b 一様ランダムサンプリング b a b 確率 3 6 b 確率 d d 2 {d}, {}, {, d}, {b}, {b, d}, {b,, d}, {a}, {a, d}, {a,, d}, {a, b}, {a, b, }, {a, b, d}, {a, b,, d} d d 2 {d}, {}, {, d}, {b}, {b, d}, {b,, d}, {a}, {a, d}, {a,, d}, {a, b}, {a, b, }, {a, b, d}, {a, b,, d} 一様ランダムサンプリング {b, d} b d a b d 2 {d}, {}, {, d}, {b}, {b, d}, {b,, d}, {a}, {a, d}, {a,, d}, {a, b}, {a, b, }, {a, b, d}, {a, b,, d} 47 graphillion で扱える部分グラフの種類経路 - 経路ハミルトン経路 ( すべての頂点を通る ) サイクル ( 周して戻る ) 木森全域森木全域木連結成分マッチングクリーク ( 頂点同士がすべて結ばれている頂点集合 ) その他様々な制約を課した部分グラフ ( 再掲 ) フロンティア法は Knuh のアルゴリズム (- 経路 ) を様々な部分グラフに適用できるように拡張したもの 48

適用事例 : パズルソルバーナンバーリンク適用事例 -: ナンバーリンクソルバー /4 グラフの問題として定式化 - 経路 2-2 経路 p-p 経路 ( 複数終端対経路 ) を同時に求める問題同じ数字同士を線を交差させずに結ぶ R. Yohinaka, T. Saioh, J. Kawahara, K. Turuma, H. Iwahia, S. Minao.

13 適用事例 : パズルソルバーナンバーリンク適用事例 -: ナンバーリンクソルバー /4 グラフの問題として定式化 - 経路 2-2 経路 p-p 経路 ( 複数終端対経路 ) を同時に求める問題同じ数字同士を線を交差させずに結ぶ R. Yohinaka, T. Saioh, J. Kawahara, K. Turuma, H. Iwahia, S. Minao. Finding all oluion and inan of numbrlink and lihrlink by ZDD. Algorihm, 5, 76 23, 適用事例 -: ナンバーリンクソルバー 2/4 graphillion には直接複数終端対経路を求めるメソッドはない条件をつけた部分グラフを求めるメソッドを使う 5 適用事例 -: ナンバーリンクソルバー 3/4 次数の条件終端 (i, i) の次数はそれ以外の次数はまたは 2 >>> univr = [] >>> GraphS._univr(univr) >>> poin_pair = [[2, 6], [, ], [3, 22]] >>> poin = um(poin_pair, []) >>> [2, 6,,, 3, 22] >>> dg_on = di([(v, ) for v in (rang(, 37)) if v in poin]) >>> dg_on.upda(di([(v, (, 2)) for v in (rang(, 37)) if v no in poin])) {:, 2:, 3:, 4: (, 2), 5: (, 2), 6:, 52

14 適用事例 -: ナンバーリンクソルバー 4/4 [[2, 6], [, ], [3, 22]] >>> oluion = GraphS.graph( vrx_group=poin_pair, dgr_onrain=dg_on, no_loop=tru) >>> >>> prin oluion.ln() 適用事例 -2: スリザーリンクソルバー /4 スリザーリンクサイクルを個作る書かれている数字の本数の辺を使う得られた解 {:, 2:, 3:, 4: (, 2), 5: (, 2), 6:, 適用事例 -2: スリザーリンクソルバー 2/4 初めにマスの数字は無視してサイクルをすべて求める >>> univr = [] >>> GraphS._univr(univr) >>> >>> yl = GraphS.yl() 適用事例 -2: スリザーリンクソルバー 3/4 次にあるつのマスに着目そのマスの制約を満たしている部分グラフのみを抽出 >>> = (5, 6) >>> 2 = (5, 23) >>> 3 = (6, 24) >>> 4 = (23, 24) >>> from irool impor ombinaion >>> g_ = li(ombinaion([, 2, 3, 4], 2)) >>> in_g = GraphS(g_) >>> yl = yl.inluding(in_g)

15 適用事例 -2: スリザーリンクソルバー 4/4 次にあるつのマスに着目そのマスの制約を満たしている部分グラフのみを抽出 >>> g_2 = li(ombinaion([, 2, 3, 4], 3)) >>> x_g = GraphS(g_2) >>> yl = yl.xluding(x_g) これをすべてのマスについて行う得られた部分グラフが解得られた解適用事例 2: 配電網のスイッチ構成 / 引用 : hp:// 配電網すべての家はちょうどつの変電所につながっている必要があるサイクルが生じてはいけない T. Inou al., Diribuion Lo Minimizaion wih Guarand Error Bound, IEEE Tranaion on Smar Grid, Vol. 5, Iu, 24, pp. 2-. 変電所を根とする根付き全域森 58 適用事例 2: 配電網のスイッチ構成 2/ 根付き全域森を列挙する >>> univr = [] >>> GraphS._univr(univr) >>> for = GraphS.for(roo=[, 9, 73, 8], i_panning=tru) >>> prin for.ln() 適用事例 2: 配電網のスイッチ構成 3/ 電気制約つの変電所が給電可能な最大家庭数に制限がある制限数 5 制限数オーバー 59 6

16 適用事例 2: 配電網のスイッチ構成 4/ 電気制約を満たす根付き全域森を求める制限数 6 >>> all_r = GraphS.r() >>> oo_larg_r = all_r.largr(6) まずは電気制約を満たさない大きな木を求める適用事例 2: 配電網のスイッチ構成 5/ 電気制約を満たす根付き全域森を求める >>> af_for = for.xluding(oo_larg_r) 制限数 6 根付き全域森の集合から電気制約に違反する木を含む根付き全域森を削除 6 62 適用事例 2: 配電網のスイッチ構成 6/ 与えられた構成 ( 根付き全域森 ) が制約を満たすかどうか調べる適用事例 2: 配電網のスイッチ構成 7/ 与えられた構成からスイッチ ON/OFF をいくつか変化させて制約を満たす構成に変化させる >>> unaf_for = [] >>> unaf_for in af_for Fal 2 回 5 回 4 回 63 与えられた構成変化数最小の構成を求めるには? af_for ( 制約を満たす ) 64

17 適用事例 2: 配電網のスイッチ構成 8/ 最適化問題として定式化スイッチを変化させるごとにペナルティーが発生ペナルティーを最小化する構成を求める適用事例 2: 配電網のスイッチ構成 9/ 与えられた構成 ( 根付き全域森 ) が制約を満たすかどうか調べる graphillion では採用した辺にしか重みをつけることはできない与えられた構成 ( 元グラフ ) 元グラフにない辺を採用するとペナルティー + 点 ( 採用しないと点 ) 元グラフにある辺を採用するとペナルティー - 点 ( 採用しないと 65 点 ) >>> unaf_for = [] >>> >>> wigh = {} >>> for wih in univr: wigh[wih] = if wih in unaf_for l - >>> for f in af_for.min_ir(wigh): prin f on_wih = [ for in f if no in unaf_for] off_wih = [ for in unaf_for if no in f] 66 適用事例 2: 配電網のスイッチ構成 / 事例 3: 避難所割り当て /2 bloking (hiing ) 切断によって構成 ( 根付き全域森 ) がなくなるような辺の集合グラフと避難所が与えられたとき避難所ごとにグラフを分割 >>> failur = af_for.bloking() >>> minimal_failur = failur.minimal() 極小のものだけを求めることができる 67 68

18 事例 3: 避難所割り当て 2/2 割当をすべて列挙する 6 >>> univr = [] >>> GraphS._univr(univr) >>> aignmn = GraphS.graph([[], [6], []]) >>> >>> maximal_aignmn = aignmn.maximal(), 6, は同じ連結成分に含まれてはいけないその他の適用事例選挙区割りの列挙多面体の展開図の列挙住宅フロアプランの列挙同じ連結成分内で辺が張れる場合は必ず張る 69 7 まとめ graphillion の紹介内部データ構造とアルゴリズム ZDD フロンティア法適用事例の紹介パズルソルバー ( ナンバーリンクスリザーリンク ) 配電網のスイッチ構成避難所割り当て 7

Microsoft PowerPoint - DA2_2019.pptx

Microsoft PowerPoint - DA2_2019.pptx Johnon のアルゴリズムデータ構造とアルゴリズム IⅠ 第回最大フロー疎なグラフ, 例えば E O( V lg V ) が仮定できる場合に向いている隣接リスト表現を仮定する. 実行時間は O( V lg V + V E ). 上記の仮定の下で,Floyd-Warhall アルゴリズムよりも漸近的に高速 Johnon のアルゴリズム : アイデア (I) 辺重みが全部非負なら,Dikra