分配算法 [英] Assignment Algorithm
问题描述
我需要分配N个实体（每个都有可能的父项和可能的子项）到M个计算节点，同时满足以下优化条件：
I need to assign N entities (each with possible parents and possible children) to M computation nodes while satisfying the following optimization conditions:
- 实体的孩子想要被分配到相同的计算节点（以最大化兄弟姐妹之间的数据局部性）
- 实体的分布应当尽可能均匀（即，节点）。
我正在寻找关于启发式方法的一些建议来解决这个问题。
I'm looking for some suggestions on heuristic methods to solve this problem.
我阅读了 http://en.wikipedia.org/wiki/Assignment ％5Fproblem 。
感谢。
推荐答案
不知道1是否是一个严格的要求。如果是这样，作为第一步，您应该将实体分组到已连接组件。如果没有，你应该指定1和2之间的权衡，例如。作为成本函数。
I'm not sure whether 1 is a hard requirement. If so, as a first step, you should group your entities into connected components. If not, you should specify what the tradeoff between 1 and 2 is, e.g. as a cost function.
将组件放置在计算节点上是 binpacking问题，如果你将每个节点限制为N / M实体。一个很好的近似是以下算法：
Placing the components on computation nodes is the binpacking problem, if you limit each node to N/M entities. A good approximation is the following algorithm:
- 按照实体数量按递减顺序对组件进行排序
- 将它们放置到节点上，只要每个节点仍然具有可用空间即可。
- 在使用2时，可能有未放置的组件。将它们放在到目前为止负载最小的节点上。
这篇关于分配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
