图算法负载分布

Question

我遇到了以下问题，即在网络中的多台机器上分配负载。这个问题是一个面试问题。候选人应该指定哪种算法和哪种数据结构是解决这个问题的最佳算法。

我们在一个网络中有N台机器。每台机器最多可以接受5个单位的负载。请求的算法接收当前负载(范围为0-5)的机器列表、机器之间的距离矩阵以及我们希望在网络上分配的新负载M作为输入。

该算法返回能够服务于M个负载单位并且具有最小集合距离的机器的列表。集合距离是结果列表中机器之间距离的总和。

例如，如果结果列表包含三台机器A、B和C，则这些机器可以共同服务于M个负载单元(如果M=5，则A可以服务3，B可以服务1，C可以服务1)，并且距离和sum = AB + BC是可以共同服务于M个负载单元的最小路径。

你对如何处理它有什么建议吗？

Answer 1

我能想到的最简单的方法是为每台机器定义一个值，就像这台机器和它相邻的所有机器之间的反距离之和：

v_i = sum(1/dist(i，j) for j in A_i)

(抱歉，我没能在这里放入数学公式)

您可以再次反转求和，并将其称为机器的群集值(或类似的值)，但您不需要这样做。

然后根据该值对机器进行排序(如果已反转求和值，则按降序排序)。从具有最小值(最大人群)的机器开始，并尽可能多地添加负载。然后转到下一台机器，并执行相同的操作，直到分配所有您想要的负载。

Answer 2

听起来好像每台机器都能够处理相同数量的负载--即5个单元。并且您所声明的成本度量仅取决于具有非零负载的机器集合(即，向已经具有非零负载的机器添加更多负载不会增加成本)。因此，问题可以分解为：

1. 找到可以执行所有作业的机器的最小数量k <= n。对于这一步，我们可以忽略机器的各个身份以及它们是如何connected.
2. Once的。您知道所需的最小机器数量k，确定n台机器中哪k台提供的成本最低。

(1)是一个简单的Bin packing problem。虽然这个问题是NP难的，但存在优秀的启发式算法，并且几乎所有的实例都可以在实践中快速解决到最优。

也许有一些线性代数方法可以更快地解决(2) (如果有人知道，请在评论中自由编辑或建议)，但不需要过多考虑，您可以随时使用branch and bound。这可能需要n中的指数级时间，但如果n足够低，或者如果您可以获得一个合适的启发式解决方案，以限制大部分搜索空间，则应该可以。

(我确实尝试过在DP中计算f (I，j)，这是从机器1，...，j中选择i台机器的最低成本方法，但这遇到了一个问题，即当我们尝试将第j台机器添加到f(i - 1，j- 1)中时，从新机器到所有现有机器的边的总成本取决于f(i - 1，j- 1)的解决方案中的确切机器，而不仅仅是这个解决方案的成本，因此违反了最优子结构。)