使用圖分配鄰居敏感工作的算法

Question

我有一些服務器處理世界的矩形塊，稱他們爲「地區」。當一個玩家從一個區域移動到另一個區域時，如果該區域不屬於當前服務器，則所有玩家數據必須發送到擁有他們剛進入的區域的服務器。

你可以想象一個區域只是一個包含4個鄰居（連接區域）的圖上的一個節點。圖形增長並縮小，因此我定期重新平衡服務器之間的工作分配。

我想使用算法來優化區域分配給服務器，以下列3點考慮：

1. 平衡的工作分配與問候到節點的權重，即數量之前觀察過的球員;如果我劃分所有節點的權重總和，那麼我需要點擊「好的」點，每個服務器處理的總權重與系統中的其他所有服務器大致相同。
2. 區域的連續性;考慮到上述情況，節點需要彼此相鄰以最小化在服務器之間交換播放器。
3. 並且在（2）上延伸，考慮從一個區域到另一個區域的交換次數。一種更喜歡兩個區域在同一個服務器中組合在一起的方式，因爲它們表現出在它們之間移動的玩家的高流量，而不會破壞（1）。

我已經考慮過，我可以實現這一目標的一種方法是使用原始填充，將分數賦予幾種類型的區域分配「填充」，但這是O（n^2），可能不是非常適合這項任務。

我想到的另一種算法是從最高流量區域開始，選擇交叉點最高的節點，直到滿足最低工作閾值。例如，這將是O（n），但可能會產生非常「擱淺」的空間分配，例如，交叉在工作重新分配之間交替。

是否有另一種方法可以將區域分配給我的服務器，比如O（n）？

Answer 1

據我所知，沒有簡單快捷的方式將節點拆分成可以創建最佳邊緣切割的方式。由於您計劃只在少數服務器上運行它，並且您知道圖表的樣子，我認爲您可以簡單地計算區域的權重並優化分割，以便每個區域具有相同的權重。

這應該會給你很好的結果。當運行在100或1000臺服務器上時，由於您需要保持平衡的區域太多，因此需要更長的時間。你仍然知道你的圖的結構，並應該利用這些信息。

如果你不知道結構，有幾種算法可以嘗試以集中式或分散式方式計算最佳邊緣切割，但它們都不是你想要的，因爲它是一個NP複雜問題。我必須在Giraph之上實現一個 - Ja-Be-Ja from KTH (Royal Institute of Technology)，他們還將它們的算法與其他算法進行比較。所以你可以看到你的想法肯定會爲你的問題提供更好的結果。

希望這可以幫助