我有许多服务器处理世界的矩形 block ，称它们为“区域”。当玩家从一个区域移动到另一个区域时，如果该区域不属于当前服务器，则所有玩家数据都必须发送到拥有他们刚进入的区域的服务器。
您可以想象一个区域只是具有 4 个相邻区域(连接区域)的图上的一个节点。该图会增长和缩小，因此我会定期重新平衡服务器之间的工作分配。
我想使用一种算法将区域最佳地分配给服务器，考虑以下 3 点:
- 关于节点权重的平衡工作分配，即之前在其中观察到的玩家数量；如果我除以所有节点的权重总和，我需要达到“不错”的位置，即每个服务器处理的总权重大致等于系统中的所有其他服务器。
- 区域的连续性；考虑到上述因素，节点需要彼此相邻，以尽量减少服务器之间的玩家交换。
- 并扩展 (2)，考虑从一个区域到另一个区域的交换次数。一种更喜欢将两个区域组合在同一服务器中的方式，因为它们表现出高流量的玩家在它们之间移动，而不会中断 (1)。
我考虑过实现此目的的一种方法是使用粗略的填充填充，它将分数分配给几种类型的区域分配“填充”，但这是 O(n^2) 并且可能不太适合任务。
我想到的另一种算法从流量最高的区域开始，选择具有最高交叉的节点，直到它满足最低工作阈值。这将是 O(n)，但可能会产生非常“搁浅”的空间分配，例如，交叉在工作的重新分配之间的方向上交替。
有没有其他方法可以为我的服务器分配区域，比如说，O(n)？
最佳答案
据我所知，没有一种简单快捷的方法可以创建最佳切边方式来分割节点。由于您计划仅在几台服务器上运行它，并且您知道您的图形将是什么样子，我认为您可以简单地计算一个区域的权重并优化拆分，以便每个区域具有相同的权重。
这应该会给你很好的结果。当在 100 或 1000 台服务器上运行时，这将花费更长的时间，因为您需要保持平衡的区域太多。您仍然知道图形的结构，应该利用这些信息。
如果您不知道结构，有几种算法可以尝试以集中或分散的方式计算最佳边缘切割，但它们都不是您要找的，因为它是一个 NP 复杂问题。我不得不在 Giraph 之上实现一个 - Ja-Be-Ja from KTH (Royal Institute of Technology)他们还将他们的算法与其他算法进行比较。所以你可以看到你的想法肯定会为你的问题提供更好的结果。
希望对你有帮助
关于使用图形分配邻居敏感工作的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21721708/