使用熱方程進行負載平衡

我不認爲這對mathoverflow來說足夠滿足，所以我想我會在這裏嘗試。它的編程問題雖然如此，所以它的主題。我有一個圖（如在數學的一個），其中我有一些頂點，A，B，C ..每個都有一個負載「值」，這些是通過一些任意的拓撲連接（有至少一棵生成樹）。問題的目標是在每個頂點之間傳遞負載，最好使用可能的最小流量。使用熱方程進行負載平衡

我想知道每個邊緣的傳輸值。

我想到的問題的解決方案是將其視爲傳熱問題，並以迭代方式轉移負載，或以某種方式求解熱方程，計算沿每個邊消散的負載量。因此，直到網絡達到穩定狀態的傳熱量應該產生結果。

雖然我認爲這會起作用，但它似乎是愚蠢的解決方案。我想知道是否有參考或樣本問題，有人可以指向我 - 我不確定要搜索的關鍵字。

我看不出如何將問題耦合爲單純形問題或網絡流問題 - 每個邊都具有無限容量，每個節點也是如此。有兩個同時最小化問題需要解決，所以單工似乎不適用？

來源

2011-07-25 OptimiseCoder

這聽起來像[拉普拉斯平滑]（http://en.wikipedia.org/wiki/Laplacian_smoothing）。 – lhf

您尚未明確定義您的問題; 「在每個頂點之間傳遞負載，最好使用可能的最小流量」可能意味着許多事情（可能根本沒有傳輸，這肯定是最小流量）。對傳熱的暗示表明你想要從具有較高值的頂點向具有較低值的頂點移動「負載」。也許你的目標是實現所有頂點的水平加載所需的最小轉移量。但是我不認爲迄今爲止描述的數據支持連續模型（傳熱）。 – hardmath

如果你有一棵生成樹，那麼就有一個O（n）解決方案。

計算平均值。（最後，每個節點都會有這個值。）然後迭代葉子：計算葉子所需的值的變化（平均值），將該變化添加到葉子，將其分配（作爲流）到邊緣將葉子連接到樹，並從另一個節點中減去它。從樹上移除葉子和邊緣（不是從當然的圖表）;如果樹中只剩下一個剩餘的邊，另一個節點可能會成爲一個新的葉。

當你到達最後一個節點，如果你做到了將結束與平均值的算術正確，就像所有其他節點。

來源

2011-07-25 18:37:28 Beta

使用熱方程進行負載平衡

回答

相關問題