題目背景是以前用來對網頁進行排名的Page Rank算法，是早期Google的革命性發明。

背后的原理是矩陣和圖論。這個數學模型是由Google的創始人拉里·佩奇和謝爾蓋·布林發現的。

如果一個網頁被很多網頁鏈接那么它的排名就高，當然不同的網頁應該用不同的權值加以區分，

一個網頁的排名來自指向它的網頁權值之和，這就帶來一個問題，計算排名過程需要用到網頁本身排名。

這個問題可以變成一個二維矩陣相差，一開始認為所有的網頁的排名都是相同，然后迭代算出排名。

從理論上可以證明無論初始值如何選取，這種算法最后都會收斂于真實值。

還有一個實際問題，互聯網網頁是非常大的，這個矩陣需要稀疏化處理。

?

此題是簡化版，給一個矩陣，Eij = 1表示i到j有個超鏈接，假設點擊都是隨機的，求S矩陣，S的j行和i列表示從i到j的概率。

迭代計算直到收斂為止。

?

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> const double eps = 1e-10;const int N = 3000+10;double G[N][N];const double alpha = 0.85; char buf[N][N];bool ok(double *q1,double *q2,int n) {double s = 0;for(int i = 0; i < n; i++) s += fabs(q1[i]-q2[i]);return s < eps; } double q0[N]; double q1[N]; double q2[N];int main() {// freopen("in.txt","r",stdin);int n;for(int i = 0; i < N; i++) q0[i] = 1;while(~scanf("%d",&n)){double beta = (1-alpha)/n;for(int i = 0; i < n; i++){scanf("%s",buf[i]);}for(int i = 0; i < n; i++){int cnt = 0;for(int j = 0; j < n; j++)if(buf[i][j] == '1') cnt++;for(int j = 0; j < n; j++)if(buf[i][j] == '1'){G[j][i] = (cnt?alpha/cnt:0)+beta;}else G[j][i] = beta;}memcpy(q1,q0,sizeof(double)*n);double *qCur = q1, *qNxt = q2;do{for(int i = 0; i < n; i++){qNxt[i] = 0;for(int j = 0; j < n; j++){qNxt[i] += G[i][j]*qCur[j];}}std::swap(qCur,qNxt);}while(!ok(qCur,qNxt,n));for(int i = 0,sz = n-1; i < sz; i++)printf("%.2lf ",qCur[i]);printf("%.2lf\n",qCur[n-1]);}return 0; }

?

轉載于:https://www.cnblogs.com/jerryRey/p/4656442.html

總結

以上是生活随笔為你收集整理的HDU 5097 Page Rank （模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。