algorithm - 根据 bool 限制计算将元素放入垃圾箱

Question

我们有一个项目池。每个项目都有一组特征。每个特征都是字符串、整数或 float 。每个项目也属于特定类型。类型是分层的。

我们还有一组垃圾箱。每个箱子都有一个要求，这是一个 bool 表达式，由关于元素特性的原子表达式组成。这些原子表达式可以是字符串、整数或 float 比较和类型比较。

我们希望将元素放入箱子中，以便放入箱子中的每个元素都满足该箱子的要求。每个箱子还必须包含指定数量的元素。

例如，我们可能有以下类型层次结构:

• 形状
  • 三角形
    • 等边三角形
  • 矩形
    • 正方形

我们可以有以下项目:

• 大红三角
• 类型 = 三角形
• color = "红色"
• 面积=1000
• 小身材
• 类型=形状
• 面积= 5
• 大蓝方 block
  • 类型 = 正方形
  • color = "蓝色"
  • 面积 = 2000

这是一个示例容器:

• 大矩形
  • (类型 == 矩形)和(面积 > 750)
  • 项目数 = 5

我们可以将 LargeBlueSquare 放入 LargeRectangles 容器中。我们正好需要在这个箱子里放 5 件元素。

这是另一个例子:

• 非蓝色三角形
  • (type == triangle) and (not (color == "blue"))
  • 项目数 = 10

LargeRedTriangle 可以放入 NonBlueTriangles 容器中。我们正好需要在这个箱子里放 10 件元素。

所以，我们有一组元素和一组箱子。问题是找出在满足约束条件(即对箱子中元素的要求和每个箱子中元素的数量)的情况下，有多少种方法可以将元素放入箱子中。 (我们不需要列举所有的方法；我们只需要知道有多少种不同的方法。)

有没有一种有效的方法来确定这个数字？还是我们只需要“暴力破解”它并尝试所有可能的组合？

Answer 1

如果我理解正确的话，你的问题归结为寻找 Perfect Matchings 的数量的问题。在二分图中。

项目形成左集。垃圾箱形成了权利。如果一个箱子需要 k 件元素，您可以复制该箱子的 k 个副本。

现在，如果某项可能是 bin 的候选，则在该 item 和 bin 之间形成一条边。

现在您需要找出该图中完美匹配的数量。

不幸的是，这是一个难题。计算图中完美匹配的数量相当于找到 Permanent关联矩阵的，即 #P-Complete .请参阅:Computation of the Permanent .

最好的选择可能是随机/近似算法。