「隨機遊走」算法是如何工作的？

-3

下面的算法是用僞代碼寫的，爲了簡單起見，不包括實際路由在數據結構中的存儲。「隨機遊走」算法是如何工作的？

LengthFromSrc = 0; 
    LengthFromDest = 0; 
    TotalNumberHops = 0; 

    X = SRC; /*Last Node Visited from Random walk starting at SRC;*/ 
    Y = DEST; /*Last Node Visited from Random walk starting at DEST;*/ 
    /* Randomly select a route length */ 
    do { 
     Length = rand() % Max; 
     while(Length < Min); 


    while(TotalNumberHops < Length) {   

     Next = Toss Coin to Pick Random Walk from Src or from Dest; 

     if(Next == RandWalkFromSrc) { 
     Z = Randomly select an adjacent node to X; 
     TotalNumberHops = 1 + LengthFromSrc + LengthFromDest 
          + shortest-path from Z to Y; 
     if(TotalNumberHops > Length) 
      break; 
     X = Z;   /*include the node in the route*/ 
       Store X in the route data structure 
      LengthFromSrc++; 
     } 
     else { /* Next = RandWalkFromDest */ 
     Z = Randomly select an adjacent node to Y; 
     TotalNumberHops = 1 + LengthFromSrc + LengthFromDest 
          + shortest-path from Z to X; 
     if(TotalNumberHops > Length) 
      break; 
     Y = Z;    
       Store Y in the route data structure 
      LengthFromDest++; 
     } 
     }

有人會給我一個簡單的算法分析/或者通過代碼走我，因爲我想更好地理解它嗎？我的主要問題是理解第一部分：

 do { 
      Length = rand() % Max; 
      while(Length < Min); 


      while(TotalNumberHops < Length)

PS：我的來源是http://www.onion-router.net/Archives/Route/

來源

2014-04-09 Jokernight

想象一下rand（）給出的值介於0和非常大的值之間。％最大值確保該值小於最大值。然後，如果它小於Min，則重試。 – user189

我要說，代碼缺少}（雖然它是僞代碼，所以任何事情都會發生真的）

do { 
    Length = rand() % Max; 
} 
while(Length < Min);

rand()是a function is C++產生0和至少32767（雖然，出於這個目的，我認爲我們應該假設相比，可以產生的最大數目是GRE之間的整數比Max）。

% Max給出由Max分割數的剩餘的，所以Length將0和Max-1（含）之間。

然後您重複此操作直至Length >= Min，因此最後Length將在Min和Max-1（含）之間。

我們可以完全避免使用此代碼迴路：

Length = Min + rand() % (Max - Min);

或者，因爲這是僞代碼：

Length = random number in the range [Min, Max)

的代碼的其餘部分在產生兩個路徑同時從源和目的地，然後停止鏈接時（使用盡可能短的路徑）將導致散步比Length更長。

來源

2014-04-09 19:07:57 Dukeling

thx很多:)，這有助於我很多 – Jokernight

「隨機遊走」算法是如何工作的？

回答

相關問題