每個頂點的概率

Question

我有一個包含N個頂點和M個邊的圖（N在1和15之間，M在1和N^2之間）。該圖被定向和加權（具有該excact邊緣的概率）。給你一個起點和一些邊。程序然後將計算每個頂點作爲結束頂點的概率。

Examle輸入：

3 3 //頂點和

1 2 0.4 //邊緣nr.1從頂點1〜2 0.4

概率邊數數從頂點1

1 3 0.5 //邊緣NR 2〜3，用0.5

2 1 0.8 //邊緣nr.3概率...

3 //的問題數目

2 1 //開始頂點，邊數訪問

輸出：

0.8 0.2 0.0 //該頂點1頂點的概率頂點2的最後頂點爲0.8，頂點2爲0.2，頂點3爲頂點的概率爲0.0

0.1 0.4 0.5

0.33 0.12 0.55

我在我的解決方案使用的DFS，但是當邊數的訪問可高達1十億，這是太慢......我一直在尋找DP，但我不確定如何針對此特定問題實施它（如果它甚至是解決問題的正確方法）。所以我希望你們中的一些人能夠提出DFS的替代方案和/或使用/實施DP的方法。

（我知道這可能是一個有點亂，我只用C++編程一個月）

#include <iostream> 
#include <vector> 
#include <stack> 
using namespace std; 

struct bird { 
    int colour; 
    float probability; 
}; 

struct path { 
    int from; 
    int to; 
}; 

vector <vector <bird>> birdChanges; 
vector <int> layer; 
vector <double> savedAnswers; 
stack <path> nextBirds; 
int fromBird; 

//Self loop 
void selfLoop(){ 
    float totalOut = 0; 
    for (int i = 0; i < birdChanges.size(); i++) { 
     for (int j = 0; j < birdChanges[i].size(); j++) { 
      totalOut += birdChanges[i][j].probability; 
     } 
     if (totalOut < 1) { 
      bird a; 
      a.colour = i; 
      a.probability = 1 - totalOut; 
      birdChanges[i].push_back(a); 
     } 
     totalOut = 0; 
    } 
} 

double fillingUp(double momentarilyProbability, long long int numberOfBerries){ 
    int layernumber=0; 
    while (layer[numberOfBerries - (1+layernumber)] == 0) { 
     layernumber++; 
     if (numberOfBerries == layernumber) { 
      break; 
     } 
    } 
    layernumber = layer.size() - layernumber; 
    path direction; 
    int b; 
    if (layernumber != 0) { 
     b= birdChanges[nextBirds.top().from][nextBirds.top().to].colour;//Usikker 
    } 
    else { 
     b = fromBird; 
    } 
    while (layer[numberOfBerries - 1] == 0) { 
     //int a = birdChanges[nextBirds.top().from][nextBirds.top().to].colour; 
     if (layernumber != 0) { 
      momentarilyProbability *= birdChanges[nextBirds.top().from][nextBirds.top().to].probability; 
      //b = birdChanges[nextBirds.top().from][nextBirds.top().to].colour; 
     } 
     for (int i = 0; i < birdChanges[b].size(); i++) { 
      direction.from = b; 
      direction.to = i; 
      //cout << endl << "Stacking " << b << " " << birdChanges[b][i].colour; 
      nextBirds.push(direction); 
      layer[layernumber]++; 
     } 
     layernumber++; 
     b = birdChanges[nextBirds.top().from][nextBirds.top().to].colour; 
    } 
    //cout << "Returning" << endl; 
    return momentarilyProbability *= birdChanges[nextBirds.top().from][nextBirds.top().to].probability;; 
} 

//DFS 
void depthFirstSearch(int fromBird, long long int numberOfBerries) { 
    //Stack for next birds (stack) 
    path a; 
    double momentarilyProbability = 1;//Momentarily probability (float) 
    momentarilyProbability=fillingUp(1, numberOfBerries); 
    //cout << "Back " << momentarilyProbability << endl; 
    //Previous probabilities (stack) 
    while (layer[0] != 0) { 
     //cout << "Entering" << endl; 
     while (layer[numberOfBerries - 1] != 0) { 
      savedAnswers[birdChanges[nextBirds.top().from][nextBirds.top().to].colour] += momentarilyProbability; 
      //cout << "Probability for " << birdChanges[nextBirds.top().from][nextBirds.top().to].colour << " is " << momentarilyProbability << endl; 
      momentarilyProbability = momentarilyProbability/birdChanges[nextBirds.top().from][nextBirds.top().to].probability; 
      nextBirds.pop(); 
      layer[numberOfBerries - 1]--; 
      if (layer[numberOfBerries - 1] != 0) { 
       momentarilyProbability *= birdChanges[nextBirds.top().from][nextBirds.top().to].probability; 
      } 
     } 

     if (layer[0] != 0) { 
      int k = 1; 
      while (layer[layer.size() - k]==0&&k+1<=layer.size()) { 
       //cout << "start" << endl; 
       momentarilyProbability = momentarilyProbability/birdChanges[nextBirds.top().from][nextBirds.top().to].probability; 
       //cout << "Popping " << nextBirds.top().from << birdChanges[nextBirds.top().from][nextBirds.top().to].colour << endl; 
       nextBirds.pop(); 
       //cout << "k " << k << endl; 
       layer[numberOfBerries - 1 - k]--; 
       k++; 
       //cout << "end" << endl; 
      } 
     } 
     if (layer[0] != 0) { 
      //cout << 1 << endl; 
      //cout << "Filling up from " << nextBirds.top().from << birdChanges[nextBirds.top().from][nextBirds.top().to].colour << endl; 
      momentarilyProbability = fillingUp(momentarilyProbability, numberOfBerries); 
     } 
    } 
    //Printing out 
    for (int i = 1; i < savedAnswers.size(); i++) { 
     cout << savedAnswers[i] << " "; 
    } 
    cout << endl; 
} 

int main() { 
    int numberOfColours; 
    int possibleColourchanges; 
    cin >> numberOfColours >> possibleColourchanges; 
    birdChanges.resize(numberOfColours+1); 
    int from, to; 
    float probability; 
    for (int i = 0; i < possibleColourchanges; i++) { 
     cin >> from >> to >> probability; 
     bird a; 
     a.colour = to; 
     a.probability = probability; 
     birdChanges[from].push_back(a); 
    } 
    selfLoop(); 
    int numberOfQuestions; 
    cin >> numberOfQuestions; 
    long long int numberOfBerries; 
    for (int i = 0; i < numberOfQuestions; i++) { 
     cin >> fromBird >> numberOfBerries; 
     savedAnswers.assign(numberOfColours + 1, 0); 
     layer.resize(numberOfBerries, 0); 
     //DFS 
     depthFirstSearch(fromBird, numberOfBerries); 
    } 
    system("pause"); 
} 

Answer 1

如何用馬爾可夫鏈的概念做快速的解釋：

Basic algorithm: 
Input: starting configuration vector b of probabilities of 
    being in a vertex after 0 steps, 
    Matrix A that stores the probability weights, 
    in the scheme of an adjacency matrix 
    precision threshold epsilon 
Output: 
    an ending configuration b_inf of probabilities after infinite steps 
Pseudocode: 
    b_old = b 
    b_new = A*b 
    while(difference(b_old, b_new) > epsilon){ 
     b_old = b_new 
     b_new = A*b_old 
    } 
    return b_new 

在這個算法中，我們基本上計算概率矩陣的效能，並查找它們何時變得穩定。

b是概率是在後沒有在那裏採取的步驟的頂點 （所以，在你的情況下，每個條目是零，除了起始頂點，這是其中之一）

A * b是那些後一步採取

A^2 * b是採取了兩個步驟後，n步後的A^n * b。

當A^N * b爲幾乎相同的A^N-1 * B，我們認爲沒有什麼大的會發生在任何更多，這是基本相同的A ^無窮* B

可以用一些例子來模擬這種算法，比如在子圖中以非常小的概率導致的邊緣，這將導致在無限步驟之後以1的概率出現在子圖中，但是例如從現實中，它將起作用。

對於差異，歐幾里德距離應該運作良好，但基本上任何規範，你也可以去最大或曼哈頓。

請注意，我提出了一個實用的觀點，數學家會更詳細地瞭解A的哪些屬性會收斂哪些ε值。

您可能想爲矩陣使用一個好的庫，例如Eigen。

編輯：

讀Jarod42的評論，我知道你的步驟量給出。在這種情況下，只需使用A ^步驟* b即可獲得確切的解決方案。使用一個好的圖書館來快速計算效價。