プリムのアルゴリズム 重み付きグラフG=（V,E)の任意の点集合　U⊂Vに対して一方の端点がUの中にあり、他方の端点がV-Uの中にあるような枝の中で最小の重みを持つものをlとすれば、枝ｌを含むような最小木が存在する。

Presentation on theme: "プリムのアルゴリズム 重み付きグラフG=（V,E)の任意の点集合　U⊂Vに対して一方の端点がUの中にあり、他方の端点がV-Uの中にあるような枝の中で最小の重みを持つものをlとすれば、枝ｌを含むような最小木が存在する。"— Presentation transcript:

1 プリムのアルゴリズム 重み付きグラフG=（V,E)の任意の点集合　U⊂Vに対して一方の端点がUの中にあり、他方の端点がV-Uの中にあるような枝の中で最小の重みを持つものをlとすれば、枝ｌを含むような最小木が存在する。

2 隣接ロボット間のコスト均等化１ A周辺のコスト平均 ( 10 + 6)/ 2 = 8 Move(A,C)=8 – 6 =2 A E A E
4 2 10 10 D 12 D 12 C C 2 2 4 4 F F B 6 B 6 8 8 10 10

3 隣接ロボット間のコスト均等化２ AからCへは2.5だけコストが C周辺のコスト平均 移動できる
( )/ 4 = 7.5 AからCへは2.5だけコストが 移動できる 7,5 – 10 = -2.5 A E A E 4 8 2 D 8 10 D 12 C 3.5 -4.5 -2.5 C 2 2 10.5 4 F B 8 1.5 F B 6 -0.5 7.5 -2.5 8 8 10

4 隣接ロボット間のコスト均等化３ 3.5－1.5 = 2 移動する A E A E 4 8 2 D 8 10 D 12 C 3.5 -4.5
-2.5 C 2 2 10.5 4 F B 8 1.5 F B 6 -0.5 7.5 -2.5 8 8 10

5 隣接ロボット間のコスト均等化3 コストはロボットとホストの距離に依存する コストの均等化に注目している
隣接ロボットにホストを渡した結果かえってコストが増加することがある 複数ステップ先のホストで距離が短くなる場合も考えられる →複数ステップ先のコストを知る必要がある

6 負荷均等化アルゴリズム ロボット間で最小木を作る ホストを各ロボットにランダムに割り当てる 割り当てられたホストを収集する
隣接ロボット間でコスト均等化する 3に戻る

7 これまでのまとめ Webページのロボットによる収集方法に関して リンクを利用したコミュニティの発見方法について

8 ロボットによるWWWページ収集 URL データベース ホストリスト WWW ロボット WWW リンクを抽出 WWW WWW ファイル
HTML ファイル システム テキストを保存

9 リンクによるランク付け Page Rank 多くの良質なページからリンクされているページはやはり良質である
0.4 +0.2 0.2 +0.2 0.4 +0.2 +0.4 ページランクの例

10 Page Rank ページ u の Page Rank R(u) v：ページuのリンク元 Nv：ページｖの持つリンク数
E(u)：ページuがジャンプ先として選択される確率に対応 Page Rankの総和を1に正規化し、ベクトルとして表現 R=c(A+E×1)R 適当なEをあたえるとRは固有値を 最大とする固有ベクトルとして求まる GoogleではEとして全ての総和が0.15となる ベクトルを用いている(87％リンクをたどり、13％ジャンプする)

11 参考文献 原田昌紀:サーチエンジンにおける検索結果のランキング，共立出版，bit Vol.32 ，2000．