C09 ネットワーク問題のモデル化と アルゴリズムの研究

Presentation on theme: "C09 ネットワーク問題のモデル化と アルゴリズムの研究"— Presentation transcript:

1 C09 ネットワーク問題のモデル化と アルゴリズムの研究
伊藤大雄(京大)　 岩間一雄(京大)　 増澤利光(阪大)　 宮崎修一(京大)　 堀山貴史(埼玉大)

2 今回紹介する成果 P2P探索の効率化 安定結婚問題の近似アルゴリズム 競合比の自動証明 孤立クリーク・密部分グラフの列挙
組合せゲーム・パズルの成果

3 Peer to Peer (P2P) 探索の効率化
例：Napster, Gnutella, BitTorrent, Winny 探索問題 目的オブジェクト（ファイル等）を持つピアの探索 最適化 探索に要するメッセージ数の最小化 探索問題の難しさ 莫大な数のピア 動的ネットワーク環境（ノードの参加・離脱） 超大規模Peer-to-Peerネットワークにおけるオブジェクト検索（情報検索） 適応的な分散型解法が必要 3

4 散布・更新コストと 探索コストの トレードオフ
ランダム探索モデル A B B： Owner ： Index ：Object A： Searcher ランダム探索 (Miura, Tagawa, Kakugawa, IEEE TPDS, 2006) ファイル所有者はインデックスをランダムに散布 探索者はランダムに探索クエリーを送付 超大規模Peer-to-Peerネットワークにおけるオブジェクト検索（情報検索）のためのインデックス情報（情報の所在場所を表すデータ）散布方式 インデックス情報をランダムに散布する手法：通信コストをかけてインデックス情報を多く配布すれば検索時には低コストでインデックス情報を発見でき，逆にインデックス情報の配布を少なくすれば検索時にはインデックス情報の発見に通信コストがかかるという，トレードオフの関係がある． 散布・更新コストと 探索コストの トレードオフ インデックス数 少 多 インデッスク散布・更新コスト 小 大 探索コスト 4

5 研究成果（１） システム全体の総通信コストの最小化 総コスト：（インデックス散布・更新コスト） ＋（探索コスト）＊（探索頻度）
総コスト：（インデックス散布・更新コスト） 　　　　　　　　　　　＋（探索コスト）＊（探索頻度） オブジェクトの探索頻度に応じてインデックス数を最適化 システム全体の総通信コストの最小化：オブジェクトの探索頻度（人気度）に応じて、散布インデックス数と散布タイミングを最適化することにより達成 5

6 研究成果（２） 自己適応型の探索アルゴリズム ファイルの探索頻度（人気度）の変化 総コストの最適化（インデックス数の自己最適化）
　　　　　ファイルの探索頻度（人気度）の変化 　 　　総コストの最適化（インデックス数の自己最適化） 最適化法は各ノードの局所的な情報（受け取った検索要求頻度など）のみに基づいて最適化を行う点が特徴 つぎに提案手法の有効性を確認するために，計算機によるシミュレーション実験を行った．ノード数を20000とし，オブジェクトのアクセス頻度を変化させたときのシステム全体の通信コストに関して，提案手法と理論的最適値を比較したものがこの図である． 人気度が連続変化する場合 人気度が離散変化する場合 6

7 安定結婚問題 入力 ：男性 N 人 出力 ：男女間の安定マッチング 女性 N 人 各人の希望リスト 例 （N=5） 男性 女性
1: a c b d e a: 2: c a e b d b: 3: b a e d c c: 4: c b d e a d: 5: c d b e a e: 男性 女性

8 安定結婚問題の応用 病院 － 研修医 NRMP (National Resident Matching Program)
病院　－　研修医 NRMP (National Resident Matching Program) CaRMS (Canadian Resident Matching Service) SPA (Scottish Pre-registration house officer Allocations) JRMP (Japanese Resident Matching Program) 学校　－　生徒 Singapore [Teo, Sethuraman, Tan 1999]

9 本特定領域研究での成果 同順位と不完全リストを許す拡張に対して最大サイズの安定マッチングを求めることはＮＰ困難であることが知られていた。この問題に対して多項式時間近似アルゴリズムを与えた。 log N ・　　　　　　　　　　 [Iwama, Miyazaki, Okamoto; SWAT 2004, IEICE Trans. 2006] 2 - c N 1 ・ 　　　　　　　 [Iwama, Miyazaki, Yamauchi; ISAAC 2005] 2 - c √ N ・ 　　　 [Iwama, Miyazaki, Yamauchi; SODA 2007]　 ・ 1.8 　　　　 [現在] 男女にできるだけ平等な安定マッチングを求める問題はNP完全であることが知られていた。この問題に対し近似アルゴリズムを与えた。[Iwama, Miyazaki, Yanagisawa; WADS 2007]

10 オンライン・アルゴリズムの性能保証 競合比の解析 競合比＝ オフラインの利得 オンラインアルゴリズムの利得 の最悪値
将来の情報なしに、いかにうまい行動をとるか 将来の情報をすべて知っている場合の最良の選択に 　　どれだけ迫れるか 競合比＝ オフラインの利得 オンラインアルゴリズムの利得 の最悪値 より良い競合比を示すには、詳細な場合分けに基づく アルゴリズム設計と競合比解析が必要

11 競合比改善のアイデアはあっても、場合分けが膨大となるため、
オンライン・アルゴリズムの性能保証 競合比改善のアイデアはあっても、場合分けが膨大となるため、 証明が困難 競合比の解析 将来の情報なしに、いかにうまい行動をとるか 将来の情報をすべて知っている場合の最良の選択に 　　どれだけ迫れるか 計算機の援用による 自動解析 競合比＝ オフラインの利得 オンラインアルゴリズムの利得 の最悪値 より良い競合比を示すには、詳細な場合分けに基づく アルゴリズム設計と競合比解析が必要

12 競合比の自動解析 ２ビンの オンライン ナップザック 問題 → 1.301 （上下限 一致） アイデア （無限を有限におさえる）
競合比　上界 下界 アイデア （無限を有限におさえる） アルゴリズムの状態の遷移を自動生成、 各状態で競合比解析 アイテムを大きさをクラス分けして扱い、入力を網羅 クラスに基づくと、ビンの状態は有限 SS + LL ≦１ or ＞１ 等の場合分けを自動生成 → （上下限 一致） （人手による解析）

13 状態遷移図 276状態 状態遷移をすべて列挙 2. 各状態で 競合比 ≦ を証明

14 孤立クリーク・密部分グラフの列挙 < ck 本の枝 クリーク列挙：ウェブ探索などで近年注目されている。
しかしクリークの問題は難しい・・・ 最大クリーク発見問題⇒近似比: Ω (n1-ε ) [Hastad 99] 極大クリーク列挙⇒指数(Θ(3n/3))個ありうる[Moon, et al. 65] そこで我々は・・・孤立クリークを導入 全c-孤立クリークをO(c422cm)時間で列挙！ さらにc=O(1)⇔線形時間、c=O(logn)⇔多項式時間を証明。 k 節点 < ck 本の枝

15 孤立クリーク・密部分グラフの列挙 擬クリークPC(α,β): 誘導部分グラフの平均次数≧αかつ最小次数≧β、を定義し、　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1-孤立擬クリーク　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(ε>0)に対し、「ε=0 ⇔ 多項式時間列挙可能」を証明。 1-孤立２部クリークに対し、 それが指数個存在し得ること 部の大きさの比が定数のときの多項式時間総列挙アルゴリズム 　 を示した。

16 組合せゲーム・パズルの成果 半順序集合ゲーム（ニム、チョンプ等を含む古典的ゲーム）を拡張し重み付き半順序集合ゲームを提案。 一般化三並べ
(0,1)重み：（重み無し）半順序ゲームに多項式時間帰着。 実数重み：半順序が全順序であるものに対する多項式時間必勝手順。 一般化三並べ スネーキーの置き石１の必勝法　　　　　　　　　　⇒スネーキーのハンディキャップ数は0か1。

17 今回紹介した成果 P2P探索の効率化 安定結婚問題の近似アルゴリズム 競合比の自動証明 孤立クリーク・密部分グラフの列挙
組合せゲーム・パズルの成果