木幅とパス幅を利用したグラフ彩色アルゴリズムの

木幅とパス幅を利用したグラフ彩色アルゴリズムの実験による
評価
田野登志博
明治大学大学院
理工学研究科基礎理工学専攻情報科学系
計算理論研究室
2015 年 2 月 14 日
概要
本研究では 2 種類の実験をした．一つ目に，コンパイラの最適化手法の一つである，レジスタ割
り当て問題に関する実験をした．実験には Mikkel Thoup によって考案された，入力で与えられた
プログラムのレジスタ割り当て問題を (k+1) 近似で行うアルゴリズム用いる．このアルゴリズム
は，プログラムの control flow graph の最適な木分解が求まっているとき，多項式時間で動作する
アルゴリズムである．しかし，実用性の面からこの理論的な近似率を考えると，大き過ぎると考え
られる．そこで，実際のプログラムを入力としたこのアルゴリズムを実装実験をする．これは，実
験による解が理論的な近似値より良くなる可能性があるため，結果を比較して検証することを研究
の目的とする．比較対象としてバックトラックアルゴリズムを用いることで，近似アルゴリズムの
近似率，実行時間の比較し性能を評価する．入力プログラムには，java.util パッケージ，java.lang
パッケージのクラスファイルを対象として実験を行い，これを実験 1 とする．実験を行った結果，
ほとんどのケースで理論的な近似値よりはるかに良い解が求まった．しかし，バックトラックアル
ゴリズムに実行時間で劣るケースが多かったため，このアルゴリズムの有用性を強く主張すること
ができなかった．しかし，実装によるオーバーヘッドなども大きくかかわってくるため，このアル
ゴリズムが有効である可能性は十分にあると考えられる．
二つ目の実験として，一般の無向グラフ G に対する彩色アルゴリズムについて実装実験する．
探索順の異なる 3 つのバックトラックアルゴリズムと，パス分解に基づく動的計画法アルゴリズム
を用いる．バックトラックアルゴリズムは，実行時間が探索順序に大きく影響する．本実験では，
頂点順序順に探索するもの，G の最適なパス分解に対応する順序列順に探索するもの，G の最適か
つ好適なパス分解の導入頂点順に探索するもので実験を行う．実験には二つの作成方法でグラフ
を作成し，それぞれについてを検証する．実験 2 として，全ての 2 頂点間に一定の確率 P で辺が
引かれるという方法で無向グラフ G を作成する．G の頂点数 N と P を固定し，それぞれのアル
ゴリズムを 10 回ずつ実行し，実行時間の平均を取ることでそれぞれの性能を評価する．実験 3 と
して，全ての頂点は 2 次元座標を持ち，全ての 2 頂点間の距離が L 以下である場合，一定の確率
P で辺が引かれるという方法で G を作成する．L, P, N を固定し，それぞれのアルゴリズムを 10
回ずつ実行し，実行時間の平均をとることでそれぞれの性能を評価する．実験結果として，バック
トラック解法とパス分解に基づく動的計画法について興味深い結果を得ることができた．一般に，
バックトラックアルゴリズムはメモリの消費を少ないが，入力の大きさの増加と共に実行時間が指
数的に爆発的に増加する，パス分解に基づく動的計画法では，パス幅の小さいときに有効だがパス
幅の増大と共にメモリ消費と実行時間が共に爆発的に増加するため，適用できる入寮が限られる，
という一般的な認識に対し，バックトラック法が予想以上に高速に動作するということ，特に好適
なパス分解の導入頂点順に探索するバックトラック法では，実験した範囲ではほとんどの場合で高
速であるという結果を得た．
1
目次
第1章
はじめに
3
第2章
k-complexlisting に基づいたグラフ彩色アルゴリズム
5
第3章
パス分解に基づいたグラフ彩色アルゴリズム
7
3.1
バックトラックアルゴリズム
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.2
パス分解に基づいた動的計画法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
第4章
実験
10
4.1
実験 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4.2
実験 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.3
実験 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
まとめ課題
35
第5章
参考文献
36
2
第1章
はじめに
グラフ彩色問題は，コンパイラ最適化手法の一つであるレジスタ割り当て問題と密接な関係を持っている．
レジスタ割り当て問題は，プログラムの変数をどのようにして効率的にレジスタに割り当てるかを問う問題で
ある．変数に割り当てるレジスタを色として，生存期間が重なる二つの変数に同一の色を割り当ててはいけな
いと考えると，これは変数を頂点とし，生存期間が重なる二つの変数間に辺の引かれた彩色問題となる．ここ
で使用するレジスタを最小化することを目的とすることから，彩色に使う変数の色を最小化する．また，割り
当て問題は，NP 完全であることが知られている．[1]
本研究では，Mikkel Thoup 氏の論文 [3] による，k-complexlisting に基づいたグラフ彩色の近似アル
ゴリズムを実装し，実装上の性能を実験により評価する．この論文によると，グラフ G が k-complexlisting
を持つということと，グラフの木幅が k であることは，必要十分条件を満たす．これは，木幅の求め方
と，k-complexlisting の求め方が本質的に同じだからである．研究では，グラフ彩色を行う際に必要となる
k-complexlisting を Bodlaender 氏等による木幅を求めるアルゴリズムを用いて求めている．
グラフの木幅が小さく求まると，多くの NP 完全な問題を木幅をパラメータとして使うことで，高速に解
くことができる．グラフ彩色問題もその一つである，今回実験に使用するアルゴリズムでは，木幅の値の大き
さが近似率にも影響を与えることになる．このアルゴリズムの実用性を考えたとき，この近似度は高いと考え
られるが，実験で求まるこのアルゴリズムの解が近似値より良い可能性があるため，結果を比較して検証する
ことを研究の目的とする．
レジスタ割り当ての考え方として，プログラムのコード以下で使用されなくなった変数に使用していたレ
ジスタは再利用できる．
このようなプログラムを考えた場合，以下のように考えることができる．
• 変数 a は，e := a + b のあと再利用できる．
• e も同様に，f := e − 1 のあと再利用できる．
• a, e, f はどうようのレジスタ (r1 ) に割り当てられる．
このことから，プログラムを使用するレジスタに割り当てると，下記のように割り当てることができる．
G = (V, E) が control flow graph を示す．これは，プログラムを実行したときに通る可能性のある全経路を
示したもので，basic block を頂点とする有向グラフであるが，今回取り扱うアルゴリズムに関しては向きは
考慮しないことから，G は無向グラフとする．basic block とは，命令列から成り，block 内には，分岐や合流
は存在せず．上流から下流へ常に同じ順番で実行される．変数を頂点として，G で生存期間が重なるものの頂
点間に辺をひいてできたグラフの彩色を行う．よって，データフロー解析というプログラム内のさまざまな位
3
置で，変数の取りうる値の集合の情報を収集する技法を control flow graph 上で使用する必要がある．隣接
点は別の色で彩色するという条件と，必要最小数の色だけ使うという条件で彩色を行うと，レジスタ割り当て
問題を解くことができる．
4
第2章
k-complexlisting に基づいたグラフ彩色アル
ゴリズム
本節では，論文で紹介されているグラフ彩色アルゴリズム [3] について示す．G = (V, E) を無向グラフとす
る．このとき，G の木分解を T D = (X, T ) とする．T = (I, F ) は木であり，X = (Xi |i ∈ I) が V の部分集
合で，次の 3 つの条件を満たすとき，T D は G の木分解であるという．
1.
∪
Xi (i ∈ I) = V
2. 全ての辺 e = (u, v) ∈ E に対して，u ∈ Xi かつ v ∈ Xi となる i が少なくとも一つは存在する．
3. 全ての v ∈ V に対して，v が含まれる全ての頂点集合 (i ∈ I|v ∈ Xi ) が T の連結な部分木である．
X1 , X2 , . . . をバッグといい，maxi∈I (|Xi | − 1) を木分解における幅といい，グラフ G のすべての木分解に
おける幅の最小値を G の木幅という．一般に，G の木幅を求める問題は，v ∈ V の頂点順列を求める問題と
して取り扱われる．最適な頂点順列を求めることで，G の木幅が求まる．
k-complexlisting とは，全ての頂点 v ∈ V の順列 π で表したものを示す．v と v より右側に現れる頂点
の集合を Pv とし，Pv の中で v を v より左に現れる頂点集合と別の連結成分に分けることのできる頂点集
合を Sv とする．すべての頂点 v ∈ V に対して，Sv の大きさが k 以下となるよう定義できるとき，π は
k-complexlisting であるという．また，グラフ G が k-complexlisting を持つとき，G は k-complex であると
いう．
変数の生存期間を表す G の部分グラフを X とする．また，interference graph I を X からなる intersection
graph とする．入力で G と k-complexlisting が与えられる．また，彩色で使用する色を 1, 2, 3, . . . とし， χ(I)
を彩色における必要最小数とする．
定理 2.1. グラフ G が k-complex であることと，G の木幅が k であることは必要十分条件を満たす．[3]
G =control flow graph, L = {v1 , v2 , . . . , vn } =G の k-complexlisting, vi を部分グラフとして含む変数の
生存期間の集合 Xvi の列 X = {Xv1 , Xv2 , . . . , Xvn } が入力として与えられたとき，変数のレジスタ割り当て
問題を (k + 1) 近似で行うアルゴリズムの疑似コードを以下に示す．
5
Algorithm 1 (k + 1) 近似彩色アルゴリズム
1: for i := 1, . . . , n do
2:
3:
for x ∈ Xvi do
if x が彩色されていない then
x ∈ Xvi を Svi で使用されていない最小の色で彩色する
4:
5:
6:
7:
end if
end for
end for
このアルゴリズムの実行時間は，O(kωn) で，control flow graph の木幅が求まっている場合、多項式時間ア
ルゴリズムで動作する．しかし，近似率が (k + 1) 近似であり，実用性を考えたとき近似率が大き過ぎると考
えられる．そこで，実験による解が理論的な近似値より良くなる可能性があるため，バックトラックアルゴリ
ズムを用い，それぞれのアルゴリズムの解と実行時間を比較することで近似アルゴリズムの性能を評価する．
6
第3章
パス分解に基づいたグラフ彩色アルゴリ
ズム
一般の無向グラフ G に対する 2 つの彩色アルゴリズムについて示す．本研究では，これらのアルゴリズム
を用い，ランダムに生成した無向グラフ G に対して実行時間を比較し，評価する．
3.1 バックトラックアルゴリズム
一般の無向グラフ G に対するバックトラックアルゴリズムについて示す．本研究では，探索順序の異なる
3 つのバックトラックアルゴリズムについて実行時間の検証を行う．
バックトラックアルゴリズムは，決められた順序で，全ての状態について探索するアルゴリズムである．し
かし，暫定解より良くなり得ないときに枝刈りをして探索回数を減らすことができる．一般にバックトラック
アルゴリズムの実行時間は，頂点の探索順序に大きく影響を受ける．本研究では，以下に示す順序で探索する
バックトラックアルゴリズムについて実験を行った．
• BT 1 : 頂点番号を探索順序とするバックトラックアルゴリズム
• BT 2 : G の最適なパス分解に対応する頂点順列を探索順序とするバックトラックアルゴリズム
• BT 3 : G の好適なパス分解の導入頂点順に探索するバックトラックアルゴリズム
7
入力として無向グラフ G, 探索順序順の頂点順列 π = {v1 , v2 , . . . , vn }，暫定解 = ∞ が与えられたとき、G
の彩色を行うバックトラックアルゴリズムの疑似コードを以下に示す．
Algorithm 2 バックトラックアルゴリズム BT(i, M )
1: if M が暫定解以上である then
return
2:
3:
end if
4:
if i = n then
5:
暫定解を M とする．
6:
return
7:
end if
8:
for j = 0 to M + 1 do
if vi の全ての隣接点が j で彩色されていない then
9:
BT(i + 1, max(M, j))
10:
end if
11:
12:
end for
3.1.1 実行時間
無向グラフ G の頂点数 = n，彩色に使用する色数 = k とすると，彩色に対するバックトラックアルゴリズ
ムの実行時間は，O(k n ) である．全ての頂点 v に対して k 通りの割り当てが考えられる．このことから全て
の場合は k n 通りなので，バックトラックアルゴリズムの実行時間は O(k n ) となる．
3.2 パス分解に基づいた動的計画法
一般の無向グラフ G に対する G のパス分解に基づいた動的計画法について示す．この動的計画法は，パス
分解に基づいた動的計画法としては標準的なものであり，この解説論文として Bodlaender による A tourist
guide through treewidth[5] が挙げられる．
以下の条件を満たすとき，X = {X0 , X1 , . . . , Xr } を G = (V, E) のパス分解という．
•
∪
(0≤i≤r)
Xi = V • ∀e = (u, v) ∈ E に対して，u ∈ Xi かつ v ∈ Xi となる i が少なくとも一つ存在する．
• v ∈ Xi かつ v ∈ Xk (i ≤ j ≤ k) のとき v ∈ Xj である．
G = (V, E) を無向グラフ,X = {X0 , X1 , . . . , Xr } を G のパス分解とする．G の頂点数を n とすると，G
のパス分解が，2n + 1 個の列 X0 , . . . , X2n であり，次の条件を満たすとき，好適なパス分解であるという．
1. X0 = X2n = ∅
2. 全てのバッグ Xi は，次のいずれかを満たす．
• Xi−1 ⊂ Xi かつ |Xi | − |Xi−1 | = 1 である．
• Xi ⊂ Xi−1 かつ |Xi−1 | − |Xi | = 1 である．
8
前者の場合，Xi を導入バッグといい，v = Xi \ Xi−1 を導入頂点という．Xi−1 に v を追加するこ
とを v を導入するという．後者の場合，Xi を忘却バッグといい，v = Xi−1 \ Xi を忘却頂点とい
う．Xi−1 から v を消去することを，v を忘却するという．
3. G の全ての頂点 v に対しても，それを導入するバッグと忘却するバッグが一つだけ存在する．
無向グラフ G = (V, E) の好適なパス分解 P D = {X0 , X1 , . . . , X2n } が与えられてたとき，G の最適な彩
色数を求めるアルゴリズムについて示す．この問題の部分問題を，バッグの番号 i, Xi の色付けを γ とすると
き，この最適値 opt(i, γ) =
∪
j≤i
Xj の色付けの組み合わせのうち，Xi の色付けが γ と同じもので色数が最
小のものとして定義する．このとき，漸化式は以下のようになる．
Xi が v を導入するバッグで，γ ′ を，γ において v の色付けを無視した色付けづけとすると
opt(i, γ) = max(γ の使う色数, opt(i − 1, γ ’))
となる．Xi が v を忘却するバッグで，γc を，v を c で彩色し，その他の頂点を γ のように彩色する色付けと
するとき，
opt(i, γ) = minc (opt(i − 1, γc ))
となる．
i を 0 から初めて，大きい方へ向けて opt(i, γ) の計算をすることで，もとの問題の最適値は opt(2n, ∅) として
求めることができる．
3.2.1 実行時間
無向グラフ G の頂点数 = n，彩色に使用する色数 = k, G のパス幅を w とすると，パス分解に基づくグラ
フ彩色の動的計画法の実行時間は O(nwk+1 ) である．全ての導入バッグ Xi で導入頂点 v を彩色する．その
バッグにおける v を Xi に存在する隣接点で使用されていない色で彩色する．このとき，v の隣接点の数が
最大で k 個存在する．Xi の全頂点を彩色するとき，最大で k + 1 色で彩色できるので，すべてのバッグは
O(nwk+1 ) で彩色することができる．よって，パス幅が小さく求まれば，実行時間を小さくすることが期待で
きる．
9
第4章
実験
4.1 実験 1
(k+1) 近似アルゴリズムとバックトラックアルゴリズムを用意し，一般に公開されているプログラムについ
て実装実験を行う．入力のテストケースに対して，2 つのパラメータ N V, tw を次のように定義する．
• N V : プログラムに存在する，変数の生存期間の数を示す．
• tw : control flow graph の木幅を示す．
4.1.1 実験内容
• バックトラックアルゴリズム
• (k+1) 近似アルゴリズム
一般に公開されているプログラムの，java.util パッケージと java.lang パッケージのクラスファイルについ
て，(k+1) 近似アルゴリズムとバックトラックアルゴリズムで実装実験する．実験では，(k+1) 近似アルゴ
リズムの近似率，また，両方の実行時間について計測する．tw と，N V の値が等しい入力のとき，アルゴリ
ズムの解と実行時間の平均を取ることで，2 つのアルゴリズムの性能を評価する．近似率の評価項目に，ave,
worst を用い，実行時間の評価項目に ave1, ave2 を用いる．
• ave : N V, tw が等しい入力に対する近似率の平均値を示す．
∑
∑
ave = 近似解/ 最適解
• worst : N V, tw が等しい入力に対する，近似度が最も高かったものを示す．
• ave1 : N V, tw が等しい入力に対する、バックトラック法の実行時間の平均を示す．
• ave2 : N V, tw が等しい入力に対する、近似アルゴリズムの実行時間の平均を示す．
10
4.1.2 実験結果
実験 1 の結果について，表 6.1 から表 6.3 に実験結果を示す．表中における空欄 (-) は，木幅を求めるプロ
グラムの実行が終わらず，求めることができなかったことを示す．実験の結果，ほとんどのテストケースで木
幅が小さく求まり，近似アルゴリズムの解の平均値と最悪値，共に理論的な近似値よりはるかに小さく求まっ
た．しかし，実行時間ついてはバックトラックアルゴリズムより高速に求まるケースは少なく，4061 個中，
127 個の場合でのみ実行時間を上回ることができた．よって，近似度については良い結果を得ることができた
が実行時間についてはあまり良い結果を得ることができなかったため，本実験では近似アルゴリズムの優位性
を主張することができなかった．しかし，本実験においてバックトラックアルゴリズムで枝刈りが強く効いて
いたことや，オーバーヘッドによる時間のロスがあったことも考えられる．近似アルゴリズムは control flow
graph の木幅が求まっているとき常に線形時間で動作することが保障されているので，今回の実験で近似率が
小さく求まったことから近似アルゴリズムの実用性は十分似可能性が残っていると考える．
11
表 4.1
tw = 0
実験 1 の結果 (近似度)
tw = 1
tw = 2
tw = 3
NV
ave
worst
ave
worst
ave
worst
ave
worst
1
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
2
1.000
1.000
1.039
2.000
1.003
2.000
1.000
1.000
3
1.000
1.000
1.000
1.000
1.028
1.500
1.000
1.000
4
1.000
1.000
1.008
1.333
1.049
1.333
1.000
1.000
5
1.000
1.000
1.054
1.250
1.107
1.667
1.150
1.250
6
1.000
1.000
1.000
1.000
1.067
1.667
1.094
1.500
7
1.000
1.000
1.056
1.167
1.050
1.500
1.192
1.400
8
1.000
1.000
1.083
1.167
1.052
1.200
1.036
1.143
9
1.000
1.000
-
-
1.037
1.286
1.042
1.167
10
1.000
1.000
-
-
1.118
1.500
1.150
1.600
11
1.000
1.000
-
-
1.081
1.200
1.333
2.250
12
1.000
1.000
-
-
1.095
1.286
1.126
1.167
13
-
-
1.000
1.000
1.102
1.333
1.167
1.333
14
1.000
1.000
1.000
1.000
1.097
1.400
1.100
1.100
15
-
-
1.000
1.000
1.319
1.600
1.000
1.000
16
-
-
-
-
1.250
1.500
1.120
1.500
17
-
-
-
-
-
-
1.455
1.455
19
-
-
-
-
-
-
1.273
1.273
21
-
-
-
-
1.000
1.000
-
-
22
-
-
-
-
-
-
-
-
23
-
-
-
-
-
-
1.077
1.077
24
-
-
-
-
-
-
-
-
28
-
-
-
-
-
-
-
-
30
-
-
-
-
-
-
-
-
31
-
-
-
-
-
-
-
-
33
-
-
-
-
-
-
-
-
12
表 4.2
実験 1 結果 (実行時間 (ナノ秒))
tw =0
tw =1
tw =2
tw =3
NV
ave1
ave2
ave1
ave2
ave1
ave2
ave1
ave2
1
1956
6894
2495
8447
2325
9436
3047
24059
2
2712
7316
2773
8963
2751
10175
1444
9143
3
3092
6950
3697
9813
3712
16040
2085
19729
4
3756
7624
5993
13418
4507
16586
2165
16119
5
3539
7862
2955
7698
6054
21368
3560
15783
6
4619
7650
16146
76402
7361
23251
4918
85358
7
4544
7806
3689
10105
8380
26385
3850
30315
8
4908
5485
4571
19488
7538
26607
4330
36811
9
34453
4330
-
-
6128
24616
5052
40179
10
6530
5293
-
-
5714
27909
6255
36209
11
9624
6496
-
-
6616
32360
6736
53492
12
13954
8661
-
-
6416
42505
7859
33202
13
-
-
7699
13473
18104
54374
9864
42826
14
11067
9143
10105
12304
11644
30796
8181
46195
15
-
-
11549
10105
12511
42986
9142
71698
16
-
-
-
-
8340
62876
27813
68329
17
-
-
-
-
-
-
137621
38977
19
-
-
-
-
-
-
12993
63517
21
-
-
-
-
17323
47638
-
-
22
-
-
-
-
-
-
-
-
23
-
-
-
-
-
-
21928
67435
24
-
-
-
-
16361
93833
22135
68329
28
-
-
-
-
-
-
-
-
30
-
-
-
-
18766
111156
-
-
31
-
-
-
-
-
-
-
-
33
-
-
-
-
-
-
-
-
13
4.2 実験 2
4.2.1 実験の内容
一般の無向グラフ G 対する彩色アルゴリズムの実装実験を行う．実験 2 では複数のアルゴリズムを用い，ラ
ンダムに生成した G について実行時間の計測をすることで性能を評価する．実験には，BT1, BT2, BT3,CDP
の 4 つのアルゴリズムを用意する．
• BT1 : G の頂点番号順に色の割り当てをして，最適な彩色を求めるバックトラックアルゴリズム．
• BT2 : G の最適なパス分解に対応する順列順に色の割り当てをして，最適な彩色を求めるバックトラッ
クアルゴリズム．
• BT3 : G の好適なパス分解の導入頂点順に探索を行うバックトラックアルゴリズム．
• CDP : アルゴリズム 2 に記述した，G の好適なパス分解を用いて彩色を行い，最適な彩色を求める動
的計画法アルゴリズム．
バックトラックアルゴリズムは，探索順序によって実行時間が大きく影響する．BT1, BT2, BT3 は，バッ
クトラックアルゴリズムの探索順序を変えたものであり，探索順序が G の頂点数，辺密度，パス幅にどのよ
うに影響があるか観察する．G の頂点数 = N (0 ≤ N ≤ 30), 辺密度 = P (0 ≤ P ≤ 40) のグラフを 10 回ずつ
ランダムに生成し，4 つのアルゴリズムの実行時間の平均と，最も大きくかかった実行時間を求める．実験結
果の評価項目に，ave, worst を用いる．
• ave : 10 回の実行での平均実行時間を示す．
∑
ave = 実行時間/実行回数 (10 回)
• worst : 10 回の実行で最も実行時間が大きくかかったものを示す．
尚，実験で，グラフ G のパス幅を求めるアルゴリズムとして，O(1.89n ) のアルゴリズム [2] を用いる．
4.2.2 実験の結果
表 6.3 から表 6.6 と，図 6.1 から図 6.8 に実験結果を示す．pw とは，頂点数 N と辺密度 P によって生成
された G のパス幅の平均を示す．実験では，頂点数 N = 30 までしか実行することができなかった．これは，
頂点数と辺密度が増えることで，CDP の状態数が増え，メモリが大きくなりすぎてしまうことが原因である．
実行速度の面では，辺密度 P = 20 までは，CDP は BT1 と BT2 よりも実行が遅かったが，P = 30 以上
になると，CDP の実行時間がその二つよりも平均的に速く求まるという結果を得た．好適なパス分解の導入
頂点順に探索するバックトラックアルゴリズムは，ほとんどすべてのテストケースで実行時間が 4 つの中で最
も優れているという結果を得た．
14
表 4.3
実験 2 結果 (実行時間 (マイクロ秒))(P = 10)
BT1
BT2
BT3
CDP
pw
N
ave
worst
ave
worst
ave
worst
ave
worst
10
9.9
25.2
10.7
20.3
17.2
46.7
352.5
1280.4
1
11
8.4
27.1
6.1
15.9
7.7
13.0
197.2
331.4
1
12
7.9
20.5
9.2
35.3
8.4
11.7
209.7
282.1
1
13
11.2
31.5
6.9
15.5
11.0
34.4
193.3
288.6
1
14
6.7
15.4
5.5
10.2
5.8
8.2
157.5
227.3
1
15
13.4
32.9
11.2
20.8
5.5
7.7
147.5
173.9
1
16
10.3
14.7
14.9
25.6
7.0
9.8
168.9
189.5
1
17
15.0
27.8
13.3
33.0
6.7
10.2
176.9
231.5
1
18
41.2
81.3
39.4
67.0
7.8
10.1
196.4
237.4
2
19
35.0
83.1
43.0
90.9
8.1
11.5
221.7
334.9
2
20
92.2
217.0
69.2
115.9
11.4
20.6
313.4
572.1
2
21
57.1
89.5
59.4
140.5
12.0
16.3
330.6
616.8
2
22
79.2
201.6
35.7
74.1
12.3
17.8
354.4
735.2
3
23
156.8
291.1
53.9
89.5
11.6
19.2
373.6
822.3
3
24
191.4
325.2
83.6
239.6
19.4
34.1
542.8
755.4
3
25
77.2
124.6
40.8
68.8
17.9
26.9
578.3
1448.3
4
26
35.8
49.0
51.4
85.6
15.8
26.9
491.4
1144.2
3
27
230.2
614.9
45.8
90.9
22.1
32.7
773.5
2126.8
4
28
241.5
435.4
69.1
120.7
22.1
28.8
954.6
1797.2
5
29
231.9
552.4
114.2
244.4
57.4
185.2
1247.4
2206.2
5
30
249.7
541.8
76.3
162.6
37.4
112.6
1242.4
2326.0
5
15
表 4.4
実験 2 結果 (実行時間 (マイクロ秒))(P = 20)
BT1
BT2
BT3
CDP
pw
N
ave
worst
ave
worst
ave
worst
ave
worst
10
11.3
28.0
10.7
16.6
3.8
5.1
121.8
134.8
1
11
13.9
32.3
14.3
36.9
5.7
7.5
153.7
183.2
2
12
16.5
53.7
20.8
52.4
9.2
38.8
160.6
187.2
2
13
29.2
82.5
17.7
25.4
7.9
15.0
181.5
213.6
2
14
33.5
122.3
18.2
26.8
13.9
44.6
232.5
292.9
3
15
35.2
69.8
22.7
32.3
13.0
24.2
292.5
651.0
3
16
60.7
143.9
19.2
28.9
22.8
53.3
319.7
668.7
4
17
26.3
42.0
25.7
40.2
11.5
20.3
274.5
419.1
4
18
39.4
85.1
21.3
27.8
19.2
36.0
478.0
1080.7
4
19
47.4
94.6
58.1
139.7
17.7
35.3
452.2
885.7
4
20
147.3
370.5
114.7
248.7
27.6
45.2
511.1
906.0
5
21
66.8
105.8
60.8
115.0
60.4
137.6
728.2
2105.7
5
22
692.4
1255.4
145.8
327.6
51.6
129.4
859.9
2004.6
7
23
298.0
511.0
596.4
1370.4
35.5
99.1
393.7
512.9
7
24
165.8
364.7
83.2
218.9
89.6
229.0
721.0
1174.1
7
25
1053.2
1975.3
251.3
451.3
27.5
37.5
1027.7
2845.7
8
26
266.9
360.8
500.0
780.4
197.5
383.0
1253.6
2548.8
8
27
2604.4
5378.3
657.5
876.2
236.2
601.4
678.0
1000.4
9
28
2038.4
4665.1
536.6
1336.7
200.6
357.0
826.6
826.6
10
29
1223.4
2005.6
2330.6
5743.5
271.5
665.9
750.1
750.1
10
30
1643.5
3030.0
3599.6
7412.7
52.9
106.8
349.3
349.3
11
16
表 4.5
実験 2 結果 (実行時間 (マイクロ秒))(P = 30)
BT1
BT2
BT3
CDP
pw
nv
ave
worst
ave
worst
ave
worst
ave
worst
10
12.2
20.5
13.1
22.0
7.2
15.0
152.3
180.7
3
11
21.2
52.7
22.0
79.1
8.0
18.2
162.0
197.5
2
12
26.6
66.1
39.7
111.4
9.8
25.9
181.5
213.0
3
13
48.9
103.1
40.1
84.9
13.7
24.5
228.4
340.1
4
14
26.1
44.4
38.4
123.9
16.1
28.0
430.6
991.1
4
15
38.8
75.8
52.7
122.2
32.4
69.0
401.9
864.6
5
16
125.3
272.5
55.7
87.1
27.9
42.2
547.1
1220.5
5
17
161.9
250.9
112.1
236.8
33.4
59.8
996.1
1887.4
6
18
124.5
194.6
189.5
502.7
24.8
46.0
839.9
2161.6
7
19
470.9
1071.1
327.0
763.0
37.6
89.2
989.3
1889.3
7
20
302.2
711.6
456.5
1320.3
50.6
108.2
990.2
1765.0
8
21
220.4
435.4
1451.1
3273.0
107.2
219.9
1593.1
3573.3
9
22
180.9
314.2
111.8
179.4
68.9
179.0
1198.8
2644.6
9
23
432.5
923.8
431.3
822.3
50.4
76.9
325.2
325.2
9
24
858.6
1343.9
642.1
1028.7
298.4
569.2
1279.7
1914.6
10
25
1194.9
2554.1
418.7
968.6
271.1
626.9
2639.3
5461.5
11
26
1004.8
2195.2
7786.0
12236.7
282.7
402.7
17212.7
44721.2
12
27
30006.9
60488.9
32606.8
79751.6
477.7
698.2
8453.8
9926.0
12
28
20804.5
38623.5
28031.3
49053.8
2633.3
4985.1
1244.3
1244.3
13
17
表 4.6
実験 2 結果 (実行時間 (マイクロ秒))(P = 40)
BT1
BT2
BT3
CDP
pw
nv
ave
worst
ave
worst
ave
worst
ave
worst
10
23.9
62.5
25.1
81.1
27.0
67.4
363.3
649.3
4
11
18.8
26.5
21.8
45.5
24.8
65.2
201.6
353.6
5
12
53.7
87.9
64.7
148.9
12.8
28.3
190.9
355.4
5
13
35.9
88.0
61.9
111.9
14.3
21.6
209.4
307.2
5
14
74.0
160.0
106.3
324.8
22.1
51.9
390.7
853.3
6
15
81.9
172.7
49.5
85.7
23.7
50.9
594.7
1590.9
7
16
136.1
238.6
340.0
775.6
43.9
103.0
702.7
1407.2
7
17
48.4
90.8
55.1
112.5
53.3
134.5
873.4
1930.7
8
18
352.4
652.7
230.5
543.7
53.9
108.1
1277.6
2568.1
9
19
139.0
269.9
235.1
407.5
54.0
89.3
1265.0
1993.1
10
20
705.9
1193.8
1771.5
3110.4
74.6
173.2
859.1
2504.1
10
21
331.3
498.9
1148.8
3253.8
206.1
315.1
15928.4
32991.6
11
22
855.8
2347.7
135.6
135.6
97.6
153.9
2639.8
3601.7
12
23
1364.3
3516.5
1394.4
3057.9
310.2
527.8
2724.3
3820.2
13
24
3181.2
4988.0
2832.8
4859.5
175.6
372.4
14970.5
19211.6
14
25
6472.0
12423.4
8629.6
17451.4
833.0
1291.0
16971.9
30117.4
14
26
24202.3
35988.9
12632.0
22019.9
184.9
261.7
663.5
663.5
14
27
6758.4
12653.4
548.5
548.5
2093.5
4550.1
41586.7
41586.7
14
18
表 4.7
実験 2 パス幅による各アルゴリズムの実行平均時間 (マイクロ秒)
BT1
BT2
BT3
CDP
pw
ave
ave
ave
ave
1
10.4
9.8
8.1
191.7
2
38.3
35.7
8.8
215
3
66.1
38.2
14.5
331.6
4
63.9
34.6
18.4
415.2
5
126.5
77.6
31.4
642.4
6
121.9
80.8
28.5
795.4
7
276.6
248.1
48
768.6
8
493.7
359.6
82.4
1137.3
9
715.4
577.4
103.3
1012
10
1031.5
1285.9
210.2
3928.8
11
1231.4
1384.7
140.6
1876.1
12
10792
13929.1
356.8
9463.6
13
11992.9
15432
1404.4
8107.4
14
12477.6
7270
1037.1
19740.7
19
図 4.1 実験 2 結果 (P=10) 平均
図 4.2
実験 2 結果 (P=10) 最悪の場合
20
図 4.3 実験 2 結果 (P=20) 平均
図 4.4
実験 2 結果 (P=20) 最悪の場合
21
図 4.5 実験 2 結果 (P=30) 平均
図 4.6
実験 2 結果 (P=30) 最悪の場合
22
図 4.7 実験 2 結果 (P=40) 平均
図 4.8
実験 2 結果 (P=40) 最悪の場合
23
図 4.9
実験 2 結果パス幅による各アルゴリズムの実行平均時間
24
4.3 実験 3
4.3.1 実験の内容
実験 2 と同様の 4 つのアルゴリズムについて実行時間の計測をし，性能を評価する．G のすべての頂点に
x, y(0 ≤ x, y ≤ 200) の 2 次元座標持たせ，2 頂点間の距離が 100 以下の頂点間に辺を引くという方法でグラ
フを生成する．このグラフの生成方法は，頂点数 N ，辺密度 P が増えても，実験 2 のグラフ作成方法ほど G
のパス幅が大きくなりにくいという傾向がある．N, P を固定して 10 回グラフを生成し，彩色アルゴリズムの
実行時間の平均を求める．また，生成したグラフのパス幅ごとにアルゴリズムの実行平均時間を計測すること
で，パス幅が各アルゴリズムがに対して与える影響を観察する．実験結果の評価項目に，ave, worst, pw を用
いる．
• ave : 10 回の実行での平均実行時間を示す．
∑
ave = 実行時間/実行回数 (10 回)
• worst : 10 回の実行で最も実行時間が大きくかかったものを示す．
• pw : G のパス幅を示す．
4.3.2 実験の結果
実験 3 の結果について，表 4.7 から表 4.10 と，図 4.10 から図 4.18 に実験結果を示す．実験 2 同様に，辺
密度が大きくなると，パス分解に基づいた動的計画法である CDP が BT1 と BT2 の二つのバックトラックよ
りも速くなるという結果を得た．グラフ上の組み合わせ最適化問題の解法として，バックトラック解法は，メ
モリ消費が少ないが計算時間が入力の大きさとともに指数的に爆発し，パス分解に基づく動的計画法は，パス
幅の小さいときには有効であるが，パス幅の増大と共ににメモリ消費と実行時間がともに爆発的に増加するた
め，適用できる入力が限られる，と一般的に認識されている．実験の結果，彩色問題に対してはバックトラッ
ク法が予想以上に高速であることが判明した．特に，好適なパス分解に基づいた探索順序を用いたバックト
ラック法が，動的計画法よりも実験した範囲ではほとんどの場合に高速であるという事実は興味深く，彩色問
題に対する実用的なアルゴリズムを設計する上で重要な知見である．
25
表 4.8 実験 3 結果 (実行時間 (マイクロ秒)(P = 10)
BT1
BT2
BT3
CDP
pw
N
ave
worst
ave
worst
ave
worst
ave
worst
10
13.6
27.3
12.5
30.0
17.3
41.4
294.3
975.7
0
11
8.4
20.5
6.0
8.7
7.5
10.2
200.9
294.0
1
12
4.2
6.7
3.9
4.9
6.4
9.8
188.7
252.4
1
13
4.6
9.3
4.4
5.9
8.8
19.1
170.9
213.2
1
14
4.5
5.8
4.2
5.8
4.9
8.7
151.7
188.1
1
15
4.4
7.5
4.1
6.5
4.0
6.4
140.0
171.0
1
16
4.8
8.9
7.1
21.7
5.1
11.2
165.2
266.4
1
17
7.3
23.4
5.5
11.3
5.0
10.6
172.4
249.6
1
18
9.0
19.9
7.6
10.4
5.2
9.4
180.2
212.3
1
19
6.6
9.3
8.0
11.6
4.1
5.6
220.9
228.3
1
20
10.8
15.8
9.3
14.4
7.0
11.0
276.7
324.8
1
21
27.1
42.8
9.6
13.9
8.5
21.1
305.4
371.4
1
22
28.8
45.2
12.4
14.9
8.9
11.5
322.9
360.8
1
23
53.1
86.6
12.4
13.4
9.0
12.9
324.7
361.3
1
24
55.5
96.2
13.5
17.8
10.5
13.9
361.6
459.0
1
25
19.5
51.9
11.0
19.7
10.8
18.2
379.6
544.2
1
26
48.3
98.1
13.1
18.2
11.7
17.8
398.2
521.6
1
27
42.3
79.3
11.2
15.3
11.0
18.2
394.5
479.2
1
28
24.3
59.6
11.1
14.9
15.4
27.9
508.9
851.2
2
29
86.0
208.8
16.8
26.9
16.9
39.9
469.7
598.1
2
30
145.8
245.8
34.6
76.5
14.6
20.6
493.0
666.9
2
26
表 4.9 実験 3 結果 (実行時間 (ナノ秒)(P = 20)
BT1
BT2
BT3
CDP
pw
N
ave
worst
ave
worst
ave
worst
ave
worst
10
6.1
9.2
6.6
8.0
3.4
5.4
136.8
152.6
1
11
5.9
12.6
6.5
8.9
3.1
4.4
147.3
159.5
1
12
9.1
21.7
9.1
17.1
3.7
6.6
160.3
176.8
1
13
15.7
45.6
15.1
39.6
5.0
8.1
183.5
222.3
1
14
16.0
42.5
9.6
15.2
5.0
8.3
193.7
231.2
1
15
16.8
38.1
18.3
47.6
5.3
8.4
207.3
235.5
2
16
27.0
86.3
29.5
72.4
6.5
8.1
234.8
265.6
1
17
36.1
97.7
23.8
58.6
8.0
12.2
251.2
280.9
2
18
42.2
138.6
41.7
88.3
9.1
13.6
300.2
522.2
2
19
47.4
125.6
39.3
105.4
7.9
11.0
263.6
308.0
2
20
55.0
102.4
21.1
39.4
13.0
20.6
330.2
414.7
2
21
87.2
166.4
35.2
71.6
12.9
18.2
350.7
441.2
2
22
81.3
140.0
66.6
96.7
12.6
15.3
338.8
411.9
3
23
78.1
159.2
106.7
239.1
15.5
20.6
545.6
1057.1
3
24
148.7
300.2
69.7
140.9
16.0
26.4
519.3
1239.0
3
25
85.4
170.3
120.5
223.7
17.2
28.8
593.1
1166.8
3
26
94.9
177.5
67.6
204.9
28.4
86.1
760.9
1428.1
4
27
162.8
268.5
109.0
197.2
22.9
48.1
777.2
2165.3
4
28
245.6
516.8
81.9
196.3
25.6
36.5
1287.1
2581.6
5
29
156.4
307.0
109.5
284.8
39.0
138.5
1012.1
1283.8
5
30
102.7
143.3
129.4
238.1
31.3
81.3
1506.3
2287.5
5
27
表 4.10
実験 3 結果 (実行時間 (ナノ秒)(P = 30)
BT1
BT2
BT3
CDP
pw
N
ave
worst
ave
worst
ave
worst
ave
worst
10
7.5
15.6
9.6
26.1
3.4
5.0
134.3
149.4
1
11
10.3
20.9
10.9
21.3
5.3
9.9
161.4
194.3
1
12
13.0
23.9
13.9
44.1
5.8
9.8
183.2
237.0
1
13
15.9
34.2
17.8
30.2
5.9
7.8
189.7
213.6
1
14
28.1
90.8
24.4
63.9
6.6
9.2
206.7
268.6
2
15
28.4
103.6
31.5
98.9
7.9
13.7
232.8
326.8
2
16
21.8
38.4
21.6
31.4
8.8
15.3
259.4
417.5
3
17
71.7
193.0
39.4
102.7
10.3
17.3
291.7
449.1
3
18
24.9
63.4
50.5
83.6
8.7
19.8
271.4
443.7
3
19
63.1
190.6
53.2
148.4
11.5
17.3
380.2
767.8
4
20
83.7
216.0
65.9
147.2
19.6
28.3
486.3
632.7
4
21
50.3
99.6
51.8
78.9
18.7
44.2
533.6
1080.2
4
22
29.5
39.9
128.0
289.6
24.9
51.9
699.9
1172.6
5
23
231.7
502.8
88.3
161.6
39.5
94.7
796.4
1390.6
5
24
42.3
76.5
122.4
239.1
21.8
34.1
907.1
1432.5
5
25
41.8
49.5
371.8
997.9
41.0
78.4
850.5
1400.2
6
26
59.1
129.9
128.9
235.3
31.4
50.5
676.9
1170.2
6
27
159.9
257.9
67.8
89.0
128.0
288.2
882.9
1185.1
7
28
21.6
21.6
134.1
251.1
53.9
127.5
1290.4
2600.3
7
29
53.4
80.3
69.2
91.4
62.6
95.7
1334.5
2028.7
8
30
321.9
527.8
180.4
237.2
77.2
266.5
1345.0
2650.8
8
28
表 4.11
実験 3 結果 (実行時間 (ナノ秒)(P = 40)
BT1
BT2
BT3
CDP
pw
N
ave
worst
ave
worst
ave
worst
ave
worst
10
20.5
46.3
21.4
38.0
22.2
71.9
382.5
1139.5
2
11
11.3
24.3
8.9
14.5
10.4
15.0
180.7
328.4
2
12
14.2
27.4
17.1
35.5
12.5
25.5
172.5
269.1
2
13
14.7
24.4
17.3
28.2
10.3
19.3
185.5
310.1
3
14
22.4
52.8
21.9
55.6
8.9
11.8
178.8
213.5
3
15
30.6
71.6
26.5
44.7
10.4
22.5
208.2
344.3
3
16
26.8
79.3
29.8
56.1
10.2
14.7
376.6
1264.0
4
17
26.6
58.3
35.1
74.2
17.1
28.2
362.1
647.5
5
18
59.3
138.9
114.2
198.1
18.3
38.1
453.3
599.5
5
19
36.4
70.9
57.9
142.9
18.8
36.9
590.7
1687.6
5
20
62.8
171.7
84.2
204.9
21.1
42.3
760.9
1845.8
5
21
84.2
204.5
59.9
128.9
43.7
121.7
474.6
659.7
6
22
512.6
1058.6
326.0
680.8
66.4
146.2
614.1
1131.2
6
23
250.9
517.2
143.1
369.0
74.1
175.6
1709.7
5017.8
7
24
695.6
1389.6
215.6
281.0
90.6
194.4
966.6
2138.9
7
25
55.5
86.6
183.4
220.8
42.3
86.1
713.8
1180.3
7
26
362.3
667.8
91.9
136.6
68.9
147.7
2120.8
5098.7
7
27
85.6
85.6
451.3
585.6
69.6
137.1
878.6
2078.2
9
28
704.4
1012.4
1977.1
5416.8
134.7
284.8
983.0
1476.3
9
29
2157.7
3942.4
1937.4
2849.1
130.2
196.3
697.7
718.9
10
30
14507.4
21912.1
4665.0
7945.9
274.1
511.5
638.5
638.5
10
表 4.12 実験 3 パス幅による各アルゴリズムの実行平均時間 (マイクロ秒)
pw
BT1
BT2
BT3
CDP
0
13.6
12.5
17.3
294.3
1
17.2
10.1
6.5
225.2
2
46.0
24.7
11.6
310.7
3
58.0
54.1
11.9
339.2
4
80.3
62.9
18.5
552.5
5
99.3
95.1
25.7
837.6
6
174.4
221.6
45.6
654.0
7
257.7
139.3
76.3
1280.7
8
187.6
124.8
69.9
1339.8
9
395.0
1214.2
102.2
930.8
10
8332.5
3301.2
202.1
668.1
29
図 4.10
実験 3 結果 (P=10) 平均
図 4.11 実験 3 結果 (P=10) 最悪の場合
30
図 4.12
実験 3 結果 (P=20) 平均
図 4.13 実験 3 結果 (P=20) 最悪の場合
31
図 4.14
実験 3 結果 (P=30) 平均
図 4.15 実験 3 結果 (P=30) 最悪の場合
32
図 4.16
実験 3 結果 (P=40) 平均
図 4.17 実験 3 結果 (P=40) 最悪の場合
33
図 4.18 実験 3 パス幅による各アルゴリズムの平均実行時間
34
第5章
まとめ課題
実験 1 では，近似アルゴリズムの理論的な近似率よりも，はるかに小さく解を求めることができた．しかし
最適値を求めるバックトラック法に実行時間で劣ってしまう場合が多く，近似アルゴリズムの実用性を主張す
るために実装による工夫が必要であると考えられる．実験 2 では，好適なパス分解の導入頂点順に探索する
バックトラックアルゴリズムがほとんどの場合で他のアルゴリズムよりも高速に動作するという観察を得たの
で，その理由を追及することが今後の課題であると考える．
35
参考文献
[1] Gustedt, Jens, Ole A. Mhle, and Jan Arne Telle. The treewidth of Java programs. Algorithm
Engineering and Experiments. Springer Berlin Heidelberg, 2002. pp.86–97.
[2] K. Kitsunai, Y. Kobayashi, K. Komuro, H. Tamaki and T. Tano, Computing directed pathwidth
in O (1.89 n) time., Parameterized and Exact Computation., Springer Berlin Heidelberg, pp.182–
193,2012.
[3] Thorup, Mikkel. All structured programs have small tree width and good register allocation.,
Information and Computation 142.2 (1998): pp.159–181.
[4] Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos.
On exact algorithms for treewidth. Springer Berlin Heidelberg, 2006.
[5] Hans L. Bodlaender, A tourist guide through treewidth. , Acta cybernetica 11.1-2 (1994): 1.
36
謝辞
修士論文の作成に辺り，多くの方にご協力いただきました．
玉木先生，研究のためのご指導や，その他いろいろなことに相談にのっていただき，本当にありがとうござい
ました．先生のご協力無しには卒業できなかったかもしれません．
小林先輩，わからないところを何度も聞いたり，実験のための相談にのっていただいたりしました．ありがと
うございました．
橘内，小室，丸田，須田君，プログラムを提供してもらったり，日常的に楽しい時間を過ごさせてもらったり
しました．本当にありがとう．
荻窪，長澤，一緒に時間を過ごしてとても楽しかったです．ありがとう．
櫻田君，松井君，二人の幅広い知識に，何度も救われました．ありがとうございました．
また，玉木研で一緒だった，先輩や学部卒の同期のみなさん，今まで本当に楽しかったです．ありがとうご
ざいました．
最後に家族へ，大学 1 年からこれまで，学費や生活費の資金援助，また，たくさんの相談にのってもらって
本当にありがとうございました．何度も助けてくれて，本当にありがとうございました．
37

Download Report