Download presentation
Presentation is loading. Please wait.
1
フロンティア法 - 組合せ問題の解を列挙索引化するZDD構築アルゴリズム
川原 純 科学技術振興機構 ERATO湊離散構造処理系プロジェクト 北海道大学 情報科学研究科
2
講義の目標 パスの数え上げアルゴリズムを理解する 大規模データを扱うためのデータ構造の1つ 「ZDD」 についてより詳しく知る
大規模データの保存、活用 様々な対象を表現するZDDを高速に構築する手法 「フロンティア法」 アルゴリズムを理解する 適用事例について知る
3
ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
(Zero-suppressed Binary Decision Diagram) [S.Minato 93] 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 ZDD
4
ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ZDD ei e1 e5 : ノード ～ いずれかのラベル e1 , e2 ,… , e5 の順序
5
ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ZDD ei e1 e5 : ノード ～ いずれかのラベル e1 , e2 ,… , e5 の順序
6
ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 1つの集合が、 top から までの1本のパスに対応 1 ZDD : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ei e1 e5 : ノード ～ いずれかのラベル
7
ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 1つの集合が、 top から までの1本のパスに対応 1 ZDD : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ei e1 e5 : ノード ～ いずれかのラベル
8
ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 1つの集合が、 top から までの1本のパスに対応 1 ZDD : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ei e1 e5 : ノード ～ いずれかのラベル
9
ZDDの性質 e1 e1 1 1 e2 e2 e2 e3 e3 e4 e4 e5 e5 1 1 等価な2つのノードは必ず共有される
10
パスは辺の集合で表現できる e1 e4 s t e3 e2 e5 e1 e1 e4 e4 s t s t e3 e3 {e1, e4}
11
パスは辺の集合で表現できる e1 e4 全ての s-t パスを列挙して、 s t e3 辺集合の集合で表す e2 e5 e1 e1 e4
12
パスは辺の集合で表現できる e1 e4 s t 全ての s-t パスを列挙して、 e3 辺集合の集合で表す e2 e5
all s-t path = {{e1, e4}, {e2, e5}, {e1, e3 ,e5}, {e2, e3 ,e4}} e1 e4 e1 e4 s t s t e3 {e1, e4} e3 {e2, e5} e2 e5 e2 e5 e1 e1 e4 e4 s t s t e3 e3 {e2, e3 ,e4} {e1, e3 ,e5} e2 e2 e5 e5
13
Knuth のパス列挙アルゴリズム 全 s-t パスを表現する ZDD をトップダウン的に構築 ZDD
14
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e4 e1 e1 = 1 e1 = 0 s t e3 e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e5 e3 e3 e3 e3 1 1. 辺に順番を付ける （例えば、s から幅優先） e4 （もっと良い方法もあり） e5 2. ZDDを構築 辺 e1, e2,… の順に処理 s-t パスになっている 1 s e1 t e2 e3 e4 e5 各辺変数 ei に対し、 ei = 0 or 1 を決めていく ei = 1 である辺が s-t パスになっているか？
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/14/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "e1. e4. e1. e1 = 1. e1 = 0. s. t. e3. e2. e2. e2 = 0. e2 = 1. e2 = 0. e2 = 1. e2. e5. e3. e3. e3. e 辺に順番を付ける. （例えば、s から幅優先） e4. （もっと良い方法もあり） e5. 2. ZDDを構築. 辺 e1, e2,… の順に処理. s-t パスになっている. 1. s. e1. t. e2. e3. e4. e5. 各辺変数 ei に対し、 ei = 0 or 1 を決めていく. ei = 1 である辺が s-t パスになっているか？")
15
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e4 e1 e1 = 1 e1 = 0 s t e3 e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e5 e3 e3 e3 e3 1 1. 辺に順番を付ける （例えば、s から幅優先） e4 （もっと良い方法もあり） e5 2. ZDDを構築 s-t パスに なっていない s-t パス + 余分な辺 辺 e1, e2,… の順に処理 s e1 t e2 e3 e4 e5 s e1 t e2 e3 e4 e5 各辺変数 ei に対し、 ei = 0 or 1 を決めていく ei = 1 である辺が s-t パスになっているか？
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/15/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "e1. e4. e1. e1 = 1. e1 = 0. s. t. e3. e2. e2. e2 = 0. e2 = 1. e2 = 0. e2 = 1. e2. e5. e3. e3. e3. e 辺に順番を付ける. （例えば、s から幅優先） e4. （もっと良い方法もあり） e5. 2. ZDDを構築. s-t パスに. なっていない. s-t パス + 余分な辺. 辺 e1, e2,… の順に処理. s. e1. t. e2. e3. e4. e5. s. e1. t. e2. e3. e4. e5. 各辺変数 ei に対し、 ei = 0 or 1 を決めていく. ei = 1 である辺が s-t パスになっているか？")
16
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e4 e1 e1 = 1 e1 = 0 s t e3 e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e5 e3 e3 e3 e3 1 1. 辺に順番を付ける （例えば、s から幅優先） e4 （もっと良い方法もあり） e5 2. ZDDを構築 辺 e1, e2,… の順に処理 1 1 1 1 他は0 各辺変数 ei に対し、 ei = 0 or 1 を決めていく 1 が1つのパスに対応
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/16/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "e1. e4. e1. e1 = 1. e1 = 0. s. t. e3. e2. e2. e2 = 0. e2 = 1. e2 = 0. e2 = 1. e2. e5. e3. e3. e3. e 辺に順番を付ける. （例えば、s から幅優先） e4. （もっと良い方法もあり） e5. 2. ZDDを構築. 辺 e1, e2,… の順に処理 他は0. 各辺変数 ei に対し、 ei = 0 or 1 を決めていく. 1. が1つのパスに対応.")
17
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e3 e1 e1 = 1 e1 = 0 s t e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e4 e3 e3 e3 1 1
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/17/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "e1. e3. e1. e1 = 1. e1 = 0. s. t. e2. e2. e2 = 0. e2 = 1. e2 = 0. e2 = 1. e2. e4. e3. e3. e")
18
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e3 e1 e1 = 1 e1 = 0 s t e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e4 e3 e3 e3 1 1 ノードを共有できるときは共有したい ただし、子DAGを作成せずに、共有可能か判定を行う
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/18/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "e1. e3. e1. e1 = 1. e1 = 0. s. t. e2. e2. e2 = 0. e2 = 1. e2 = 0. e2 = 1. e2. e4. e3. e3. e ノードを共有できるときは共有したい. ただし、子DAGを作成せずに、共有可能か判定を行う.")
19
パス列挙（ZDD構築）アルゴリズム [Knuth 08] s t
e1 e3 パス列挙（ZDD構築）アルゴリズム [Knuth 08] s t e2 e4 e1 = 0 e1 = 1 e2 = 0 e2 = 1 ? e1 = 0 e1 = 1 e2 = 1 e2 = 0 途中の経路は分からないが s につながっていることは分かっている
![パス列挙（ZDD構築）アルゴリズム [Knuth 08] s t](http://slidesplayer.net/slide/11273961/61/images/19/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+s+t.jpg "e1. e3. パス列挙（ZDD構築）アルゴリズム [Knuth 08] s. t. e2. e4. e1 = 0. e1 = 1. e2 = 0. e2 = 1. e1 = 0. e1 = 1. e2 = 1. e2 = 0. 途中の経路は分からないが. s につながっていることは分かっている.")
20
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
s t … … 未処理辺 処理済み辺 t フロンティア
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/20/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "s. t. … … 未処理辺. 処理済み辺. t. フロンティア.")
21
… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d a t s f c b h g f f d d d d a s a s
![… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d a t s f c b h g f f d d d d a s a s](http://slidesplayer.net/slide/11273961/61/images/21/%E2%80%A6+%E2%80%A6+%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+d+a+t+s+f+c+b+h+g+f+f+d+d+d+d+a+s+a+s.jpg "… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d a t s f c b h g f f d d d d a s a s")
22
… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d f a t s d f a c s b t h g c b h g f
![… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d f a t s d f a c s b t h g c b h g f](http://slidesplayer.net/slide/11273961/61/images/22/%E2%80%A6+%E2%80%A6+%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+d+f+a+t+s+d+f+a+c+s+b+t+h+g+c+b+h+g+f.jpg "… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d f a t s d f a c s b t h g c b h g f")
23
mate 配列 … … パス列挙（ZDD構築）アルゴリズム [Knuth 08] 接続情報の記憶法 d 頂点がパスの端 a a t s
逆端の頂点 f c s b … b h 頂点がパスの途中 g 頂点がいずれの パスにも含まれない v d f g v a b 自身の頂点 mate[v] mate[v] f d s a 0 mate 配列
![mate 配列 … … パス列挙（ZDD構築）アルゴリズム [Knuth 08] 接続情報の記憶法 d 頂点がパスの端 a a t s](http://slidesplayer.net/slide/11273961/61/images/23/mate+%E9%85%8D%E5%88%97+%E2%80%A6+%E2%80%A6+%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+%E6%8E%A5%E7%B6%9A%E6%83%85%E5%A0%B1%E3%81%AE%E8%A8%98%E6%86%B6%E6%B3%95+d+%E9%A0%82%E7%82%B9%E3%81%8C%E3%83%91%E3%82%B9%E3%81%AE%E7%AB%AF+a+a+t+s.jpg "逆端の頂点. f. c. s. b. … b. h. 頂点がパスの途中. g. 頂点がいずれの. パスにも含まれない. v. d f g. v. a b. 自身の頂点. mate[v] mate[v] f d s. a 0. mate 配列.")
24
パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 a s b e6 e4 s a c
mate 値 a s b e6 e4 s a c b a s a a b b s s a s b s s s a c s c s s
![パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 a s b e6 e4 s a c](http://slidesplayer.net/slide/11273961/61/images/24/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+a+e1+e5+s+t+e3+e2+a+s+b+e6+e4+s+a+c.jpg "mate 値. a. s. b. e6. e4. s. a. c. b. a. s. a. a. b. b. s. s. a. s. b. s. s. s. a. c. s. c. s. s.")
25
パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 a s b e6 e4 s a c
mate 値 a s b e6 e4 s a c a a b s b a s s b s a s a b s s s c s
![パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 a s b e6 e4 s a c](http://slidesplayer.net/slide/11273961/61/images/25/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+a+e1+e5+s+t+e3+e2+a+s+b+e6+e4+s+a+c.jpg "mate 値. a. s. b. e6. e4. s. a. c. a. a. b. s. b. a. s. s. b. s. a. s. a. b. s. s. s. c. s.")
26
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
a e1 e5 s t e3 e2 b e6 e4 c s a s c s s a c t s
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/26/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "a. e1. e5. s. t. e3. e2. b. e6. e4. c. s. a. s. c. s. s. a. c. t. s.")
27
パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c
s a s c s a t 1 s c s 1 1
![パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c](http://slidesplayer.net/slide/11273961/61/images/27/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+a+e1+e5+s+t+e3+e2+b+e6+e4+c.jpg "s. a. s. c. s. a. t. 1. s. c. s")
28
パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c
s a 根から までの 1つの経路が 1 つのs-t パスに 対応する 1 s c s a t 1 s c s 1 1
![パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c](http://slidesplayer.net/slide/11273961/61/images/28/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+a+e1+e5+s+t+e3+e2+b+e6+e4+c.jpg "s. a. 根から までの. 1つの経路が. 1 つのs-t パスに. 対応する. 1. s. c. s. a. t. 1. s. c. s")
29
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
mate 配列の更新例 a a g g b b s c s c d d f f v a b c d f v a b c d f g mate[v] c a d s mate[v] g d s c
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/29/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "mate 配列の更新例. a. a. g. g. b. b. s. c. s. c. d. d. f. f. v. a b c d f. v. a b c d f g. mate[v] c 0 a d s. mate[v] 0 0 g d s c.")
30
パス列挙（ZDD構築）アルゴリズム [Knuth 08]
mate 配列の更新 一般に a b c d c d a b c d a b a b c d d c 最大4か所書きかえれば更新できる
![パス列挙（ZDD構築）アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/30/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%EF%BC%88ZDD%E6%A7%8B%E7%AF%89%EF%BC%89%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "mate 配列の更新. 一般に. a b c d. c. d. a. b. c d a b. a b c d. 0 0 d c. 最大4か所書きかえれば更新できる.")
31
パス列挙アルゴリズム [Knuth 08]
![パス列挙アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/31/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "パス列挙アルゴリズム [Knuth 08]")
32
枝刈り a a b c s g d f g b s c d f
33
枝刈り a a b c s g d f g b s c d f
34
枝刈り a a b c s g d f t g b s c d t f
35
枝刈り 1 a a b c s g d f t g b s c d t f
36
パス列挙アルゴリズム [Knuth 08]
![パス列挙アルゴリズム [Knuth 08]](http://slidesplayer.net/slide/11273961/61/images/36/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D.jpg "パス列挙アルゴリズム [Knuth 08]")
37
p q 終端判定条件 辺 e を処理する前の判定 if x = 1
if GetDegree(p) = 2 or GetDegree(q) = 2 終端 if (p = s or p = t) and GetDegree(p) = 1 終端 GetDegree(v) if (q = s or q = t) and GetDegree(q) = 1 if mate[v] == v 終端 return 0 if mate[p] = q and mate[q] = p if mate[v] == 0 終端 return 2 if mate[p] = s and mate[q] = t or else mate[p] = t and mate[q] = s return 1 for each vertex v in the frontier if v != s or v != t or v!= p or v!= q if GetDegree(v) = 1 終端 end for 1 終端 end if
38
a a g g b b s s c c d d f f 辺 e を処理した後の判定
for each v such that v がフロンティアから外れる if v = s or v = t if GetDegree(v) = 0 GetDegree(v) 終端 if mate[v] == v else return 0 if GetDegree(v) = 1 if mate[v] == 0 終端 return 2 else return 1 a a g g b b s c s c d d f f
39
e1 e3 s パスの数え上げ e2 e4 e5 e6 e8 e7 e9 e10 t e11 e12 12 6 6 6 6 2 4 3 3
40
実験結果 s n × n グリッド t 頂点の数 (n + 1) × (n + 1)
・・・ n × n グリッド t 頂点の数 (n + 1) × (n + 1) The On-Line Encyclopedia of Integer Sequence (OEIS) : 数列大辞典
41
実験結果 s n × n グリッド t 頂点の数 (n + 1) × (n + 1)
・・・ n × n グリッド t 頂点の数 (n + 1) × (n + 1) The On-Line Encyclopedia of Integer Sequence (OEIS) : 数列大辞典
42
実験結果 s n × n グリッド t 頂点の数 (n + 1) × (n + 1) n time（秒） 15 206.0 16 701.9
17 2326.0 18 7607.1 19 20 21 実験結果 ・・・ n × n グリッド t 頂点の数 (n + 1) × (n + 1) Thanks to 岩下洋哲氏
43
実験結果 日本地図グラフ 北海道から鹿児島までの全パス 日本地図 47 0.01秒 951 1.4 × 1010 2重化 94
頂点数 計算時間 ZDDノード数 パスの数 日本地図 47 0.01秒 951 1.4 × 1010 2重化 94 248.72秒 18,971,787 5.0 × 1044 本 本 （= 503正9760澗3851溝1518穣9594杼2145垓9492京6092兆3972億3861万6064）
44
講義の目標 パスの数え上げアルゴリズムを理解する 大規模データを扱うためのデータ構造の1つ 「ZDD」 についてより詳しく知る
大規模データの保存、活用 様々な対象を表現するZDDを高速に構築する手法 「フロンティア法」 アルゴリズムを理解する 適用事例について知る
45
ZDD と集合族 集合の集合（集合族）は ZDD で効率よく保持できる a 1 b b {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} c c c d d d 1 1 1 1 は省略
46
ZDD と集合族 集合族への操作例： a を含む集合だけを取り出し、a を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} {{b, c, d}, {c}} a を含まない集合だけ 取り出すなら、LO 枝側を もってこればよい a 1 b b b c c c c c d 1 d d d 1 1 1 1 1 トップの要素なら簡単にできる
47
ZDD と集合族 集合族への操作例： c を含む集合だけを取り出し、c を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} {{a, b, d}, {a}, {b, d}} a a 1 1 b b b b c c c c c c d d d d 1 d d 1 1 1 1 1 1 1 トップでなければ、その変数の深さまで潜って、 枝の付け替えを行う
48
ZDD と集合族 集合族への操作例： c を含む集合だけを取り出し、c を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} {{a, b, d}, {a}, {b, d}} c を含まない集合だけ 取り出すなら、LO 枝の 方に付け替えればよい a a 1 1 b b b b c c c c c c d d d 1 d d 1 d 1 1 1 1 1 1 トップでなければ、その変数の深さまで潜って、 枝の付け替えを行う
49
ZDD と集合族 集合族への操作例： 集合族 F から要素 ｘ を含む集合だけを取り出し、x を消去する F / x 集合族 F から要素 ｘ を含まない集合だけを取り出し、x を消去する F % x {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} abcd + ac + bd + bcd = (abd + a + bd) c + bd c を含む集合だけを取り出し、c を消去する (abcd + ac + bd + bcd ) / c = abd + a + bd c を含む集合だけを取り出し、c を消去する (abcd + ac + bd + bcd ) % c = bd
50
ZDD と集合族 集合族への操作例： a を各要素に追加する {{b, c, d, e}, {b, d}, {c, e}, {c, d}} {{a, b, c, d, e}, {a, b, d}, {a, c, e}, {a, c, d}} a b 1 b c c c c d d d d d d e e e 1 e e e 1 1 1 1 1 1 1 トップに加える場合
51
ZDD と集合族 集合族への操作例： d を各要素に追加する {{a, b, c, d, e}, {a, c, d},
{{a, b, c, e}, {a, c}, {b, e}, {b, c}} {{a, b, c, d, e}, {a, c, d}, {b, d, e}, {b, c, d}} a d が1つも 含まれない場合 a 1 b b b b c c c c c c d d d d e e e 1 e e e 1 1 1 1 1 1 1 間に加える場合
52
ZDD と集合族 集合族への操作例： d を各要素に追加する {{a, b, c, e}, {a, d},
{b, e}, {b, d}} {{a, b, c, d, e}, {a, d}, {b, d, e}, {b, d}} d が含まれる場合 {d} ∪ {d} = {d} である それほど簡単ではない（省略）
53
ZDD と集合族 集合族への操作例： 集合族 F の各要素に ｘ を加える F * x {{a, b, c, e}, {a, d}, {b, e}, {b, d}} abce + ad + be + bd 各要素に d を加える (abce + ad + be + bd) * d = abcde + add + bde + bdd = abcde + ad + bde + bd
54
ZDD と集合族 集合族 F から要素 ｘ を含む集合だけを取り出す（x は消去しない） (F / x) * x {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} abcd + ac + bd + bcd = (abd + a + bd) c + bd c を含む集合だけを取り出す（c は消去しない） ((abcd + ac + bd + bcd ) / c) * c = (abd + a + bd) * c = abcd + ac + bcd
55
ZDD と集合族 F = { {c}, {b, c} , {a}, {a, b}, {a, b, c} } G = { {b}, {b, c}, {a, b} } c + bc + a + ab + abc b + bc + ab a a 1 1 b b b b c c c c 1 1 F ∪ G = { {c}, {b, c} , {a}, {a, b}, {a, b, c}, {b} }
56
F = { {c}, {b, c} , {a}, {a, b}, {a, b, c} }
G = { {b}, {b, c}, {a, b} } c + bc + a + ab + abc b + bc + ab a a 1 1 b b b b c c c c 1 1 (c + bc) a(ε + b + bc) (b + bc) a(b) F ∪ G = (c + bc) ∪ (c + bc) a((ε + b + bc) ∪(b))
57
F G a a 1 1 F0 F1 G0 G1 一般に F = F0 ∪ a * F1 G = G0 ∪ a * G1 のとき F ∪ G = (F0 ∪ G0) ∪ a * (F1 ∪ G1)
58
apply (F, G, ∪) = make_node(a, apply (F0, G0, ∪), apply (F1, G1, ∪))
1 1 1 F0 F1 G0 G1 F0 ∪ G0 F1 ∪ G1 一般に F = F0 ∪ a * F1 G = G0 ∪ a * G1 のとき F ∪ G = (F0 ∪ G0) ∪ a * (F1 ∪ G1) （ノード飛び越しがあると もっと複雑） apply (F, G, ∪) = make_node(a, apply (F0, G0, ∪), apply (F1, G1, ∪)) apply (F, {}, ∪) = F など ∩ や Δ (対称差) なども同様
59
F G F ∪ G a a a 1 1 1 F0 F1 G0 G1 F0 ∪ G0 F1 ∪ G1 最悪計算量は (F のノード数) * (G のノード数) 演算をキャッシュすると高速化できる （実用的には出力ZDDのノード数に線形のことが多い）
60
e1 e3 s F: 全s-t パスを表すZDD e2 e4 e5 e6 e8 e7 e9 e10 t e11 e12 e9 を必ず通る s-t パスの集合は？ (F / e9) * e9 e9 を必ず通らない s-t パスの集合は？ (F % e9) * e9
61
a, b, c, d のうち、 ちょうど3個の要素からなる集合の集合 を表すZDD { {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d} } a 1 b b R(3, 4) と表記する c c c d d d d 1
62
e9 を必ず通る長さが 8 の s-t パスの集合は？
F: 全s-t パスを表すZDD e2 e4 e5 e6 e8 e7 e9 e10 t e11 e12 e9 を必ず通る長さが 8 の s-t パスの集合は？ ((F / e9) * e9) ∩ R(8, 12) （必ずしも効率的とは限らない。 フロンティア法で直接作る方が速いことも）
63
条件付きパス（サイクル）の列挙
64
1 条件付きパス（サイクル）の列挙 e2 e1 e3 e4 f = f + f / e4 % e3 % e2 % e1) * e4
65
一様ランダムサンプリング 確率 確率 a a 1 b b b b c c c d d {d}, {c}, {c, d},
13 7 13 13 6 13 a a 1 6 7 6 7 b b b b 3 4 3 c c c d d 1 2 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} 1
66
一様ランダムサンプリング 確率 確率 a 1 b b b c c c c c d d {d}, {c}, {c, d},
13 確率 確率 a 1 6 3 6 3 6 b 6 7 b b 3 3 3 4 3 c c c c c d d 1 2 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} 1
67
一様ランダムサンプリング {b, d} a 1 b b c c c d d {d}, {c}, {c, d},
13 a 1 6 7 b b 3 4 3 c c c d d 1 2 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} 1
68
講義の目標 パスの数え上げアルゴリズムを理解する 大規模データを扱うためのデータ構造の1つ 「ZDD」 についてより詳しく知る
大規模データの保存、活用 様々な対象を表現するZDDを高速に構築する手法 「フロンティア法」 アルゴリズムを理解する 適用事例について知る
69
フロンティア法とは トップダウンにZDDを構築する技法 e1 e1 = 1 フロンティア e1 = 0 a e2 e2 e2 = 0
t s e3 e3 b 1 c v a b c ノードを共有できるときは共有したい mate[v] 0 s c 各ノードについて、 フロンティア上に 何らかの情報を持たせて、 共有可能性と枝刈りを判定 一般化して configuration と呼ぶ
70
パス列挙アルゴリズム [Knuth 08] (a), (b), (c) がs-tパスの場合の固有の処理
![パス列挙アルゴリズム [Knuth 08] (a), (b), (c) がs-tパスの場合の固有の処理](http://slidesplayer.net/slide/11273961/61/images/70/%E3%83%91%E3%82%B9%E5%88%97%E6%8C%99%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%5BKnuth+08%5D+%28a%29%2C+%28b%29%2C+%28c%29+%E3%81%8Cs-t%E3%83%91%E3%82%B9%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E5%9B%BA%E6%9C%89%E3%81%AE%E5%87%A6%E7%90%86.jpg "パス列挙アルゴリズム [Knuth 08] (a), (b), (c) がs-tパスの場合の固有の処理")
71
ハミルトンパス （全点を通る s-t パス） 辺 e を処理した後の判定
for each v such that v がフロンティアから外れる if v = s or v = t if GetDegree(v) = 0 終端 else if GetDegree(v) = 1 or GetDegree(v) = 0 終端
72
複数終端対パス s2 s1 - t1 パス s1 交差しない の組を全列挙 s2 - t2 パス t3 s3 - t3 パス
si や ti をヒント頂点、 t2 s3 (si , ti) をヒントペアという t1
73
複数終端対パス p q 終端判定条件 辺 e を処理する前の判定 if x = 1
if GetDegree(p) = 2 or GetDegree(q) = 2 終端 GetDegree(v) if (p がヒント頂点) and GetDegree(p) = 1 if mate[v] == v 終端 return 0 if (q がヒント頂点) and GetDegree(q) = 1 if mate[v] == 0 終端 return 2 if mate[p] = q and mate[q] = p else 終端 return 1 if (mate[p] と mate[q] がともにヒント頂点) (mate[p], mate[q]) も (mate[q], mate[p]) もヒントペアではない 終端
74
最後の辺を処理し終えて、 終端でなければ 終端
複数終端対パス 終端判定条件 辺 e を処理した後の判定 for each v such that v がフロンティアから外れる if v がヒント頂点 GetDegree(v) if GetDegree(v) = 0 if mate[v] == v return 0 終端 if mate[v] == 0 else return 2 if GetDegree(v) = 1 else 終端 return 1 最後の辺を処理し終えて、 終端でなければ 終端 1
75
全域木 （本質的には [K.Sekine, H.Imai 95]） サイクルが生じてはいけない 連結成分が2つ以上 生じてはいけない
![全域木 （本質的には [K.Sekine, H.Imai 95]） サイクルが生じてはいけない 連結成分が2つ以上 生じてはいけない](http://slidesplayer.net/slide/11273961/61/images/75/%E5%85%A8%E5%9F%9F%E6%9C%A8+%EF%BC%88%E6%9C%AC%E8%B3%AA%E7%9A%84%E3%81%AB%E3%81%AF+%5BK.Sekine%2C+H.Imai+95%5D%EF%BC%89+%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E3%81%8C%E7%94%9F%E3%81%98%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84+%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%E3%81%8C2%E3%81%A4%E4%BB%A5%E4%B8%8A+%E7%94%9F%E3%81%98%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84.jpg "全域木 （本質的には [K.Sekine, H.Imai 95]） サイクルが生じてはいけない 連結成分が2つ以上 生じてはいけない")
76
フロンティア法（再掲） 枝刈り の設計 configuration の設計
77
全域木 （本質的には [K.Sekine, H.Imai 95]） configuration の設計 a a b b A A c c B
等価 v a b c v a b c mate[v] A A B mate[v] A A B configuration として、各頂点が属する 連結成分のIDを記憶 同じ連結成分に属しているなら同じID 異なる連結成分に属しているなら異なるID
![全域木 （本質的には [K.Sekine, H.Imai 95]） configuration の設計 a a b b A A c c B](http://slidesplayer.net/slide/11273961/61/images/77/%E5%85%A8%E5%9F%9F%E6%9C%A8+%EF%BC%88%E6%9C%AC%E8%B3%AA%E7%9A%84%E3%81%AB%E3%81%AF+%5BK.Sekine%2C+H.Imai+95%5D%EF%BC%89+configuration+%E3%81%AE%E8%A8%AD%E8%A8%88+a+a+b+b+A+A+c+c+B.jpg "等価. v. a b c. v. a b c. mate[v] A A B. mate[v] A A B. configuration として、各頂点が属する. 連結成分のIDを記憶. 同じ連結成分に属しているなら同じID. 異なる連結成分に属しているなら異なるID.")
78
全域木 （本質的には [K.Sekine, H.Imai 95]） 枝刈りの設計 a a b A b A c c B B v a b c a
同じ連結成分を 両端とする辺を加えるとき、 サイクルができる a a b A b に接続 A c c B B 加えない v a b c a mate[v] A A B 孤立成分が 生じる b A 最後の辺まで処理後、 0 に接続されないなら に接続 c B 1 に接続
![全域木 （本質的には [K.Sekine, H.Imai 95]） 枝刈りの設計 a a b A b A c c B B v a b c a](http://slidesplayer.net/slide/11273961/61/images/78/%E5%85%A8%E5%9F%9F%E6%9C%A8+%EF%BC%88%E6%9C%AC%E8%B3%AA%E7%9A%84%E3%81%AB%E3%81%AF+%5BK.Sekine%2C+H.Imai+95%5D%EF%BC%89+%E6%9E%9D%E5%88%88%E3%82%8A%E3%81%AE%E8%A8%AD%E8%A8%88+a+a+b+A+b+A+c+c+B+B+v+a+b+c+a.jpg "同じ連結成分を. 両端とする辺を加えるとき、 サイクルができる. a. a. b. A. b. に接続. A. c. c. B. B. 加えない. v. a b c. a. mate[v] A A B. 孤立成分が. 生じる. b. A. 最後の辺まで処理後、 0 に接続されないなら. に接続. c. B. 1. に接続.")
79
マッチングの列挙 configuration の設計 枝刈りの設計 a a b b c c v a b c i a b c mate[v]
マッチングに 使われている 頂点に 辺を加える時 c c に接続 v a b c i a b c mate[v] mate[i] 既にマッチングに使われている頂点は 1 使われていない頂点は 0 と すればよい 最後の辺まで処理後、 0 に接続されないなら 1 に接続
![マッチングの列挙 configuration の設計 枝刈りの設計 a a b b c c v a b c i a b c mate[v]](http://slidesplayer.net/slide/11273961/61/images/79/%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0%E3%81%AE%E5%88%97%E6%8C%99+configuration+%E3%81%AE%E8%A8%AD%E8%A8%88+%E6%9E%9D%E5%88%88%E3%82%8A%E3%81%AE%E8%A8%AD%E8%A8%88+a+a+b+b+c+c+v+a+b+c+i+a+b+c+mate%5Bv%5D.jpg "マッチングに. 使われている. 頂点に. 辺を加える時. c. c. に接続. v. a b c. i. a b c. mate[v] mate[i] 既にマッチングに使われている頂点は 1. 使われていない頂点は 0 と. すればよい. 最後の辺まで処理後、 0 に接続されないなら. 1. に接続.")
80
辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド
[Knuth 2008] 森 全域木 一般化 ハミルトンパス カット（セット） 信頼性多項式 [Imai et al. 1997] 辺被覆 集合被覆 s-tカット オイラー路 シュタイナー木 k 終端カット サイクル 根付き森、木 完全 マッチング [Knuth 2008] 連結成分 集合分割 ハミルトンサイクル 信頼性多項式 複数終端対パス [Hardy et al. 2007] 集合 パッキング Tutte多項式 マッチング （ナンバーリンク） Jones多項式 （ひもの絡み目） [Yoshinaka et al. 2012] 上記3つ [今井, 今井 1998] 複数サイクル 上記2つ[関根, 今井 1996] 有向グラフ 有向パス [Knuth 08] 頂点変数型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド 独立集合 特殊 部分和 括弧列 Tutte 多項式 [Saitoh et al. 2009] [Imai et al. 1996] 支配集合 特殊 数分割 動的計画法的な見方も可能
81
支配集合の列挙 v1 v4 v7 v5 v8 v2 v9 v1 v3 v1 = 0 v1 = 1 v6 v2 v2 v2 = 0
頂点の取捨選択の情報を （フロンティア上の）頂点に記憶しているため、 効率が良いとは限らない v1 v4 v7 v5 v8 v2 ではない全ての頂点は v9 v1 v3 v1 = 0 v1 = 1 少なくとも1つの に隣接する v6 v2 v2 v2 = 0 v2 = 1 v2 = 0 v2 = 1 v1 v4 v7 頂点を変数とするZDDを構築 v5 v8 v2 i 頂点が支配されているなら1 支配されていないなら0 と すればよい mate[i] v3 v9 v6
82
0/1 ナップザック問題の列挙 x1 x2 xn x1 x1 = 1 x1 = 0 x1 x2 x2 x2 = 1 x2 = 0
重さ x1 各アイテムを 取るかとらないかを選択 重さが M 以下になるような取り方 50 x2 100 … … xn configuration = 重さの総和 210 x1 x1 = 1 x1 = 0 50 x1 x2 x2 x2 = 0 x2 = 1 x2 = 0 x2 = 1 x2 動的計画法のテーブルと見ることもできる … このグラフに対する フロンティア法と 見ることができる xn
83
辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド
[Knuth 2008] 森 全域木 一般化 ハミルトンパス カット（セット） 信頼性多項式 [Imai et al. 1997] 辺被覆 集合被覆 s-tカット オイラー路 シュタイナー木 k 終端カット サイクル 根付き森、木 完全 マッチング [Knuth 2008] 連結成分 集合分割 ハミルトンサイクル 信頼性多項式 複数終端対パス [Hardy et al. 2007] 集合 パッキング Tutte多項式 マッチング （ナンバーリンク） Jones多項式 （ひもの絡み目） [Yoshinaka et al. 2012] 上記3つ [今井, 今井 1998] 複数サイクル 上記2つ[関根, 今井 1996] 有向グラフ まとめ ・フロンティア法によって様々な対象を表現する ZDDを構築可能 → configuration と枝刈りの設計 有向パス [Knuth 08] 頂点変数型 クリーク 課題: 計算量評価等の理論的裏付け 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド 独立集合 特殊 部分和 括弧列 Tutte 多項式 [Saitoh et al. 2009] [Imai et al. 1996] 支配集合 特殊 数分割 動的計画法的な見方も可能
84
適用事例：配電網のスイッチ構成 配電網 すべての家は ちょうど1つの変電所に つながっている必要がある サイクルが生じてはいけない
変電所を根とする 根付き全域森 ∩ 根付き森 ZDD 電気制約 ZDD 条件を満たす ZDD 引用：
85
適用事例：配電網のスイッチ構成 配電網 468個のスイッチ 制約条件を満たす解の個数は 通り （＝ 約1063）
通り （＝ 約1063） 約1時間15分 ZDDノード数 約110万個 (779MB) すべての家は ちょうど1つの変電所に つながっている必要がある サイクルが生じてはいけない 変電所を根とする 根付き全域森 ∩ 根付き森 ZDD 電気制約 ZDD 条件を満たす ZDD 引用：
86
まとめ パスの数え上げアルゴリズム ZDD について詳細 様々な対象を表現するZDDを高速に構築する手法 「フロンティア法」 アルゴリズム
「フロンティア法」 アルゴリズム ハミルトンパス 複数終端対パス 全域木 マッチング 適用事例 フロンティア法のソースコード
Similar presentations
