b775. 10028. Fast Page Rank
標籤 :
通過比率 : 2人/6人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-01-13 14:55

內容

每一個網站都有超連結 (hyperlink) 到另一個網站,該網站會將自己的 Page Rank Value 均勻分配給連出去的網站。當一個網站被連接的次數越多,則網站的 Page Rank 越高。

N 個網站之間的關係轉為 Graph,計算轉換成馬可夫過程。但馬可夫過程容易造成 Page Rank 失算,因為有些點並沒有出度 (連接到別的網站),數值就會隨著迭代集中到這個孤島上 (或者說蜘蛛網),造成其他點的 Page Rank 皆為 0。為了防止這一點,給予 Page Rank 的總和 N。轉移只有 α 的信任度,剩餘的 1α 將隨機選擇全局的網站進行轉移。

例如

1: 2, 3, 4
2: 3, 4
3: 4
4: 2

Sn×n=[00001/30011/31/2001/31/210]

根據 G=αS+(1α)1nU,;α=0.85 得到

β=(1α)/4=0.375Gn×n=[0×0.85+ββββ1/3×0.85+βββ1×0.85+β1/3×0.85+β1/2×0.85+βββ1/3×0.85+β1/2×0.85+β1×0.85+ββ]

假設 Page Rank Vector qcurqnext 分別表示當前求得的結果和下一次的迭代數值,則

qnext=Gqcur

不斷地迭代直到 |qnextqcur|<ε,其中 ε=1010

輸入說明

有多組測資,每組測資第一行會有一個整數 N 表示有多少個網站,接下來會有一個 N×N 的 0/1 矩陣,其中 Ei,j 表示第 i 個網站連到第 j 個網站。

  • 1N3000
輸出說明

每組測資輸出一行,輸出每一個網站的 Page Rank Value,用空白隔開並保留兩位小數。

範例輸入 #1
4
0111
0011
0001
0100
範例輸出 #1
0.15 1.49 0.83 1.53 
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
提示 :
標籤:
出處:
NTU批改娘計算機程式設計課程 [管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」