algorithm - 是否有一种算法可以从一组公式中提取最少数量的笛卡尔积？

Question

例如，我们有一组公式如下:

B*2*j
B*3*i
B*3*j
C*2*j
C*3*i
C*3*j
D*2*i
D*2*j
D*3*i
D*3*j

我们可以用三个笛卡尔积来表示上面的公式:

D*(2+3)*(i+j)
(B+c)*3*(i+j)
(B+C)*2*j

所以总数是 3。我们还可以:

3*(B+C+D)*(i+j)
2*(B+C)*D
2*D*(i+j)

这也是 3。

请问是否有算法可以从一组公式中确定笛卡尔积的最小数量？而且还搞出这些产品？

Answer 1

首先，我将编写一组公式作为由 + 分隔的术语，因为您正在寻找的转换在代数上是有意义的(除了您不想合并的事实像 2+3 这样的数字变成 5)。

您可以使用的基本操作是因式分解:将两个项(如ABC+ABD)组合成AB(C+D)。根据您的评论，您只能生成由单因子项总和组成的新因子，如上例中的 C+D；你不能分解例如ABCD+ABDE 转换为 AB(CD+DE)。

当且仅当它们正好共享 k-1 个因子时，您才可以分解 2 个 k 因子项。(例如，在我的 ABC+ABD 示例中，k=3。)每个这样的因式分解都会将集合中的项数减少 1:删除 2 个并重新添加 1 个。

在组合 3 个或更多项时多次执行此操作:ABC+ABD+ABE 可以首先分解为 AB(C+D)+ABE，然后分解为那些2 项再次因式分解为 AB(C+D+E)。请注意，我们以何种顺序列出总和中的项或乘积中的因子并不重要，在构建包含 3 个或更多项的因子时执行因式分解步骤的顺序也不重要。

然后我们可以将问题框定为图中的搜索问题，其中起始顶点对应于原始公式 (B*2*j + B*3*i + ... + D*3 *j 在你的例子中)并且从每个顶点 v 发出到它的子顶点的弧，每个弧对应于对 v 执行一些因式分解的结果。 v 将有一个子顶点用于可以执行的每个可能的因式分解在上面;如果 v 中有 m 个项，那么这意味着在最坏的情况下它最多可以有 m(m-1)/2 个子项，因为可能所有 m 个项共享 k-1 个因子的完整补充，这意味着它们中的任何一对都可以组合。

如果一个顶点没有可以通过因式分解码合的项对，那么它就是一个“叶子”——它没有 child ，不能进一步处理。我们想要找到的是具有最少项数的叶顶点。由于对应于图中弧线的每个因式分解都会将项数减少 1，因此这相当于搜索可能最深的顶点。这可以使用 DFS 或 BFS 来完成。但是请注意，使用这种方法可以多次生成相同的表达式(顶点)，因此维护一个哈希表 seen 来记录所有已处理的表达式对于性能至关重要；然后如果我们访问一个顶点，尝试为它生成一个 child ，并且看到这个 child 已经在 seen 中，我们就避免再次访问这个 child 。

为了减轻通过同一组因式分解的多个不同顺序生成相同表达式的现象，您可以添加一个规则:order v 的子因式分解以某种方式，以便如果有 n子节点它们对应于此顺序中的因式分解 1、2、...、n，并在每个子顶点的单独“已跳过”字段中记录较早(在顺序中)因式分解被跳过以生成这个 child 。然后，当访问一个顶点时，避免生成它的任何“已经跳过”的因式分解作为 child ，因为这样做会创建一个与其他一些现有顶点相同的顶点(通过以相反的顺序执行相同的一对操作)。

可能还有其他可用的加速方法可以减少首先生成的重复顶点的数量，但这应该足以获得解决小问题的结果。