algorithm - 最小乘法与集合覆盖问题

Question

我有一个集合 I ={P1, P2, ..., Pm} 和 I 的 n 个有限子集，用 R1,R2,...,Rn 表示如下:

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2, P3, P4}

R4 = {P1, P2, P4}

....

其中 Pi 表示一个整数。

对于每个 Ri，我想计算其所有元素的乘积。
我的目标是通过在 Ri (i=1,2,...,n) 之间共享一些公共(public)部分，尽可能少地使用乘法和除法。

例如，如果我可以先计算 P2*P4，那么这个结果就可以用于计算 R3 和 R4 的所有元素的乘积。

请注意，也允许除法。例如，我可以先计算 A=P1*P2*P3*P4，然后使用 A/P1 计算 R3 的所有元素的乘积，然后使用 A/P3 计算 R4。

如果我想使用最小乘法和除法来计算 I 的每个子集的所有乘积，这是一个集合覆盖问题吗？ NP完全？顺便说一句，你能不能给出一个整数线性规划公式来描述它就像 here .

任何建议将不胜感激!

社区编辑:附加假设:

允许除法，与乘法相同的成本

给定集合中没有重复的元素。例如R5 = {P1, P1, P1, P2}不允许

Answer 1

考虑一个没有边的元素 Ri 的图。我们现在允许自己添加边如下:

在 Ra→Rb 之间添加一条有向边，用商 Rb/Ra 注释。

例如，我们可以绘制一条边 R1→R3，其代价是乘以 R1/R3 = P3*P4/P1

对所有节点执行此操作，因此您有 |R|2 条边。

现在，如果您只使用中间结果，您可以使用最小生成树算法来解决这个问题。我相信 MST 算法在边的数量上非常接近线性(逆阿克曼的一个因子，比 log(log(log(...log(n)...))) 增长慢)；甚至可能存在边数方面的随机线性时间算法，例如 http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/07/Karger95.pdf因此，这个基本算法将花费 |R|2 时间。

但是，如果您只使用中间结果，您就会失去真正的最佳答案，因为可以使用我们凭空提取的“临时”表达式来获得更好的性能。例如，您可能会考虑这种情况:

R1 = {P2, P3, P4, P5}
R2 = {P1, P3, P4, P5}
R3 = {P1, P2, P4, P5}
R4 = {P1, P2, P3, P5}
R5 = {P1, P2, P3, P4}

最优解是计算 P1*P2*P3*P4*P5 ，然后除以 Pi，得到 9 次运算。而上面的方法只会做R1=P2*P3*P4*P5这样的事情，然后每次都进行一次乘除运算，R1→R2，R2→R3，R3→R4，R4→R5，共11次运算。 (如果我们没有除法，我们也会有 9 个操作: b=P1*P2 c=b*P3 r5=c*P4 r4=c*P5, d=P4*P5, r3=b*d, e= P3*d, r1=e*P2, r2=e*P1. 虽然我认为有可能创造需要除法的情况，但似乎找不到；如果我找不到，可能是这样这实际上是一个简单的多项式时间问题。)

我将这种方法称为“临时表达”方法。如果我们选择计算一个临时表达式(开始时的单个沉没成本)，如果我们选择使用它，这将减少所有 future 计算遍历一条边的成本(因为可能有多少临时表达式的选择)用)。

这给我们带来了一个非常小的旁注:

Theorem:
  You should have at least one intermediate expression of each 
  length up to the maximum size of any R.
Proof (induction):
  To build up a product of size N, you will need to do 
  have a product of size N-1.

注意这个定理，事实证明我们在上面有点错误。最佳解决方案是记住 P1*P2*P3和 P1*P2*P3*P4正在计算中 P1*P2*P3*P4*P5 .那么我们可以得到 R5免费(和 R4 仅通过另一种方式进行一次乘法，不幸的是成本与以前相同)，将总成本从 9 减少到 8。这导致我们疯狂猜测执行 http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm在很长一段时间后，具有任意边也可能会产生最佳解决方案。

无论如何，我们如何将这样的系统整合到我们的解决方案中？我们不能添加节点，因为那会弄乱 MST 算法。对于每条边，用临时表达式 E 乘或除不会使某些 P 具有大于 p 的幂(例如，对于 p=2，我们允许中间临时表达式创建像 P1 * P4^2 / P3 这样的产品，但不允许像 P2^3 这样的产品)，我们在边上执行乘法和除法，并创建两个新边。 (我们可能会不止一次这样做，或者在 future 的日期。)我们也对边缘的所有子集这样做，我们会像上面一样记住。这种方法的代价，如果你使用MST算法，就是边的数量增加很多，所以也许(|R| + #newedges)2 = (|R|^|P|)2 可能在最坏的情况下，显着增加了找到最佳答案所需的时间。

因此，似乎更一般的问题是 NP-hard，作为猜测；如果不是这种情况，请有人插话。但是，您或许可以使用启发式方法来猜测要使用的有用临时表达式。例如，如果您看到 R 的“大”子集具有“高密度的公共(public) Ps”，您可能会生成所有公共(public) Ps 的乘积的技巧节点。如果您对在 Rs 的子集中看到的所有“大/密集的公共(public) Ps 块”执行此操作，然后运行 ​​MST，您可能会得到稍微更好的答案，而无需进行更一般的搜索。您甚至可以运行算法来帮助检测此类团块，例如层次聚类算法。

(旁注:您也可以将有关格的数学应用于此问题，因为您可以将每个集合视为一个位向量，它们共同构成格的基础。)