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

Slides:



Advertisements
Similar presentations
<最適化の概念> 最適化すべき問 題 数学モデル 変数,数式 数理計画法 定められた計算手 順を用いて解くた めの方法論.
Advertisements

1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
2016 年度 計量経済学 講義内容 担当者: 河田 正樹
陰関数定理と比較静学 モデルの連立方程式体系で表されるとき パラメータが変化したとき 如何に変数が変化するか 至るところに出てくる.
放射線の計算や測定における統計誤 差 「平均の誤差」とその応用( 1H) 2 項分布、ポアソン分布、ガウス分布 ( 1H ) 最小二乗法( 1H )
Determining Optical Flow. はじめに オプティカルフローとは画像内の明る さのパターンの動きの見かけの速さの 分布 オプティカルフローは物体の動きの よって変化するため、オプティカルフ ローより速度に関する情報を得ること ができる.
0章 数学基礎.
凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
ゲーム理論・ゲーム理論Ⅰ (第8回) 第5章 不完全競争市場の応用
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
電気回路第1スライド4-1 電気回路第1 第4回 ー網目電流法と演習ー 目次 2網目電流の設定 (今回はこれだけです。)
Approximation of k-Set Cover by Semi-Local Optimization
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
香川大学工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学工学部 富永浩之
9.NP完全問題とNP困難問題.
最尤推定によるロジスティック回帰 対数尤度関数の最大化.
第 4 章 : 一般回路の定理 4.3 ノートンの定理 ノートンの定理 キーワード : ノートンの定理を理解する. 学習目標 :
需要の価格弾力性 価格の変化率と需要の変化率の比.
誤差の二乗和の一次導関数 偏微分.
Selfish Routing and the Price of Anarchy 第2回
Selfish routing 川原 純.
計算量理論輪講 岩間研究室 照山順一.
2.伝送線路の基礎 2.1 分布定数線路 2.1.1 伝送線路と分布定数線路 集中定数回路:fが低い場合に適用
第6章 カーネル法 修士2年 藤井 敬士.
本時のねらい 「相似の意味と性質を理解し、相似な図形の辺の長さや角度を求めることができる。」
シャノンのスイッチングゲームにおけるペアリング戦略について
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
確率・統計Ⅰ 第3回 確率変数の独立性 / 確率変数の平均 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
「三角形の面積の変化の様子を一次関数としてとらえることができる。」
7.4 Two General Settings D3 杉原堅也.
情報理工学系研究科 数理情報学専攻 数理第四研究室 博士三年 指導教員: 駒木 文保 准教授 鈴木 大慈 2008年8月14日
Basic Tools B4  八田 直樹.
第3回 アルゴリズムと計算量 2019/2/24.
§ , How Bad Is Selfish Routing?
電気回路学Ⅱ コミュニケーションネットワークコース 5セメ 山田 博仁.
25. Randomized Algorithms
Selfish Routing and the Price of Anarchy 4.3
計算量理論輪講 chap5-3 M1 高井唯史.
A First Course in Combinatorial Optimization Chapter
First Course in Combinatorial Optimization
等価電源の定理とは 複数の電源を含む回路網のある一つの端子対からその回路を見た場合、その回路は、単一の電源(電圧源或いは電流源)と単一のインピーダンスまたはアドミタンスからなるシンプルな電源回路と等価と見なせる。 ただし、上記の定理が成り立つためには、回路網に含まれる全ての電源が同一周波数(位相は異なっていても良い)の電源であることと、回路が線形である(重ね合わせの理が成り立つ)ことが前提となる。
様々な情報源(4章).
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
等価電源の定理とは 複数の電源を含む回路網のある一つの端子対からその回路を見た場合、その回路は、単一の電源(電圧源或いは電流源)と単一のインピーダンスまたはアドミタンスからなるシンプルな電源回路と等価と見なせる。 ただし、上記の定理が成り立つためには、回路網に含まれる全ての電源が同一周波数(位相は異なっていても良い)の電源であることと、回路が線形である(重ね合わせの理が成り立つ)ことが前提となる。
進化ゲームと微分方程式 第15章 n種の群集の安定性
4. システムの安定性.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
サポートベクターマシン Support Vector Machine SVM
補講:アルゴリズムと漸近的評価.
Selfish Routing 4章前半 岡本 和也.
第Ⅱ部 協力ゲームの理論 第14章 交渉集合.
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
Selfish Routing and the Price of Anarchy
解析学 ー第9〜10回ー 2019/5/12.
人工知能特論II 第8回 二宮 崇.
C:開放,L:短絡として回路方程式を解く
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
線形符号(10章).
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

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

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

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

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

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

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

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

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

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

例(電子回路) フロー = 電流 単位フロー当たりのコスト = 電圧 ce(f) fe = 電圧*電流 = 電力

例(電子回路) 電源が供給する電力  = フロー fP を流すことで生じるコスト

例(電子回路) 各電源が供給する電力の和 =各素子の消費電力の和

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最適フローの求め方 証明 最適解(最適フロー)をx*とする。

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

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