No.8018 簡易版ページランク

問題提出提出一覧質問統計解説

問題一覧 > 教育的問題

No.8018 簡易版ページランク

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が

10^{- 1}

以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 25
作問者 :

horiesiniti / テスター :

37zigen

2 ProblemId : 1191 / 自分の提出

問題文最終更新日: 2017-03-18 01:28:44

問題文

最近廃止されたGoogleのページランクですが、未だに色々な分野に使われている重要技術です。今回はページランクの簡易版を実装しましょう。
（必須ではありませんが、ページランクについて調べてから回答すると知見が深まる知見が深まるかもしれません。
Wikipediaなどにページランクの解説があリます。Wikipedia: ページランク）

今回はWebページ上での人々の移動を簡易シミュレーションするとしましょう。

Googleのページランクにあやかり、どのページも最初10.0人閲覧している状態から計算を始めます。ページは0～ｎ-1までの番号をつけます。ページを点として片方向リンクを矢印としてグラフとしてみます。ある点にいるのが0.274481人のような計算を許します。

ターン制で計算し、一回の計算ごとに、人々は今とどまっているページからそのページに一つ以上あるリンクのどれかを選んでリンク先へ移動します。簡易計算なので点にはとどまる人も中断する人もおらず必ず一回の計算毎に全員が次のリンク先へ移動するとします。 100回計算した後の各ページの人数を計算してください。データはページとそのページにある片方向リンクをたどって違うページへ向かう人の割合が渡されます。割合に基づいて人々の移動をシミュレートしてください。

（ページ下でサンプルインプットを図入りで解説しているので分かりにくければそれを参照すること）

入力

 $n$ 
 $m$ 
 $a_{1}$   $b_{1}$   $c_{1}$ 
 $\dots$ 
 $a_{m}$   $b_{m}$   $c_{m}$

$1 < n \leq 1000$
$1 < m \leq 10000$
$0 \leq a_{i} < n$
$0 \leq b_{i} < n$
$a_{i} \neq b_{i}$
$0 < c_{i} \leq 10$

データセットは
一行目にページの数

n

ページは

0 ～ n - 1

までの番号が振られていると仮定してよい
2行目にページを結ぶ片方向リンクの数

m

続く

m

行に片方向リンクと、そのリンクをクリックする人の割合が整数で表示されます

a_{i}

b_{i}

c_{i}

ページ

a i

からページ

b i

へ向かう人の割合は

c i

ページ1からページ2,5,7へ向かう片方向リンクがありそれぞれの割合が3 2 4(各行でのciの値)の場合の計算例を示します

データ的にはページ１からでるリンクデータを抜き出した時下記のようであれば。

1 2 3
1 5 2
1 7 4
というデータだとします。

そのターンのページ1の人数をｎ1として

ページ1からページ2へ向かう人数は
$\frac{n 1 * 3.0}{3 + 2 + 4}$
ページ1からページ5へ向かう人数は
$\frac{n 1 * 2.0}{3 + 2 + 4}$
ページ1からページ7へ向かう人数は
$\frac{n 1 * 4.0}{3 + 2 + 4}$
と計算しページ1にとどまる人はいません。
ページ1にはページ1にリンクしているページがあればそこから同様の計算で人が来ます。このように全ての人が全ての点で一つ先のリンク先へ移動するのを1回の計算とします。 100回計算が行われた後、各点にいる人数をページ0～ページn-1まで一行ずつ実数 $U i$ で表示してください。 0.1までの誤差は許容されます。どのページも必ず一つはリンク先を持っていると仮定してよい。どこからもリンクされていないページの人数は0と算出します。計算はdouble型で行うこと。以上長い説明でしたが、それでは挑戦してください。

出力

$U_{0}$
$\dots$
$U_{n - 1}$
最後に改行してください。

サンプル

サンプル1

入力

出力

図から解説する。例えば1回目の計算で

ページa1からページa0へ行く人数は $\frac{10 人 * 3}{1 + 3}$

ページa1からページa2へ行く人数は $\frac{10 人 * 1}{1 + 3}$

となる。

ページa1へくる人数は

ページa3から $\frac{10 人 * 4}{4} = 10 人$

ページa0から $\frac{10 人 * 3}{3 + 2} = 6 人$

よってページa１の一回目の計算が終わった時点での人数は合計16人である。実際は、ページはaなどはついておらず整数値の番号（0～ｎ-1）が与えられる。 a等は図の分かりやすさのためだけにつけた。

参考として一回目の計算が終わった時の各点の人数は
ページ0　13.333333
ページ1　16.000000
ページ2 6.500000
ページ3 9.166667
ページ4 5.000000
となる、これを参考にするとよい。

サンプル2

入力

出力

ページ0はどこからもリンクされていない。 1回計算しただけでページ0の人数は0となる。ページにつけるaは省略した。興味があれば99回目と100回目で計算結果を比較してみるとよい。計算回数一回の差で各ページの評価が大きく変わることが分かる。世の中によくある大規模行列の複数回適用でページランクが収束するという話はいうほどシンプルに考えてはいけないことがわかる。

サンプル3

入力

出力

ネットが二つに分かれている場合もある。片方は中央集権的でありページ0とページ1が総取りである。ページ2やページ7の人数は計算後ほぼ0になり価値がないと判断されるが、2や7は高い価値はつけられないが他からリンクされているのでそれなりの価値はあるはずである。世の中は単純ではないことが判明し、簡易計算では問題がある事がわかる。実務ではなにをどこまでどのように計算すべきか頭を悩ますことになる。更にここで、どこへもリンクしてないページへ人々が吹きたまった場合、本物のページランクではどう処理しているかを調べるとなおよい。それと現場での計算はlogを使わないと計算精度があやしくなることも追記しておく。しかし今回の問題は簡易的に体験してみることを目的としているので計算は指定通りに行うこと。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder