情報学研究科 通信情報システム専攻 小野寺研究室 M１ 奥村 佳弘

Presentation on theme: "情報学研究科 通信情報システム専攻 小野寺研究室 M１ 奥村 佳弘"— Presentation transcript:

1 情報学研究科 通信情報システム専攻 小野寺研究室 M１ 奥村 佳弘
２章 Preliminaries(準備) 情報学研究科　通信情報システム専攻 小野寺研究室 M１　奥村　佳弘

2 発表構成 定義 コスト関数、総コスト（目的関数） ナッシュ均衡、ナッシュフロー 最適フローの定義、無秩序の代償 最適フローの求め方 前提条件
証明 計算量

3 定義 想定するモデル ネットワーク は有向グラフ G であらわされる フローはノード（頂点）からノードへ流れる
フローの始点siと終点tiの組をcommodity iという Commodityを１組だけ含むネットワークを single-commodity、 ２組以上含むならmulti-commodityと呼ぶ

4 定義 想定するモデル エッジ e に流れるフローの総量を fe で表す エッジ e の単位フローあたりのコストを ce(fe)で表す
グラフ G に含まれるエッジの集合をEと表す エッジの連なりのうち、サイクルを持たないも のをパスと呼ぶ

5 定義 想定するモデル トラフィックレート ri ＝siから湧き出すフローの総量 ＝tiへ吸い込まれるフローの総量
siからtiへ至るパスの集合Pi 全てのsi-tiの組におけるPiの集合P パスPに流れるフローの大きさ fP

6 fe 、 fP 、 ri の関係 フロー f を与えられれば、 fe 、 fP 、 ri は 一意に定まる

7 コスト関数 エッジ e のフローあたりのコストは、エッジに 流れるフローの総量に依存し、 コスト関数 ce(fe) であらわされる
feはフロー f により定まるので、ce(f)はce(fe) と同義である コスト関数は非負、連続、非減少関数である エッジ e で発生するコストはce(f) feである

8 パスのコスト パスの単位フローあたりのコストcP(f)とは、 パス上の全エッジについて、単位フロー 当たりのコストce(f)を足し合わせたもので ある

9 ネットワークの総コスト ネットワークは(G,r,c)で表わされる あるフロー f におけるネットワークの総コ ストC(f)は次式で定義される
r ：si-ti間に流れるフローの総量(i=1,2,…k) c ：各エッジ e (e ∈ E)のコスト関数 あるフロー f におけるネットワークの総コ ストC(f)は次式で定義される C(f)の最小化が目的

10 例（電子回路） フロー　＝　電流 単位フロー当たりのコスト　＝　電圧 ce(f) fe　＝　電圧＊電流　＝　電力

11 例（電子回路） 電源が供給する電力　 ＝　フロー fP　を流すことで生じるコスト

12 例（電子回路） 各電源が供給する電力の和 ＝各素子の消費電力の和

13 ナッシュ均衡、ナッシュフロー 各フロー（交通量）に属するどの エージェント(車１台）も他のパスへ行こう としない状態 （＝自分のいるパスが最も単位フローあ たりのコストが少ない） si-ti間のパスPiのうち任意のパスP1、P2 について次の関係が成り立つ （ただし、P１を通るフローは０でない） ナッシュ均衡状態にあるフローをナッシュ フローと呼ぶ （必要十分条件）

14 ナッシュフロー ナッシュフローにおいては、各commodity において、正のフローが流れる全てのパ スの単位フローあたりのコストは等しい。
このコストをcommon costと呼び、 commodity i のcommon costをci(f)で表す commodity数をk個とすると、総コストC(f) は次式で表わされる

15 ナッシュフロー その他の命題 どんな(G,r,c)で与えられるネットワークにも ナッシュフローは存在する
f と f~ がともにナッシュフローであるとき、 C(f) = C(f~) となる 証明は２章の６節にあるが、ここでは触れられ ていない

16 最適フロー 与えられた（G,r,c）において、C(f)を最小 にするようなフロー f を最適フローといい、 f*で表す
ナッシュフロー 上に全部流れる C(f)=1 最適フロー 上に半分 下に半分流れる C(f)=0.5* *1=0.75 与えられた（G,r,c）において、C(f)を最小 にするようなフロー f を最適フローといい、 f*で表す ナッシュフロー は 最適フロー と同じとは 限らない

17 無秩序の代償 無秩序の代償とは、ナッシュフローにおける 総コストが、最適フローに対しどれだけの比 率であるかを示す
上に全部流れる C(f)=1 最適フロー 上に半分 下に半分流れる C(f)=0.5* *1=0.75 無秩序の代償とは、ナッシュフローにおける 総コストが、最適フローに対しどれだけの比 率であるかを示す C(f*)=0 のとき、 C(f)=0 なのでρ= 1 とする 上の例では ρ= 4/3 となる

18 最適フローの求め方 前提条件 コスト関数は連続的微分可能である コスト関数はsemiconvexである
関数f(x)がsemiconvexとは、関数f(x)・xが凸 関数(convex function)であることを意味する。 semiconvex な関数の例 f(x)=1 f(x)・x = x (凸関数) semiconvex でない関数の例 擬似的なステップ関数

19 最適フローの求め方 前提条件 C(f)の最小化を目的関数とする （G,r,c）は与えられている →自由度はfP、feの大きさだけ
各フローは非負

20 最適フローの求め方 求め方 各エッジのコスト関数c(fe)について、次式 に従い c*(fe) を定義する
(G, r, c*)のナッシュフロー ＝(G, r, c)の最適フロー

21 最適フローの求め方 証明 コスト関数は連続的微分可能である コスト関数はsemiconvexである コスト関数は非負、非減少関数である
エッジに流れるフロー fe は非負である → ce(fe) feは下に凸な関数となる he(fe) = ce(fe) fe とおく

22 最適フローの求め方 証明 以下の非線形計画法の問題を解く Min

23 最適フローの求め方 証明 （G,r,c）は与えられている →自由度はfP、feの大きさだけ →fP、feの大きさを変数として、 （パス数＋エッジ数）次元のユークリッド 空間で最適解を探す hは凸関数なので実行可能な任意の２点 x,yについて、次式が成り立つ

24 最適フローの求め方 証明 次の４つが等価であることを証明する (a) ｆ*が最適フローであること
(b) 全てのcommodityのパスP1P2について次 式が成り立つ(ｆP1 > 0) (c) 任意のフロー f において次式が成り立つ (d) 任意のフロー f において次式が成り立つ

25 最適フローの求め方 証明 (ｃ) ⇔ (ｄ)は式変形より となるので自明

26 最適フローの求め方 証明 (ｂ)→（ｃ）を証明する h’P(f*)は定数である 各パスに流れるフローの合計は一定である
新たにフローを振り分けてもそれ以上減少 することはない

27 最適フローの求め方 証明 (a) → (b)はP1からP2へフローがλ移動した として、コストを計算することで証明する
(結論)最適フローなら （ （a）より ）

28 最適フローの求め方 証明 (d) → (a)をh(x)が凸関数であることを利用し て証明する (結論) なら最適フロー
(結論) 　　なら最適フロー 最適フローの定義は C(f) ≧ C(f*) 最適解（最適フロー）をｘ*とする。

29 最適フローの求め方 証明 最適解（最適フロー）をｘ*とする。

30 最適フローの求め方 証明 以上より、 (a)→ (ｂ)→ (ｃ)→ (ｄ)→ (a) の証明ができたので、 (a) ⇔ (ｂ)であることが言える (b)は最適フローである必要十分条件 全てのcommodityのパスP1P2について が成り立つ(ｆP1 > 0) フローが最適フロー 　　　　　　　　とおくと →ナッシュフローの条件式と同じ

31 計算量 本来、最適フローを非線形計画法で求め る計算量は指数オーダーになる
最適フローを求める問題をナッシュフ ローを求める問題とすることにより、 多項式時間で近似解を見つけることが可 能になる