我遇到了以下在网络中的多台机器上分配负载的问题。问题是一个面试问题。候选人应该指定哪种算法和哪些数据结构最适合这个问题。
我们在一个网络中有 N 台机器。每台机器最多可以接受 5 个单位的负载。请求的算法接收机器列表及其当前负载（范围为 0-5）、机器之间的距离矩阵以及我们要在网络上分配的新负载 M 作为输入。
该算法返回可以为 M 个负载单位提供服务并具有最小集体距离的机器列表。集体距离是结果列表中机器之间距离的总和。
例如，如果结果列表包含三台机器 A、B 和 C，这些机器可以共同服务 M 个负载单位（如果 M=5，A 可以服务 3，B 可以服务 1，C 可以服务 1）和距离总和SUM = AB + BC 是可以共同为 M 个负载提供服务的最小路径。
你对如何处理它有什么建议吗？
听起来每台机器都能够处理相同数量的负载——即 5 个单位。并且您声明的成本度量仅取决于具有非零负载的机器集（即向已经具有非零负载的机器添加更多负载不会增加成本）。因此问题可以分解为：
(1) 是一个简单的Bin 装箱问题。尽管这个问题是 NP 难的，但存在优秀的启发式算法，并且几乎所有实例都可以在实践中快速解决到最优。
可能有线性代数方法可以更快地解决（2）（如果有人知道，请随时在评论中编辑或提出建议），但无需考虑太多，您始终可以使用branch and bound。这可能需要 n 的指数时间，但如果 n 足够低，或者如果您可以获得一个体面的启发式解决方案来限制大部分搜索空间，则应该没问题。
（我确实尝试过考虑一个 DP，我们在其中计算 f(i, j)，这是从机器 1，...，j 中选择 i 机器的最低成本方法，但是当我们尝试添加jth 机器到 f(i - 1, j - 1)，从新机器到所有现有机器的边的总成本取决于 f(i - 1, j - 1) 的解决方案中的机器，以及不仅仅是这个解决方案的成本，因此违反了最优子结构。）
我能想到的最简单的方法是为每台机器定义一个值，例如这台机器与其所有相邻机器之间的倒置距离的总和：
v_i = sum(1/dist(i, j) for j in A_i)
(抱歉，我无法将数学公式放在这里）
您可以再次反转总和，并将其称为机器的人群值（或类似名称），但您不需要。
然后根据该值对机器进行排序（如果您已反转总和值，则降序排列）。从具有最小值（最大人群）的机器开始，并尽可能多地添加负载。然后去下一台机器，做同样的事情，直到你分配了你想要的所有负载。