スライド 1

需要点,供給点,辺容量を持つ木
の分割アルゴリズム
西関研究室７６７１
川端真生
研究背景
• 電力配送問題
– 供給点はどの需要点にどれだけの電力を送れば
よいのか
– 送電線には送電量の制限がある
2
分割問題
需要点
発電所
送電線
3
分割問題
需要点
供給点
供給可能な
量
必要な電力
4
分割問題
需要点
供給点
辺容量
供給可能な
量
必要な電力
辺容量
辺を除去し, いくつかの連結成分に分割
供給点
需要点
5
分割問題
１３
１８
１５
辺容量
供給点
需要点
１８
各成分にちょうど1つの供給点
供給量は需要量の合計以上
辺容量を超えない
6
最大分割問題
辺容量
供給点
需要点
分割を考えたとき分割はない
電力が供給される需要量を最大にする
7
最大分割問題
8
１７
8+17+8+16
8
16
=49
辺容量
供給点
需要点
電力が供給される需要量を最大にする
8
研究結果
既存の研究
（辺容量を考えない）
自分の結果
（辺容量を考慮）
一般
NP完全
NP完全
木
線形時間
線形時間
木
NP困難
擬多項式時間アルゴリズム
FPTAS
(完全多項式近似スキーム)
NP困難
擬多項式時間アルゴリズム
FPTAS
グラフ
の形
分割問題
最大分割問題
9
FPTAS(Fully Polynomial-Time
Approximation Scheme)
• 完全多項式時間近似スキーム
•
OPT：最適解
P：近似解
• 誤差
計算時間
10
まとめ
• 分割問題
– 木に対して解く線形時間アルゴリズム
• 最大分割問題
– 木に対して解く擬多項式時間アルゴリズム
– 木に対して解くFPTAS
11
今後の課題
• グラフの形を限定した場合
– 木より広いグラフのクラス
• 計算時間量の短縮
– FPTAS
12
13
予備スライド
14
直並列グラフ
分割問題アルゴリズム
• 線形時間で解ける
• 子がすべて葉である点に対して操作を行う.
– 子が葉である点が需要点or供給点
– 葉が需要点or供給点
16
分割問題例
17
最大分割問題アルゴリズム
• 木Tの葉から根に対してDP（動的計画）法を適
用する.
• 擬多項式時間アルゴリズムである.
18
最大分割問題アルゴリズム
部分木がある需要量が
供給されたときの
余裕量
不足量
を計算する
5
8
4
3
15
16
20
7
20
9
7
7
6
9
8
10
1
14
15
7
10
5
4
4
2
19
FPTAS
• 擬多項式時間アルゴリズムを変更する.
• 満たされる需要量をずつ計算する.
t
ε md
2n
md : 最大の需要量
20
アルゴリズム（工夫）
• 分割問題
– 場合分けの操作方法の拡張
• 最大分割問題
– 実際の余裕量と不足量を求める関数
21
最大分割問題アルゴリズム
22

Download Report