考虑你的元素Ri的无边图。我们现在允许自己按以下方式添加边：
- 在Ra→Rb之间添加一条有向边，并注明商Rb/Ra。
例如，我们可以画出一个边缘R1→R3，其成本为乘以R1/R3=P3*P4/P1。
对于所有节点都执行此操作，因此您有|R|²个边缘。
如果你只使用中间结果，你可以使用最小生成树算法来解决这个问题。我相信最小生成树算法在边的数量上非常接近线性（因子是反阿克曼函数，增长比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*P4*P5的过程中，最优解是记住
P1*P2*P3和
P1*P2*P3*P4。然后我们可以免费得到
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难的；如果这不是情况，请有人发表意见。然而，您可以使用启发式算法来猜测有用的即兴表达式。例如，如果您看到R的“大”子集具有“共同P的高密度”，则可以生成所有共同P的乘积的tricknode。如果您对您的Rs子集中看到的所有“大/密集的共同Ps块”都这样做，然后运行MST，您可能会得到稍微更好的答案，而无需进行更一般的搜索。您甚至可以运行算法来帮助检测这些块，例如分层聚类算法。
（旁注：您还可以将格论的数学应用于此问题，因为您可以将每个集合视为位向量，它们一起形成格的基础。）
