什么软件算法可以从一个大集合中选择一个多样化的子集

Question

什么软件算法可以从一个大集合中选择一个多样化的子集

algorithmsubsetknapsack-problem

3

设置

假设我有非常多的物品，每个物品都具有形状、大小和颜色。它们可以是：

三角形、圆形或正方形
红色、绿色或蓝色
小号或大号

我不能对这些属性在物品中的分布作出任何假设。我“有把握”它们不全是一百万个大号的红色三角形，但这总是有可能的。

问题

我想从我的物品中挑选36个，在所有属性类别上尽可能地“多样化”。澄清一下，从很多物品中选取36个后，我理想情况下想要12个红色、12个绿色、12个蓝色、12个三角形和18个小号等。

现在有18种可能的不同物品类型（3种颜色 * 3种形状 * 2种大小），所以一种方法是包括每种不同类型的两个（假设我有它们）。

如果我没有足够数量的每种不同类型，另一种（不切实际且粗暴）的方法是迭代每种可能的36个物品的子集，并保留最佳子集。

我相信这是一个特定实例，可以通过已知算法解决更广泛的问题类，但我无法确定谷歌的“奥秘”。我将其标记为背包问题，因为感觉或许是这个问题，但我想知道是否有更好的解决方法？

您能帮忙提供解决方案或至少合适的搜索术语吗？

- Dave Durbin

嗨，很有趣，也许这可能会引起兴趣 https://math.stackexchange.com/questions/3536902/how-can-i-reward-diversity-in-an-objective-function-in-integer-programming - IronMan

2

这个问题类似于 https://dev59.com/96Xja4cB1Zd3GeqPKwIK，但因未符合 Stack Overflow 的指南而被关闭。我认为你的问题可能会在 https://math.stackexchange.com 上得到答案。 - Shridhar R Kulkarni

1

正确定义“尽可能多样化”。我明白理想情况下您希望有12个红色，12个绿色，12个蓝色，12个三角形，18个小的和18个大的。但如果无法做到呢？接下来最好的选择是什么？我们如何比较两个不同的选择以确定哪一个更好？请尝试想出一种公式，为选择分配数字分数，以便我们可以考虑最大化该分数的算法。 - yemre

2

投票重新开放，因为这个问题正在寻求一个软件算法，根据Tour的规定，这是SO的主题。 - David Eisenstat

@yemre 没有任何个别属性比其他属性更重要。我认为，如果我们将答案表示为一个具有 8 个元素的向量（3 种形状 + 3 种颜色 + 2 种大小），那么“正确”的答案将是 [12,12,12,12,12,12,18]T（或者我们可以使用分数：[1/3，1/3，...]T）。然后，实际答案和正确答案之间的简单曼哈顿距离就足够了。显然，距离会是偶数，因为额外的三角形意味着其他形状少一个，但这不会影响优化。 - Dave Durbin

1个回答

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

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

- orlp · Answer 1

看一下蓄水池抽样。为每种形状/颜色/尺寸组合（即36个蓄水池）建立一个蓄水池，每个蓄水池容量为36。对所有元素进行一次遍历，对于每个元素选择其适当的蓄水池并执行蓄水池抽样步骤。

这将把您的问题最多减少到36*36 = 1296个元素，从中公平地抽样，并覆盖即使只有单个组合的最坏情况。

然后，您可以简单地洗牌蓄水池，从每个蓄水池中随机选择一个元素（跳过空蓄水池），并将它们从蓄水池中删除。如果您拥有每种形状/颜色/尺寸的一个元素，则立即完成。如果没有，则再次洗牌蓄水池并进行另一次遍历，一直重复此过程，直到选择了36个元素。这将为您提供数据集上的均匀样本，通过形状/颜色/尺寸偏差进行归一化。