需要点,供給点,辺容量を持つ木の分割アルゴリズム

Presentation on theme: "需要点,供給点,辺容量を持つ木の分割アルゴリズム"— Presentation transcript:

1 需要点,供給点,辺容量を持つ木の分割アルゴリズム
　　　　　　　　　　西関研究室　７６７１ 　　　　　　　　　　　　　　　川端　真生

2 研究背景 電力配送問題 供給点はどの需要点にどれだけの電力を送ればよいのか 送電線には送電量の制限がある

3 分割問題 需要点 発電所 送電線

4 分割問題 供給可能な量 需要点 供給点 必要な電力 4

5 分割問題 供給可能な量 需要点 供給点 辺容量 必要な電力 辺容量 供給点 需要点 辺を除去し, いくつかの連結成分に分割

6 分割問題 １３ １８ １５ １８ 辺容量 供給点 需要点 各成分にちょうど1つの供給点 供給量は需要量の合計以上 辺容量を超えない

7 最大分割問題 辺容量 供給点 需要点 分割はない 電力が供給される需要量を最大にする 分割を考えたとき 7

8 最大分割問題 =49 8 １７ 8 16 辺容量 供給点 需要点 電力が供給される需要量を最大にする 8

9 研究結果 分割問題 既存の研究 （辺容量を考えない） 自分の結果 （辺容量を考慮） 最大分割問題 グラフの形 一般 NP完全 木 線形時間
擬多項式時間アルゴリズム FPTAS (完全多項式近似スキーム)

10 FPTAS(Fully Polynomial-Time Approximation Scheme)
完全多項式時間近似スキーム 誤差 　　計算時間 10

11 まとめ 分割問題 木に対して解く線形時間アルゴリズム 最大分割問題 木に対して解く擬多項式時間アルゴリズム 木に対して解くFPTAS 11

12 今後の課題 グラフの形を限定した場合 木より広いグラフのクラス 計算時間量の短縮 FPTAS 12

13

14 予備スライド

15 直並列グラフ

16 分割問題アルゴリズム 線形時間で解ける 子がすべて葉である点に対して操作を行う. 子が葉である点が需要点or供給点 葉が需要点or供給点
16

17 分割問題　例 17

18 最大分割問題アルゴリズム 木Tの葉から根に対してDP（動的計画）法を適用する. 擬多項式時間アルゴリズムである. 18

19 最大分割問題アルゴリズム 部分木がある需要量が供給されたときの 余裕量 不足量 を計算する 5 8 4 15 3 10 7 20 7 5 9 7 1 10 4 16 7 9 14 4 20 6 8 15 2 19

20 FPTAS 擬多項式時間アルゴリズムを変更する. 満たされる需要量を　ずつ計算する. 20

21 アルゴリズム（工夫） 分割問題 場合分けの操作方法の拡張 最大分割問題 実際の余裕量と不足量を求める関数 21

22 最大分割問題アルゴリズム 22