我有很多服务器处理世界上的矩形块，称它们为"区域"。当玩家从一个区域移动到另一个区域时，如果该区域不为当前服务器所有，则所有玩家数据都必须发送到拥有他们刚刚移动到的区域的服务器。
你可以想象，一个区域只是图上的一个节点，有4个邻居(连接的区域)。图表会增长和收缩，所以我会定期重新平衡服务器之间的工作分配。
我想使用一种算法将区域最优地分配到服务器，考虑以下3点：
- 关于节点权重的平衡工作分布，即之前在其中观察到的玩家数量；如果我将所有节点的权重之和除以，我需要找到一个"好"点，即每个服务器处理的总权重大致等于系统中的其他服务器
- 区域的邻接性；考虑到以上情况，节点需要相邻，以最大限度地减少服务器之间的玩家交换
- 在(2)的基础上，考虑从一个区域到另一个区域的交换数量。一种倾向于将两个区域分组在同一服务器中的方式，因为它们显示出玩家在它们之间移动的高流量，而不会中断(1)
我曾考虑过，我可以实现这一点的一种方法是使用粗糙的floodfill，它为几种类型的区域分配"填充"分配分数，但这是O(n^2)，可能不太适合任务。
我想到的另一种算法从流量最高的区域开始，选择交叉度最高的节点，直到达到最小工作阈值。这将是O(n)，但可能会产生非常"搁浅"的空间分配，例如，在工作重新分配之间，交叉点在方向上交替。
有没有其他方法可以将区域分配给我的服务器，比如O(n)？
据我所知，没有一种简单快捷的方法可以以创建最佳边切割的方式分割节点。由于您计划只在少数服务器上运行它，并且您知道图形的外观，我认为您可以简单地计算一个区域的权重并优化分割，使每个区域具有相同的权重。
这应该会给你带来非常好的结果。当在100或1000台服务器上运行时，这将需要更长的时间，因为您有太多的区域需要保持平衡。你仍然知道你的图表的结构，应该利用这些信息。
如果你不知道它的结构，有几种算法可以尝试以集中或分散的方式计算最优切边，但它们都不是你想要的，因为这是一个NP复杂问题。我不得不在Giraph之上实现一个——来自KTH(皇家理工学院)的Ja Be Ja，他们也将他们的算法与其他算法进行了比较。所以你可以看到，你的想法肯定会为你的问题提供更好的结果。
希望这能帮助