有约束的比例分配算法

Question

有约束的比例分配算法

4

我有一个问题，归结为以下问题。考虑一组n个箱子，每个箱子都有一个权重（可能是“加权值” - 我不是在谈论箱子的物理重量），最小（编辑：阈值）内容和最大内容。目标是将一定数量x分配到所有箱子中，使每个箱子中的数量与该箱子的权重成比例，但仍在该箱子的约束条件内（即不低于最小值（编辑：至少阈值），不超过最大值）。任何低于最小值（编辑：阈值）或高于最大值的内容都应重新分配到其他箱子中。

天真的实现会在第一轮中按比例分配x，不超过任何一个箱子的最大值；将任何多余的内容带到下一轮并重复直到分配x；然后它将检查所有箱子以查看是否满足最小值；那些不满足最小值的箱子将被清空，并将它们的内容总和重新分配到所有箱子中，依此类推，直到满足所有约束条件并分配x。

然而，这个算法的运行时间是二次的，我已经看到了一些真实数据集，它们甚至没有接近最坏情况，但仍然耗尽了我的计算预算。因此，我的问题是 - 有人认识这个问题作为已知的优化问题吗？我在文献的海洋中迷失了方向，我认为我只是没有用正确的术语搜索它。当然，如果有直接提示我如何更有效地解决这个问题，我也会很高兴（实际上更高兴：））。

编辑：我刚刚发现我在上面使用了错误的术语 - 尽管示例是正确的。在我的尝试中解决此问题时，我使用了错误的术语，导致（至少部分）混淆，使我提出了这个问题。无论如何，在上面说“最小值”的地方，应该读作“阈值”。因此，当箱子的阈值为5时，只有当大于5时才会分配到该箱子；如果不是，则应按比例将金额分配给其他箱子。

我已经修改了上面的文本以指示这一点，但它并没有帮助问题的可读性 - 不确定这里的编辑指南对此类问题的要求是什么，因为直接更改为正确版本将使评论没有任何意义。

- Roel

1

是否只有一种解决方案是可以接受的？如果理想分配不可能实现，那么如何确定一个解决方案在替代方案中是最佳的函数是什么？ - trincot

据我所知，只有一种可能的解决方案，使得每个箱子中所有值的总和等于x，每个箱子的值都在约束范围内，并且比例是正确的（除了数值不精确的情况）。如果x不适合（当每个箱子的最大值达到时），只要我知道这一点，还剩下多少就足够了。或者你是说接受权重的近似值？在那种情况下，我不挑剔。我猜想人们会想要最小化均方根误差？比如，将每个箱子的值除以权重并最小化残差？这是否有意义？ - Roel

我不知道，这是你的问题吗？问题是要最小化RMSE吗？ - trincot

是的，这是可能的 - 我会逐一审查所有回应来了解其中的细节，这似乎是一个重要的区别需要弄清楚。 - Roel

@Roel：将 minimum 更改为 threshold 明显会有不同的问题。我建议您将其作为一个不同的问题提出；没有额外的费用 :) - rici

显示剩余3条评论

2个回答

2

首先解决我之前的误解，即允许的答案必须填满每个箱子到其最小数量。

首先检查您的数量x是否大于所有箱子的最大容量之和，或小于最小容量之和。如果是其中任何一种情况，则当前选择的箱子下没有好的解决方案。

对于每个箱子，计算标准化的最小和最大数量-当前最小和最大数量除以该箱子的重量。

考虑使用（目前未知的）魔法数量q来分配到箱子中。如果标准化的最小值> q，则将箱子填充到其最小值。如果标准化的最大值< q，则将箱子填充到其最大值。否则，用重量*q填充箱子。对于非常低的q值，我们得到绝对最小总内容。对于非常高的q值，我们得到绝对最大总内容。其中一个中间值的q应与您所需的总内容相匹配。在这个值下，中间箱子的误差为零，最小和最大箱子尽可能接近它们的理想填充，而约束条件将让它们靠近。

总分配量作为q的函数是单调递增的分段线性函数，在标准化的最小值和最大值处改变斜率。如果你计算并按时间O(n log n)排序这些断点，你可以进行二进制搜索，以找到提供略高于和略低于目标数量的断点，每个猜测的总成本为n，需要log n次猜测。然后使用线性插值来精确找到q的正确值。

或者，如果你将标准化的最大值和最小值排序到一个数组中，我认为你可以跟踪随着q的增加而分配量如何增加。从最低最小值开始，分配的总量是所有最小值的总和。这里的梯度是最低最小值箱的权重。当你通过其他最小值时，梯度增加其权重。当你开始通过最大值时，梯度减少其权重。沿着这个数组扫描，你可以找到分配总量达到所需数量的位置，主要成本是对汇集的标准化最大值和最小值进行排序的成本。

现在我们有了一种填充箱子的算法，当每个箱子必须至少达到其最小数量时。这个约束条件是不正确的，实际上我们可以识别出当这个条件不成立时——当最小数量的总和超过目标数量时，或者当某个箱子最终分配到的量超过了其公平份额。

当算法出现错误时，我们可以使用与原始朴素解决方案相同的策略-如果存在最小值太大的箱子，则从考虑中删除一些箱子，并在没有足够空间容纳所有物品时将一些箱子放回（我不知道这是否是正确答案，但我认为至少可以接受，因为它在朴素解决方案中使用）。我们从标准化最小数量最大的箱子开始删除。同样，因为我们可以对箱子进行二分查找，所以我们只需要进行log n次遍历-我假设我们想要尽可能多地使用箱子。

这给我们带来了一个围绕我们原始解决方案的log n次遍历的外部循环。如果原始解决方案需要n log n的时间，并且我们每次都从头开始重复，那么成本就是n (log n)^2。如果我们使用的是仅由于初始排序而具有log n因子的替代方法，则我们只需要在开始时执行一次初始排序，每个内部遍历成本仅为O(log n)。这使我们的总成本为O(n log n)。

- mcdowella

我觉得这个方法应该有效，谢谢你。在我的尝试中，我按照“范围”（最大值减最小值）除以权重进行排序，但是没有达到预期的效果。我对你的答案还没有直观的理解，所以作为一个元问题和“调试”我的算法开发过程，你是用一种结构化的方法来得出这个算法的，还是它突然就冒出来了？（我总是试图追溯我想出的这种数值算法的推理过程，合乎逻辑的过程给了我更多信心，所以我想请教如何在下次自己得出类似结果）。 - Roel

好的，我花了非常长的时间才找到我的Excel模拟为什么不对——这个算法只在分配最小值时有效，而我所寻找的（根据我在OP中的编辑），是一个阈值而不是最小值。据我所知，依靠神秘值q在这种情况下行不通，因为你不能仅从q及其权重就计算出每个箱子的比例，因为q现在取决于是否已经达到门槛——你无法从一开始就知道这一点。或者你的第二种方法可以行得通吗？ - Roel

如果阈值的总和太大，您可以简单地不填充箱子。 - tucuxi

我已经在原始答案外面添加了一个循环，魔术值在这里是要使用的箱子数量，假设我们想要先丢弃那些标准化最小量最大的箱子。 - mcdowella

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

这个问题本质上是选举制度中的分配问题，因此它已经被数学家和政治科学家广泛研究（不一定具有相同的标准）。

分配问题包括将议会席位分配给基于选举结果的政党或名单（例如西班牙或荷兰），以及将议会席位分配给基于人口（例如美国各州）、投票人口甚至前一次选举的总票数的地方选区。政治要求导致了对基本算法的各种调整，包括最小值和最大值（就像你的问题一样）和非线性。

除非极少数情况下，否则不可能实现完美的比例，使每个实体的分配与该实体的权重（选票/人口/等）完全成比例。分配算法通常被期望最小化不成比例性，但如何衡量不成比例性尚无共识，因此对于相同的权重，通常会有不同（但类似）的分配，每个分配都最小化不同的指标。

在很大程度上，我们可以将分配算法分为两大类：最大公约数（或最大平均数）和最大余数。

最大公约数方法

最大公约数方法试图找到某个“q”，使实体“i”的分配计算为：

A<sub>i</sub> = ⌊W<sub>i</sub>/q + α⌋

其中，W_i是实体i的权重，α是范围在[0，1)内的某个数字。几乎总会有这样一个q，除非两个或更多实体并列，这种情况下可能需要任意选择一些并列实体的子集来奖励额外分配。常见的α值为0（“D'Hondt方法”）和0.5（“Sainte-Laguë方法”），这两种方法分别以开发相应算法并证明其最优性的数学家命名（显然使用略有不同的度量标准）。D'Hondt方法倾向于稍微偏向具有较大权重的实体，但在除斯堪的纳维亚以外的比例代表制系统中最常用的方法是该方法，而斯堪的纳维亚使用更类似于Sainte-Laguë的方法，这些方法对于权重更加中立。（α大于0.5的值倾向于更小的权重。）（下面提供了找到商q的算法。）

目前在美国各州之间分配国会席位的方法略有不同：亨廷顿-希尔方法（以数学家和统计学家命名）。在此方法中，与其尝试线性般地舍入分配（如在Sainte-Laguë中），不如根据几何平均数舍入分配。

最大余额法

最大余额法通常被认为更易于理解，执行该方法的算法稍微简单，但结果的稳定性存在一些问题。在这里，我们首先计算一个q值，该值已知会导致使用相同公式（将α设置为0）分配正确或少一个实体。然后有必要为某些实体的子集分配高达一个以上的分配；这是通过对由floor运算符丢弃的余数进行排序，并将额外的分配授予具有最大余数的实体来完成的（因此得名“最大余额”）。

有多种方式可以计算 q 以提供最大余额方法的起始点，并且最终结果取决于 q 的初始选择（有些难以预测）。正是这种不可预测性导致了对最大余额方法的批评：曾经在美国用于将国会席位分配给各州，但由于“阿拉巴马悖论”的结果而更改了算法；即一种特定人口分布，其中增加一个额外的国会席位将导致阿拉巴马州的分配变小。

尽管如此，最大余额机制仍在一些司法管辖区中使用，并且经常基于（可以认为是错误的）假设而提出，即理解数学比偶发的悖论结果更重要。计算 q 的两个常见公式是（这里，N是要分配的数量）：

哈雷公式：q = ΣW / N
德鲁普公式：q = ⌊1 + (ΣW / (N + 1))⌋

其中，德鲁普公式更为常见。

算法

采用最大余数法分配的O(N)算法非常简单。首先计算出q（如上所述），然后通过将每个权重除以q并取整来进行初始分配；这些初始分配值进行求和并从期望的总分配中减去。差值k必须是0到N之间的整数；随后找到最大的k个余数，并将这些实体的分配增加。可以使用快速选择在O(N)时间内完成此操作，尽管很常见看到代码执行完整的O(N log N)排序。

最简单的最大约数算法公式为O(ΣA log N)，其中N是实体的数量（如上所述），而ΣA是总分配量。对于最简单的情况——D'Hondt分配——我们从将每个实体分配为0开始，然后将N个实体放入按比较计算比率W_i/(A_i+1)排序的最大堆中。然后我们迭代地增加堆顶上的实体分配量，这会改变其比较值，从而强制进行下堆操作，直到分配总额达到所期望的总数。由于堆始终具有大小N，因此每个ΣA下堆操作需要时间log(N)。然而，我们可以通过构建商的初始估计值和基础分配（就像使用最大余数法一样），然后从该起点执行算法，从而显着提高此运行时间。如果初始猜测与正确的分配量相差不超过N，则总时间为O(N log N)。（例如，这种修改在巴西选举法律中得到描述。）

Sainte-Laguë机制将比较计算替换为W_i/(2×A_i+1)，这有效地导致比较在分配范围[A_i, A_i+1)的中间点处进行。类似地，Huntington-Hill几何平均算法使用基于W_i/√(A_i×(A_i+1))的比较。这些修改都不影响渐近复杂度。

合并最小和最大分配

将这些算法调整为最小和最大分配可以通过多种方式完成，具体取决于希望优化的比例度量标准。我不知道有关最大值的真实世界示例，但当使用最小余数方法在子国家实体之间分配席位时，最小值非常常见，因为即使实体非常小，一般认为没有代表是不民主的。一个非常普遍的规则是将最小分配分离出来，并仅对剩余要分配的内容运行上述算法之一。（这就是美国和秘鲁在将席位分配给州/部门时使用的机制。）结果，当然会不成比例地惠及较小的子国家实体，因为对于只有两个席位的实体来说，“免费”的额外席位的价值比对于有36个席位的实体来说更大。

使用最大公约数方法，一个简单而明显更为比例的解决方案是预先分配最小值，然后从那个起点继续使用标准算法。如果一个实体达到其最大值，它将被从堆中移除而不是向下堆叠，从而使其无法用于未来的分配。

对于最大余数，可以做类似的事情。例如，可以根据公式执行初始分配，然后调整以符合最大值和最小值。如果调整减少了一个或多个达到其最大值的分配，则次要分配可能会超过实体数量，但这并不会使算法变得更加复杂（每个分配将增加k或k+1而不是0或1），除了需要注意避免次要分配超过最大值。另一方面，如果许多分配增加以符合最小值，那么可能会发现次要“分配”成为使用最小余数而不是最大余数的负分配（同样要注意不降低任何实体的最小值）。