卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ～アルゴリズムの改良の考察と そのプログラム作成～

Presentation on theme: "卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ～アルゴリズムの改良の考察と そのプログラム作成～"— Presentation transcript:

1 卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ～アルゴリズムの改良の考察と そのプログラム作成～
４年：山下　由展

2 目次 　　　 □ 木分解の定義について □ 木分解を生成する 　　　ヒューリスティックアルゴリズムの紹介 □ 卒業研究について

3 木分解の定義 木Ｔ Ｘｐ＝Ｖ（Ｇ）の ある部分集合 Ｘ１ １ Ｘｐ ｐ G=(V,E)：連結な単純グラフ
(T,X):T・・木、X={Xi⊆V(G)[i∈V(T)]} 木Ｔ Ｘｐ＝Ｖ（Ｇ）の ある部分集合 Ｘ１ １ Ｘｐ ｐ ※ｐはＴの頂点の番号（ここでは１≦ｐ≦|V(G)|)

4 木分解の定義 （１）∪i∈V(T)Xi=V(G) 頂点集合｛1,2,3,4,5,6,7} １ ２ １，２，４ ３ ４ ７ ４，６，７
⇒TとX={Xi⊆V(G):i∈V(T)}が次の条件(1)(2)(3)を満たす。 （１）∪i∈V(T)Xi=V(G) 頂点集合｛1,2,3,4,5,6,7} １ ２ １，２，４ 1 5 2 ３ ４ ７ ４，６，７ ３，４，６，７ １，３，４ 4 3 ４，５，６ ５ ６ ３，４，５ ２，５ （T,X) G

5 木分解の定義 （2)∀v,w∈V(G)[(v,w)∈E(G)⇒∃i∈V(T)[v,w∈Xi]] １ ２ 1，2 ，4 ３ ４ ７ ４ ，６，
(T,X)がＧの木分解 ⇒TとX={Xi⊆V(G):i∈V(T)}が次の条件(1)(2)(3)を満たす。 （2)∀v,w∈V(G)[(v,w)∈E(G)⇒∃i∈V(T)[v,w∈Xi]] １ ２ 1，2 ，4 1 5 2 ３ ４ ７ ４ ，６， ７ １，３ ，４ 4 3 ４，５，６ ３，４，５ ５ ６ G （T,X)

6 木分解の定義 １ ２ １，２，４ ３ ４ ７ １，３，４ ４，６，７ ４，５，６ ３，４，５ ５ ６ G （T,X) (T,X)がＧの木分解
⇒TとX={Xi⊆V(G):i∈V(T)}が次の条件(1)(2)(3)を満たす。 （3)∀i,j,k∈V(T)[jがTにおけるiからｋへの道上にある 　　　⇒Xi∩Xk⊆Xj １ ２ 1 １，２，４ 5 2 ３ ４ ７ １，３，４ ４，６，７ 4 3 ４，５，６ ３，４，５ ５ ６ G （T,X)

7 木分解の定義 1,2,4 4,6,7 1,3,4 幅＝２ 4,5,6 3,4,5 幅＝maxi∈I|Xi|-1(ここではtwD(G)で表す)
木幅＝min{twD(G)} D 1,2,4 4,6,7 1,3,4 幅＝２ 4,5,6 3,4,5

8 グラフから木分解をつくってなにか役にたつの？
グラフの木幅を定数で押さえることができる ⇒最大独立集合問題やハミルトンサイクル問題など のNP困難問題を多項式時間でとくことができる。

9 目次 　　　 □ 木分解の定義について □ 木分解を生成する 　　　ヒューリスティックアルゴリズムの紹介 □ 卒業研究について

10 s-t separating set ｔ ｓ 例） グラフG=(V,E)の頂点ｓから頂点ｔへのどんな道も
集合S（⊆V∖｛ｓ、ｔ｝）の頂点を通る時、この集合S をs-t　separating setという。 例） Minimum separating vertex set =mini{|s-t separating set|} (s,t)∉E(G) ｔ Ｓ ｓ

11 木分解を生成するヒューリスティックアルゴリズム（Aire M.C.A Koster等の論文に載っているもの)
操作 このアルゴリズムの概要 Ｇ０ Gi V(G)={v1,v2,…,vn} ≠クリーク Ｇ０' Gi' ０ ｖ１、ｖ２、…、ｖｎ 木分解 i j グラフＧ ・・ ・・・ |Xi|最大 すべての Gi(i∈V(T))がクリークになるまで |Xj|最大

12 木分解を生成するヒューリスティックアルゴリズム（Aire M.C.A Koster等の論文に載っているもの)
G=(V、E) はグラフで、 (T,X)はGの木分解 である(ここで、 T=(I,F)はノードＩ と辺Fの木。 そして、X＝｛Xi：i∈I} はVの部分集合族 G=(V、E) |i|=1 かつ X1=Vの 木分解 をつくる 木分解を つくる操作をする ∃i∈I: Gi≠クリーク 目標の 木分解 完成 no yes

13 準備 ここで、Gi＝(Vi、Ei)を次で定める。 Vi＝Xi、Ei＝E(G[Xi])∪E(∪ｋ∈N(i)C(Xi∩Xｋ)) d i b f
に隣接する頂点の集合 ここで、Gi＝(Vi、Ei)を次で定める。 Vi＝Xi、Ei＝E(G[Xi])∪E(∪ｋ∈N(i)C(Xi∩Xｋ)) Cはクリーク d i b f k G3 G). j h d a e c g 1 2 3 5 abd acd cde def ・・・ e c ↑ 4 Gの 木分解の作成途中 egh

14 木分解を生成するヒューリスティックアルゴリズム（Aire M.C.A Koster等の論文に載っているもの)
G=(V、E) はグラフで、 (T,X)はGの木分解 である(ここで、 T=(I,F)はノードＩ と辺Fの木。 そして、X＝｛Xi：i∈I} はVの部分集合族 G=(V、E) |i|=1 かつ X1=Vの 木分解 をつくる 木分解を つくる操作をする ∃i∈I: Gi≠クリーク 目標の 木分解 完成 no yes

15 木分解を生成する ヒューリスティクアルゴリズム
Minimum separating vertex set S はグラフ Xi1 S Yi1 i0 i Xi0 Xi はその 頂点集合 Xi0 = S Gi Gi[Vi/S] Yim-1 Xim-1 i1 i2 im Xi1 Xi2 Xim Yi2 ･･･ ･･･ S ･･･ Xi2 Yim Xk、ｋ∈N(i) S Xim Gi[Vi/S]はｍ個の 連結成分に分割された とする。 S

16 目次 　　　 □ 木分解の定義について □ 木分解を生成する 　　　ヒューリスティックアルゴリズムの紹介 □ 卒業研究について

17 卒業研究内容 辺の数 最大 Ｇｉ [Vi/S] はグラフ i ・・・ Xi はその 頂点集合 ・・・ ･･･ ･･･ Xk、ｋ∈N(i)
Minimum Separating Vertex set (ここではＳとする) 辺の数は すべて同じとは 限らない。 Minimum separating Vertex setで誘導される Giの誘導部分グラフ

18 卒業研究内容 i i0 無駄にクリークに ならないように 努める Ｘｉ０ Ｘｉ Ｇｉ [Vi/S] Ｘｉ１ Ｘi2 Xim ・・・ ・・・
E[Gi[minimum separating vertex set]] 最大 E[Gi[Vi/S]]最小 |V[Gi[Vi/S]]|同じ

19 実演Java

20 関連データ 論文のものの 方が幅が小さい 卒研のものの 方が幅が小さい 同じ 標本数 頂点数 ５０ １０ ０ ２ ４８ ５０ ４ ９ ５０ ３７ １ １００ ０ ０ １ １ ＯＳ ＣＰＵ ＰｅｎｔｉｕｍⅢ プロセッサ ＷｉｎｄｏｗｓＸＰ 使用した計算機 ＰｅｎｔｉｕｍⅣ プロセッサ Ｒｅｄｈａｔ

21 Fin