¼¥ÞÃæ´ÖÊó¹ð4

プリムのアルゴリズム

重み付きグラフG=（V,E)の任意の点集合
U⊂Vに対して一方の端点がUの中にあり、
他方の端点がV-Uの中にあるような枝の中
で最小の重みを持つものをlとすれば、枝ｌ
を含むような最小木が存在する。
Nishimto Libratory
隣接ロボット間のコスト均等化１
A周辺のコスト平均
( 10 + 6)/ 2 = 8
A
E
10
D
12
Move(A,C)=8 – 6 =2
A
10
4
B
10
6
2
D
C
C
2
F
B
8
10
E
4
4
6
12
2
F
8
Nishimto Libratory
隣接ロボット間のコスト均等化２
AからCへは2.5だけコストが
移動できる
C周辺のコスト平均
( 6 + 10 + 10 + 4 )/ 4 = 7.5
7,5 – 10 = -2.5
A
10 2
D
3.5
-2.5
C
2
4
1.5
B
6
-0.5
-2.5
10
E
4
A
E
8
12
-4.5
2
F
8
D
8
C
B
8
8
10.5
F
7.5
Nishimto Libratory
隣接ロボット間のコスト均等化３
3.5－1.5 = 2 移動する
A
10 2
D
3.5
-2.5
C
2
4
1.5
B
6
-0.5
-2.5
10
E
4
A
E
8
12
-4.5
2
F
8
D
8
C
B
8
8
10.5
F
7.5
Nishimto Libratory
隣接ロボット間のコスト均等化3


コストはロボットとホストの距離に依存する
コストの均等化に注目している


隣接ロボットにホストを渡した結果かえってコ
ストが増加することがある
複数ステップ先のホストで距離が短くなる場合
も考えられる
→複数ステップ先のコストを知る必要がある
Nishimto Libratory
負荷均等化アルゴリズム
1.
2.
3.
4.
5.
ロボット間で最小木を作る
ホストを各ロボットにランダムに割り当て
る
割り当てられたホストを収集する
隣接ロボット間でコスト均等化する
3に戻る
Nishimto Libratory
これまでのまとめ


Webページのロボットによる収集方法に関
して
リンクを利用したコミュニティの発見方法に
ついて
Nishimto Libratory
ロボットによるWWWページ収集
WWW
URL
ホストリストデータベース
ロボット
WWW
リンクを抽出
WWW
WWW
HTML
ファイル
システム
テキストを保存
Nishimto Libratory
リンクによるランク付け

Page Rank


多くの良質なページからリンクされているペー
ジはやはり良質である
あるページのPage Rankをページに存在する
リンクの数で割った値が、それぞれのリンク先
に加算される
+0.2
0.4
0.2
+0.2
0.4
+0.4
+0.2
ページランクの例
Nishimto Libratory
Page Rank
ページ u の Page Rank R(u)
R (v )
 cE (u )
v|v u N v
R(u )  c 
v：ページuのリンク元
Nv：ページｖの持つリンク数
E(u)：ページuがジャンプ先として選択される確率に対応
Page Rankの総和を1に正規化し、ベクトルとして表現
R=c(A+E×1)R
適当なEをあたえるとRは固有値を
最大とする固有ベクトルとして求まる
GoogleではEとして全ての総和が0.15となる
ベクトルを用いている(87％リンクをたどり、13％ジャンプする)
Nishimto Libratory
参考文献

原田昌紀:サーチエンジンにおける検索結果のランキン
グ，共立出版，bit Vol.32 ，2000．
Nishimto Libratory

Download Report