如何平衡圖形中的週期？

enter image description here

第二圖像（用括號權重）是「平衡」，即，每個節點發送重量適量到其他節點，以及端節點具有相同的權重作爲起始節點。

現在讓我們說我的圖是空的（邊緣知道多少％權重發送給其他節點，但圖中沒有權重）。如果我在起始節點上加上20的權重，我該如何做到這一點，以便像第二個圖像中顯示的那樣平衡最終圖形？在我看來，我應該遞歸地更新圖表，直到每個節點的權重變得不變，但這是否是最好的方式呢？

編輯：這是與我正在研究的項目有關的這個問題的Java代碼，如果它可以幫助某人。我明白這個代碼中沒有使用某些函數的信息，但是你應該看到大局。

注：許多變量名是法國人，這裏是一個快速翻譯其中的一些：
nb_stations：節點的量
m_listeStations：所有節點
ID_ARRIVEE的列表：開始節點的ID（」開始在」圖表）
送貨線路：圖
POIDS：重量
弧：邊緣

// build the distribution matrix 
public float[] buildDistribution() { 
    int nb_stations = m_listeStations.size(); 
    float[] distribution = new float[nb_stations]; 
    Arrays.fill(distribution, 0); 
    distribution[findIndexStation(findStation(Reseau.ID_ARRIVEE))] = findStation(Reseau.ID_ARRIVEE).getPoids(); 
    return distribution; 
} 

// build the transition matrix 
public float[][] buildTransition() { 
    int nb_stations = m_listeStations.size(); 
    float[][] transition = new float[nb_stations][nb_stations]; 
    for (float[] ligne : transition) { 
     Arrays.fill(ligne, 0); 
    } 

    for (int i = 0; i < nb_stations; ++i) { 
     List<Arc> arcsOut = m_listeStations.get(i).getArcsOut(); 
     for (int j = 0; j < arcsOut.size(); ++j) { 
      transition[i][findIndexStation(arcsOut.get(j).getCible())] = arcsOut.get(j).getPoidsRelatif(); 
     } 
    } 

    int indexArrivee = findIndexStation(findStation(Reseau.ID_ARRIVEE)); 
    transition[indexArrivee][indexArrivee] = 1; // arrivée continuelle 

    return transition; 
} 

// this function does one iteration of distribution*transition to converge toward the real weights 
public float[] convergeDistribution(float[] in_distribution, float[][] in_transition) { 
    int nb_stations = m_listeStations.size(); 
    float[] converge = new float[nb_stations]; 
    Arrays.fill(converge, 0); 
    for (int i = 0; i < nb_stations; ++i) { 
     for (int j = 0; j < nb_stations; ++j) { 
      converge[i] += in_distribution[j] * in_transition[j][i]; 
     } 
    } 
    return converge; 
}

來源

2014-02-12 trakmack

你的圖表被稱爲一個Markov chain。你在找什麼是馬爾可夫鏈的stationary distribution。

如果P是您的轉換矩陣，則平穩分佈x是方程x * P = x的解。

收斂速度討論here。

一旦你擁有固定分佈，你可以很容易地解決你描述的問題。只需將權重固定在一個節點/邊上，然後基於平穩分佈和轉換矩陣，所有其他節點/邊權重與其成比例。

來源

2014-02-12 17:37:59

如何平衡圖形中的週期？

回答

相關問題