需要点、供給点、辺容量を持つ
木を分割するアルゴリズム
(Partitioning Trees with Supply,
Demand and Edge-Capacity)
西関研究室 M1309 川端真生
1
研究背景
• 電力配送問題
[伊藤 et al. ‘05]
– 各供給点はどの需要点にどれだけの電力を送れ
ばよいのか
– 各送電線には流せる電力量に上限（辺容量）が
ある [本研究]
2
分割問題
需要点
発電所
送電線
3
分割問題
需要点
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
辺を除去し, いくつかの連結成分に分割
供給点
需要点
4
分割問題
１３
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つの供給点
フロー
その供給量は需要量の合計以上
流れるフローは辺容量を超えない（フロー≦辺容量）5
分割問題
結果
• （辺容量のない）一般のグラフ対してＮＰ完全
[伊藤 et al. ‘05]
• （辺容量のある）木に対して
線形時間アルゴリズムを与えた
6
最大分割問題
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
辺容量
供給点
需要点
分割はない
電力が供給される需要量を最大にする
7
最大分割問題
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
辺容量
供給点
需要点
電力が供給される需要量を最大にする
8
最大分割問題
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
辺容量
供給点
需要点
電力が供給される需要量を最大にする
9
最大分割問題
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
辺容量
供給点
需要点
電力が供給される需要量を最大にする
10
最大分割問題
結果
• （辺容量のない）木に対してすらＮＰ困難
[伊藤 et al. ‘05]
• (辺容量のある)木に対してアルゴリズムを与えた
– 擬多項式時間
– ＦＰＴＡＳ
• 任意の誤差εについて,nとεの多項式時間である
極めてよい近似アルゴリズム
n:点数
11
最大分割問題アルゴリズム
需要点
• 入力：
– 木（需要点,供給点,辺容量）
17
• 出力：
6
– 最大分割
• 供給される需要点の需要量
が最大になる分割
• 時間計算量
– 擬多項式時間（
辺容量
5
10
5
28
25
15
7
8
4
供給点
）
n:点数
=min{22,30}=22
５＋６＋７＋４＝２２
２５＋５＝３０
12
擬多項式時間アルゴリズム
• 動的計画法
– 小さな部分解からより大きな部分解を計算する
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
13
•
5
2
6 7
3
5
10
20
2
4
2
5
7
10
6
5
14
•
2
2
7
6
3
5
10
20
5
10
4
2
5
6
5
15
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
16
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
17
23
22
5
5
8
3
2
0
1
0
4
2
1
0
7
1
0
3
4
充足量＝max{23,22}=23
2
6
8
4
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
18
time
・一つの表に対して
・ 高々
合計 :
で計算できる
回の表の更新を行う
19
FPTAS(Fully Polynomial-Time
Approximation Scheme)
• 完全多項式近似スキーム
０＜ε＜１なる任意の精度εに対して
最大化問題
最適解： f
近似解： f A
• f A (1 ) f
計算時間がnと1/εの多項式になる
20
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
21
FPTAS
• 時間計算量
– 擬多項式時間
FPTAS
md : 最大の需要量
22
結論
• 辺容量のある木に対する
– 分割問題
• 線形時間アルゴリズム
– 最大分割問題
• 擬多項式時間アルゴリズム
• FPTAS
を与えた.
23
課題
• より大きなグラフのクラスについて
直並列グラフ
考える.
• 計算時間量の削減.
FPTAS
Proceeding
M. Kawabata and T. Nishizeki, “Partitioning trees with supply, demand and edgecapacity”, in Proc. of ISORA 2011, Lecture Notes in Operation Research, Vol. 14(2011),
pp. 51-58.
24
© Copyright 2024 ExpyDoc
