計算量理論 第3章 4節 社会情報学専攻 ナレッジクラスタ講座M1 岩木 祐輔 前回までの話 その1 • ナッシュフロー – みんなが利己的にふるまったとき（ナッシュ均衡） のフロー • 最適フローを求めるには？ – を求めて – そのナッシュフローを計算 • 無秩序の代償 前回までの話 その2 • 無秩序の代償はどのくらいか? – 上は？ rは総トラフィック ・・・定数 無秩序の度合い 直感的には 「利己的な振る舞い（ナッシュフロー）が いかに迷惑になるか」の度合い 今回の話 • いろんなネットワークを考えて 上の関係の等号が成り立つのか？ • 考える事例 – Cが定数関数を含むとき(これまでの話) – Cがdiverseのとき – Cがinhomogeneousのとき (定義は後ほど…) 今回の話(結論から) • 2-Link,2-Nodeの時に最悪なことが起こるのは – Cが定数関数を含むとき(これまでの話) • m-Link,2-Nodeの時に 〃 – Cがdiverseのとき • パスの結合なグラフの時に – Cがinhomogeneousのとき 〃 ・ ・ ・ 注 「必ず起こる」かどうかについては言及されていない まずは関数の形に注目 （準備）コスト関数の図形的理解 「最善の関数」 • 無秩序の度合い(anarchy value) – ルーティングの話は抜きに 関数の式の形だけで見ると… – コスト関数が定数なら 20 • つねに1 – 〃 15 単調増加なら 10 • 最小値は1 →定数が「最善の関数」 5 1 1 2 3 4 5 6 「最悪の関数」 • 無秩序の度合い(anarchy value) 20 15 10 この部分が 大きいほど悪い 5 1 2 3 4 1.0 1.0 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 0.0 1 0.2 0.4 0.6 0.8 1.0 0 1 2 3 4 5 5 6 (本題) Cの性質を考慮して 無秩序の代償を 分析する 今回の話 • 2-Link,2-Nodeの時に最悪なことが起こるのは – Cが定数関数を含むとき(これまでの話) • m-Link,2-Nodeの時に 〃 – Cがdiverseのとき • パスの結合なグラフの時に 〃 – Cがinhomogeneousのとき ・ ・ ・ Cがdiverse(多様) • 関数集合Cが多様である を満たすような が存在する。 例 Cがdiverseのとき • 命題 ・ ・ ・ 2-node,m-edge ならば以下が成立する 証明(1/4) となるような Cは多様なので 右図のように が取れる ここで、下のようなグラフ (もっとも最悪なケース)の 最適フローを考える ・ ・ ・ 最適フロー を選ぶ 証明(2/4) ・ ・ ・ δ 最適フロー どんなδに対してもmが十分に大きくとれば が成り立つ。(コスト関数は連続なので) 証明(3/4) ・ ・ ・ ・ ・ ・ ナッシュフロー 最適フロー 証明(3/4) ・ ・ ・ ・ ・ ・ ナッシュフロー 最適フロー 証明(3/4) ・ ・ ・ ・ ・ ・ ナッシュフロー 最適フロー 証明(4/4) δ→0とすると ・・・ なので、 εは任意に小さく取れるので、 の定義そのもの 今回の話 • 2-Link,2-Nodeの時に最悪なことが起こるのは – Cが定数関数を含むとき(これまでの話) • m-Link,2-Nodeの時に 〃 – Cがdiverseのとき • パスの結合なグラフの時に – Cがinhomogeneousのとき 〃 Cがhomogeneous(一様) • 関数集合Cが一様である Cが一様ではない Cが多様 一様でない 一様でも多様でもない例 多様 Cが一様でないとき • 命題 ・ ・ ・ union of path(パスの結合) ならば以下が成立する Cが一様でないとき • 証明の方針 変換 Cは一様でない ・ ・ ・ Cは多様 ・ ・ ・ 証明(1/4) まず、Cを以下のように拡張して考える Cは一様ではないので、 となるcが必ず存在するので、 20 は多様である 15 また、β倍しても無秩序の度合いは等しいので 10 5 1 1 2 3 4 5 6 証明(2/4) フローは途中でなくなったりしないので 上のような直列のパスの全体のコスト関数をcとすると 等価 証明(3/4) ・ ・ ・ ・ ・ ・ 以下の条件を満たすように 各枝をそれぞれ(うまく)スカラー倍 m-link, 2-nodeの場合に帰着 ・ ・ ・ 証明(4/4) は多様であるから、 ・ ・ ・ より、 ・ ・ ・ m-link, 2-nodeの場合に帰着 εは任意に小さく取れるので、 ここまでのまとめ • 2-Link,2-Nodeの時に最悪なことが起こるのは – Cが定数関数を含むとき • m-Link,2-Nodeの時に 〃 – Cがdiverseのとき • パスの結合なグラフの時に – Cがinhomogeneousのとき 〃 さらに一般化すると・・・ グラフ集合Gの性質を考慮する グラフ集合Gがtrivial • グラフ集合Gがtrivialであるとは すべてが「一本道の集合」であること このとき、 これは自明。 • Gがnon-trivialならば 計算量理論 第3章 5節 これまで • いろいろな形のネットワークで 「最悪の場合」を見つけて、 無秩序の代償の上限を求めた ・ ・ ・ ・ ・ ・ 今回の話 1. コスト関数が「多項式だけ」であるとすれ ば？ 2. コスト関数がM/M/1(待ち行列)関数なら？ • 結論から言うと、 – 「無秩序の代償は変化率の大きい関数でない 限り、小さい」 (1より) – 「無秩序の代償は、トラフィックがに余裕が あれば、小さい」 (2より) コスト関数が多項式のとき • 命題 以下が成り立つ コスト関数が多項式のとき • 証明の方針 変換 ・ ・ ・ ・ ・ ・ ･･･一様でない ･･･多様 証明(1/4) 直列につないだ場合の無秩序の代償 を に内分する点 証明(2/4) 直列につないだ場合の無秩序の値 証明(2/4) 直列につないだ場合の無秩序の値 証明(2/4) 直列につないだ場合の無秩序の値 20 15 10 5 1 1 2 3 4 5 6 証明(3/4) ナッシュフロー r 最適フロー 証明(4/4) ここまで示された 証明(4/4) (ロピタルの定理を2回使う、詳細は略) コスト関数が多項式のとき 「無秩序の代償は変化率の大きい関数でない限り、小さい」 コスト関数がM/M/1関数のとき (引用： http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/?ST=start2) コスト関数がM/M/1関数のとき ナッシュフロー r 最適フロー コスト関数がM/M/1関数のとき ↑ 「トラフィックに余裕があれば、利己的ルーティングでもよい」 計算量理論 第3章 6節 今回の話 • 結論だけ先に言うと 最適化を頑張ることより 道路改良を行うほうがよい トラフィックが増えると･･･ r=1のとき トラフィックが増えると･･･ r=1のとき r=2のとき トラフィックが増えると･･･ r=1のとき r=2のとき トラフィックが増えると･･･ ナッシュフローの コストは1 r=1のとき 最適フローの コストは7/4 r=2のとき トラフィックの増加 • 命題 のナッシュフロー の最適フロー とすると、 が成り立つ。 トラフィックの増加 • 命題（ ）のとき のナッシュフロー の最適フロー とすると、 が成り立つ。 証明(1/4) • コスト関数を変換 証明(2/4) のナッシュフロー の最適フロー 証明(2/4) のナッシュフロー 最適フロー の最適フロー について、 の代わりに コストの増加分はせいぜい を用いた際の 程度。 証明(3/4) 単位フローあたりのコスト 証明(3/4) 単位フローあたりのコスト ナッシュフローなので、定数 証明(3/4) 単位フローあたりのコスト 証明(3/4) 単位フローあたりのコスト 証明(4/4) 以上の2式 より、 が成り立つ。 逆の発想 先の命題の仮定 のナッシュフロー の最適フロー 2倍のフローを流したとき 単位フロー当たりのコストが半分 ＝ 2倍のフローを流したとき 総コストが等しい とすると、 逆の発想 先の命題の仮定 のナッシュフロー の最適フロー とすると、 のナッシュフロー の最適フロー とすると、 まとめ のナッシュフロー の最適フロー ・・・ 2倍のトラフィックがあっても 単位フロー当たりのコストがもとの半分 とすると、 最適化を頑張ることより 道路改良を行うほうがよい ※道路改良・・・それぞれのルートのキャパシティを2倍にする 今回の話 • コスト関数の制約をもっと緩めても 上の関係は成り立つ • 制約をどう緩めていくか – Cが定数関数を含むとき(これまでの話) – Cがdiverseのとき – Cがinhomogeneousのとき (定義は後ほど…) Cがdiverseのとき • 証明のアプローチ ・・・証明済み ナッシュ均衡 • 「単位フローあたりのコストが等しい」は どこに現れるか ナッシュ均衡 • 「単位フローあたりのコストが等しい」は どこに現れるか ナッシュ均衡 • 「単位フローあたりのコストが等しい」は どこに現れるか 最適フロー • 「総コストが最小」はどこに現れるか 最適フロー • ナッシュフローとの比較 コスト関数に定数を含むとき • 定数＝「最善の関数」 コスト関数を定数でなくすと • 「最善」より少し悪い関数だと・・・ 単位フローあたりのコストが 等しい定数関数と比べて 無秩序の代償が小さい 無秩序の代償 • 定義式を見てみると・・・ を のいずれと取り替えて 2経路を作っても その無秩序の代償は(*)を より大きくなることはない。 何でいまさら？ • まず、もっとも単純な例 – (今まで扱ってきた例) 上の定義を少し変形して Cが定数関数を含む場合 • 条件を少し変えてみる･･･ 総流量1 総流量r は減少 Cが定数関数を含む場合 • つなげてみる を に内分する点 Cがdiverseのとき • 定数を含んでいたら 等号が成り立つことは前回示された (定数関数と「最悪の関数」の2ルート場合など) • 含まないときも上限は なのか? 復習 • まず、もっとも単純な例 – (今まで扱ってきた例) 上の定義を少し変形して 何でいまさら？ • これまで 数々の不等号が出てきたが 等号の成り立つ時については 議論してこなかった 本当はもっと小さい数でおさえられることがあるかも? 定数関数を含むとき 両辺の和をとると がナッシュフローなので、 前回の話にあった を用いて、 ナッシュ フロー 最適フロー 上リンク 0 1/2 下リンク 1 1/2 総コスト 1 3/4 ナッシュ フロー 最適フロー 上リンク 1 3/2 下リンク 1 1/2 総コスト 2 7/4
© Copyright 2024 ExpyDoc
