5

我有一个集合 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) 之间共享一些公共部分来尽可能少地使用乘法和除法。

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

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

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

任何建议将不胜感激！

社区编辑：附加假设：

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

3 回答 3

1

首先，你不需要除法

这里不需要除法，它总是一个额外的计算。

如果您需要除法，则意味着您已经进行了乘法运算，因此，如果您进行除法，则撤消已经完成的工作。

例如，如果您通过将 Pi*Pj*Pk*Pn 除以 Pn 来计算 Pi*Pj*Pk，这意味着您之前计算了 Pi*Pj*Pk*Pn，因此您之前计算了 Pi*Pj*Pk。

（我假设你所有的数字都是素数）

我的解决方案

我有一个不考虑分裂可能性的想法。

您可以使用 Ri 开始构建后缀树。

那么乘法的数量将是树中的边数。

例子 ：

使用您的示例，后缀树将是：

       P2
      / \
     P4 P1
    / \ 
   P3 P1

你得到 4 乘法：

M1=P1*P2

M2=P2*P4

M3=M2*P1

M4=M2*P3

找到最小的乘法次数相当于构建具有最少边数的后缀树。

希望这会有所帮助。

于 2012-05-30T17:26:46.963 回答
1

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

  • 在 R a →R b之间添加一条有向边，用商 R b /R a注释。

例如，我们可以画一条边 R 1 →R 3，成本乘以 R 1 /R 3 = 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，然后除以 P i，得到 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. 虽然我认为可能会产生需要除法的情况，但似乎找不到；如果我找不到，可能是这样的情况这实际上是一个简单的多项式时间问题。）

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

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

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），我们执行乘法和除法在边缘上，并创建两个新边缘。（我们可能不止一次这样做，或者在未来的日期。）我们也对边缘的所有子集这样做，我们会像上面那样记忆。这种方法的代价，如果你使用MST算法，就是边的数量大幅增加，所以可能(|R| + #newedges) 2 = (|R|^|P|) 2也许在更糟糕的情况下，会显着增加找到最佳答案所需的时间。

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

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

于 2012-05-30T17:34:08.373 回答
1

如果没有除法，这似乎等同于Gary & Johnson中描述的问题 ENSEMBLE COMPUTATION ，因此是 NP-complete。

[PO9] 集成计算

实例：有限集 A 的子集的集合 C，正整数 J。

问题：是否存在 j <= J 联合操作的序列 S = (z_1 <- x_1 U y_1, z_2 <- x_2 U y_2, ..., z_j <- x_j U y_j)，其中每个 x_i 和 y_i 都是 { a} 对于 A 中的某个 a 或对于某些 k < i 的 z_k，使得 x_i 和 y_i 不相交，1 <= i <= j，并且对于 C 中的每个子集 c 都存在一些 z_i，1 <= i < = j，这与 C 相同。

你的集合I对应A，每个R_i对应C的一个元素，乘法对应集合并集。

于 2012-05-31T00:04:04.583 回答