需要点、供給点、辺容量を持つ木を分割するアルゴ

需要点、供給点、辺容量を持つ
木を分割するアルゴリズム
関西学院大学川端真生
西関隆夫
1
研究背景
• 電力配送問題
[伊藤 et al. ‘05]
– 各供給点はどの需要点にどれだけの電力を送れ
ばよいのか
– 各送電線には流せる電力量に上限（辺容量）が
ある [本研究]
2
分割問題
需要点
発電所
送電線
3
分割問題
需要点
供給可能な
量
供給点
必要な電力
8
25
7
2
15
8
3
4
2
20
5
3
7
1
18
6
8
4
分割問題
需要点
8
供給点
15
25
7
辺容量
必要な電力
3
12
2
6
11
10
7
供給可能な
量
Yes, No 判定問題
2
3
20
8
7
7
7
1
15
15
辺容量
5
7
20
8
8
4
12
18
15
6
11
8
辺を除去し, いくつかの連結成分に分割
供給点
需要点
5
分割問題
１３
15
8
8
7
１５
供給点
需要点
7
3
3
12
2
6
5
20
Yes, No 判定問題
8
6
5
2 10
11 3
77
1 7
2
3
7
1
15 7
15
辺容量
25
１８
7
8
20
8
8
4
4
12
18
14
15
6
8
11
8
１８
各成分にちょうど1つの供給点
フロー
その供給量は需要量の合計以上
流れるフローは辺容量を超えない（フロー≦辺容量）6
分割問題
結果
• （辺容量のない）一般のグラフ対してＮＰ完全
[伊藤 et al. ‘05]
• （辺容量のある）木に対して
線形時間アルゴリズムを与える
7
最大分割問題
7
6
8
9
8
6
15
14
1
6
20
9
17
10
2
9
5
5
6
23
7
13
3
8
3
4
15
8
7
2
8
7
4
辺容量
供給点
需要点
分割はない
電力が供給される需要量を最大にする
8
最大分割問題
8
7
14
6
8
9
8
8 7
1
15
6
15
3
5
14 14
10 8
5 3
6
6
20
9 8
17
8
2
9
23
7 2
13
3
8
4
2
充足量：４５
15
12
8
7 4
8
7
4
辺容量
供給点
需要点
電力が供給される需要量を最大にする
9
最大分割問題
7
6
8
9
8
6
15
14
1
6
20
9
17
10
2
9
5
5
6
23
7
13
3
8
3
4
15
8
7
2
8
7
4
辺容量
供給点
需要点
電力が供給される需要量を最大にする
10
最大分割問題
8
7
17
6
8
9
8 7
8
16
6
15
3
5
14 6
10 8
5 3
6 5
1
20
6
9 8
13 11
7 2
17
2
3
2
9
4
2
8
23
充足量：49
15
13
8
7
8
7
4
辺容量
供給点
需要点
電力が供給される需要量を最大にする
11
最大分割問題
結果
• （辺容量のない）木に対してすらＮＰ困難
[伊藤 et al. ‘05]
• (辺容量のある)木に対してアルゴリズムを与える
– 擬多項式時間
– ＦＰＴＡＳ
n:点数
• 任意の誤差εについて,nとεの多項式時間である
極めてよい近似アルゴリズム
12
分割問題アルゴリズム
需要点
• 入力：
– 木（需要点,供給点,辺容量）
17
• 出力：
6
– 分割がある
– 分割がない
28
25
• 時間計算量：
辺容量
5
10
5
15
7
8
4
供給点
– 線形時間
n:点数
13
分割問題アルゴリズム
9
14
26
4
19
7
4
1
1
3
26
32
32
12
14
7
5
45
14
7
9
4
3
1
2
8
5
14
分割問題アルゴリズム
7
需要量≦辺容量
需要量＞辺容量
1
12
14
3
14
4
1
9
4
19
7
4
1
1
3
26
32
32
12
14
7
5
分割なし
26
45
14
7
9
4
3
1
2
8
5
15
分割問題アルゴリズム
7+1+3
7
5
4
1
3
9
12
14
14
需要量≦辺容量
19
7
4
1
11
5
3
12
26
14
4
26
32
32
12
14
7
5
45
14
7
9
4
3
1
2
8
5
16
分割問題アルゴリズム
11
11
12
9 12
14
14
12
min{14,12}
4
19
32
26
32
11
12
14
7
5
26
45
14
7
9
4
3
1
2
8
5
17
分割問題アルゴリズム
11
1
12
9
14 12－11
12
26
4
19
26
32
32
11
12
12
7
5
45
14
7
9
4
3
1
2
8
5
18
分割問題アルゴリズム
9
14
26
4
19
1
26
32
32
7
5
45
14
7
9
4
3
1
2
8
5
19
分割問題アルゴリズム
9
14
26
4
19
1
26
32
27
45
14
7
9
4
3
1
2
8
5
20
分割問題アルゴリズム
9
14
26
4
19
1
32
27
26
45
14
10
9
8
5
21
分割問題アルゴリズム
9
14
26
4
19
1
32
27
26
45
14
10
14
22
分割問題アルゴリズム
9
14
26
23
26
45
14
10
14
23
分割問題アルゴリズム
9
14
23
26
2
24
分割問題アルゴリズム
5
分割あり
25
分割問題アルゴリズム
分割あり
9
14
26
9
4
19
26
32
13
7
4
1
1
35
3
32
11
45
14
7
9
10 14
12
5 7
1
2
3
5 8
14
5
1
2
5
4
26
分割問題アルゴリズム
9
14
26
4
7
19
12
18
10
1
4
8
3
7
25
27
14
7
4
6
3
8
3
1
4
27
分割問題アルゴリズム
9
14
4
19
8
26
7
12
18
10
6
28
分割問題アルゴリズム
9
14
8
26
7
29
分割問題アルゴリズム
16
分割はない
時間
30
最大分割問題アルゴリズム
需要点
• 入力：
– 木（需要点,供給点,辺容量）
17
• 出力：
6
– 最大分割
• 供給される需要点の需要量
が最大になる分割
• 時間計算量
– 擬多項式時間（
辺容量
5
10
5
28
25
15
7
8
4
供給点
）
n:点数
=min{22,30}=22
５＋６＋７＋４＝２２
２５＋５＝３０
31
擬多項式時間アルゴリズム
• 動的計画法
– 小さな部分解からより大きな部分解を計算する
5
8
4
3
2
10
20
10
6
7
3
10
4
2
6
5
1
14
15
7
10
5
4
4
2
32
擬多項式時間アルゴリズム
目的：木全体での最大分割を求めたい
5
での電力の流れはど
うなるか
5
4
2
の外へ出ていく
の中へ入ってくる
2 には流れない
動的計画法で計算する
10
6
7
3
10
10
20
3
4
2
6
5
1
14
15
7
10
5
4
4
2
33
• 出分割
:部分木が以上の需要を満たすとき、
からの外にどれだけの電力を供給できるか
その最大値
３＋２＋５＋２＝１２≧１０=x
3
5
2
7
5
6
3
5
2
10 4
20
2
10
5
6
5
34
• 出分割
:部分木が以上の需要を満たすとき、
からの外にどれだけの電力を供給できるか
その最大値
３＋２＋５＝１０≧１０ =x
4
5
2
3
6
6
7
10
9
10 4
20
2
5
6
5
35
•
5
2
6 7
3
5
10
20
2
4
2
5
7
10
6
5
１３
36
• 出親分割
:部分木が以上の需要を満たすとき、実際に
からの親
にどれだけの電力を供給できるか
その最大値
・・・
37
• 入分割
:部分木が以上の需要を満たすために、
の外からへ入れないといけない最小の電力
3
５＋４＋３＝１２≧１０ =x
5
3
10
5
9
9 4
10
8
6
4
2
7
4
38
• 入分割
39
• 入親分割
:部分木が以上の需要を満たすために、
からへ入れないといけない最小の電力
・・・
40
• 孤立分割
に電力を供給しないとき、
部分木は以上の需要を満たせるか
:
５＋６＋７＝１８≧１７ =x
5
2
9
6
16
11
15
7
5
12
7
8
5
3
2
7
7
10
13
存在しない
41
• 孤立分割
42
5
8
4
2
10
20
3
10
6
7
3
10
4
2
6
5
1
14
15
7
10
5
4
4
2
43
5
8
4
2
10
20
3
10
6
7
3
10
4
2
6
5
1
14
15
7
10
5
4
4
2
44
擬多項式時間アルゴリズム
23
22
5
5
8
8
4
4
充足量＝max{23,22}=23
3
2
6
1
0
3
2
0
1
0
4
2
1
0
7
1
6
5
1
5
1
4
7
1
0
6
5
2
0
1
0
7
4
2
1
0
1
0
3
4
4
2
3
2
1
6
5
1
1 4
5
7
1
0
5
4
4
2
45
計算時間量
• 各 x （ 0  x  F ）の値に対して
各y （ 0  y  F ）の中から最大値を探す
F 時間で求まる
⇒各
時間
46
計算時間量
時間
時間
時間
47
計算時間量
• 各 x （ 0  x  F ）の値に対して
各y （ 0  y  F ）の中から最大値を探す
F時間で求まる
⇒各
⇒１つの表に対して
5
4
8
• 葉から根まで計算する
⇒高々 2n 回
2
6
(点数＋合成回数)
• 合計 O( F n)
2
3
10
20
4
2
3
10
7
10
6
5
1
14
15
7
10
5
4
4
2
48
FPTAS(Fully Polynomial-Time
Approximation Scheme)
• 完全多項式近似スキーム



０＜ε＜１なる任意の精度εに対して
最大化問題
最適解： f
近似解： f A
• f A  (1   ) f
計算時間がnと1/εの多項式になる
49
FPTAS
• 擬多項式時間アルゴリズムを変更する
Fの値まで1ずつ計算する
t
md : 最大の需要量
8
2
6
１t
7
3 10
10 4 6
20 2 5
5
4
10
1
14
15
3
7 5
10 4
4
2
50
FPTAS
最適解
t
2nt
近似解
51
FPTAS
• t ごとに計算している
1回計算するごとに
誤差がt 生じる
各点誤差t
合成回数:n-1
• 木全体で誤差は高々2nt
nt+(n-1)t
52
FPTAS
最適解
近似解
md : 最大の需要量
53
FPTAS
• 時間計算量
– 擬多項式時間
FPTAS
md : 最大の需要量
54
結論
• 辺容量のある木に対する
– 分割問題
• 線形時間アルゴリズム
– 最大分割問題
• 擬多項式時間アルゴリズム
• FPTAS
を与えた.
55
課題
• より大きなグラフのクラスについて
考える.
直並列グラフ
• 計算時間量の削減.
FPTAS
56

Download Report