0

在从事个人项目时，我遇到了一个问题，我将在这里尝试概括。

给定一个具有不同价值的资源列表（例如resources = [1, 0.8, 1.5, 0.8, 1.2...]），我想以尽可能公平的方式在一组 N 人中共享它们（即，没有人最终会囤积太多价值而其他人拥有的价值太少）。

我认为解决这个问题的一个好方法是最小化函数：

f(r1,...,rN) = (avg - r1)^2 + (avg - r2)^2 + ... + (avg - rN)^2

whereavg = sum(resources) / N和rxis 分配给 person 的资源x。

我偶然发现了scipy.optimize.minimize，我认为这可能会有所帮助，但我无法弄清楚如何描述 的值r1, ..., rn不能是任意的，而是需要取自resources（并且以一种相同的资源不是在解决方案中提供给多个人），因为我没有使用此模块的任何经验，也没有适用于此类问题的强大数学背景。

有没有一种简单的方法可以解决这个问题scipy？

4

1 回答 1

0

这是分区问题的广义变体（优化变体是 NP-hard）。

您的情况的差异：

    1. 你得到的是实数而不是整数
    1. 你寻找一个 n 路分区
    1. 你有不同的损失度量（二次与线性 | l2-norm vs. l1-norm）

现在我会毫不犹豫地说，您的问题仍然是 NP 难题，尽管在需要证明时可能会处理上述差异（1. 通常在温和条件下很容易；例如，在您的情况下：乘以 10；2。容易 3. 不知道我将如何解决这个问题）。

从wikis Partition 文章开始，该文章概述了基本结果和方法（您将看到：2 分区和 n>2 分区复杂性之间存在差异）。

由于这是一个离散优化问题（例如，公式化为二进制二次规划），scipy 在精心选择的方法方面没有提供任何东西：例如，没有（二进制）整数规划。

与 wiki 链接一起提到的内容也将表明，评论中的方法并不能保证最佳解决方案。

于 2019-06-21T21:05:02.700 回答