最小乘法与集合覆盖问题

Question

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

R1 = {P1,P2}

R2 = {P2,P4}

R3 = {P2,P3,P4}

R4 = {P1,P2,P4}

....

其中Pi表示整数.

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

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

请注意,也允许分割.例如,我可以首先计算A = P1*P2*P3*P4,然后使用A/P1计算R3的所有元素的乘积,并使用A/P3作为R4.

如果我想使用最小乘法和除法来计算I的每个子集的所有乘积,它是否是一个集合覆盖问题？NP完成？顺便说一句,你能给出一个整数线性程序公式来描述它就像这里一样.

任何建议将受到高度赞赏!

社区编辑:增加假设:

• 允许划分,与乘法相同的成本
• 给定集合中没有重复的元素.例如R5 = {P1, P1, P1, P2}是不允许的

Answer 1

_{考虑元素 R i}的图表_{，没有边。我们现在允许自己添加边，如下所示：}

\n\n

\n
• _{在 R a} \xe2\x86\x92R _b之间添加有向边，用商 R _b /R _a注释。
\n

\n\n

例如，我们可以绘制一条边 R ₁ \xe2\x86\x92R ₃，成本为乘以 R ₁ /R ₃ = P3*P4/P1

\n\n

对所有节点执行此操作，这样您就有 |R| ²边。

\n\n

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

\n\n

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

\n\n

R1 = {P2, P3, P4, P5}\nR2 = {P1, P3, P4, P5}\nR3 = {P1, P2, P4, P5}\nR4 = {P1, P2, P3, P5}\nR5 = {P1, P2, P3, P4}\n

\n\n

最优解是计算P1*P2*P3*P4*P5，然后除以 P _i，共进行 9 次运算。而上面的方法只会执行类似 R1=P2*P3*P4*P5 的操作，然后每次执行乘法和除法以进行 R1\xe2\x86\x92R2, R2\xe2\x86\x92R3, R3\xe2\x86 \x92R4，R4\xe2\x86\x92R5，产生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.虽然我认为有可能创造出需要除法的情况，但似乎找不到一个；如果我找不到一个，情况可能是这样这实际上是一个简单的多项式时间问题。）

\n\n

我将这种方法称为“临时表达”方法。如果我们选择计算一个临时表达式（开始时有一个沉没成本），那么如果我们选择使用它，这将减少所有未来计算遍历一条边的成本（因为可以选择要计算多少个临时表达式）使用）。

\n\n

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

\n\n

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

\n\n

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

\n\n

无论如何，我们如何将这样的系统整合到我们的解决方案中？我们不能添加节点，因为这会扰乱 MST 算法。对于每条边，乘以临时表达式 E 或除以临时表达式 E 不会使某个 P 具有大于幂 p 的值（例如，对于 p=2，我们允许使用中间临时表达式来创建类似的产品，P1 * P4^2 / P3但不允许使用类似的产品P2^3），我们执行该乘法和除法在边缘上，并创建两条新边缘。（我们可能会多次执行此操作，或者在将来执行此操作。）我们还会对边缘的所有子集执行此操作，我们会像上面一样记住这些子集。如果您使用 MST 算法，此方法的成本是边数大幅增加，因此在最坏的情况下可能 (|R| + #newedges) ² = (|R|^|P|) ² ，显着增加找到最佳答案所需的时间。

\n\n

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

\n\n

（旁注：您也许还可以将有关晶格的数学应用于此问题，因为您可以将每个集合视为一个位向量，它们一起构成晶格的基础。）

\n