在重叠集上执行关联操作的最小操作数

Question

设V是属于域D的元素数组(例如整数)

V = {v1, v2, ..., vN}

设f(x,y)是[DxD] - > D中定义的二元算子z = f(x,y).

f是联想和可交换的.

f不支持其完整域上的逆,即如果结果z和参数x或y中的一个已知,则不总是可以获得另一个参数.

给定一对有序索引(i,j),运算符g(i,j)被定义为用运算符f获得的子数组{vi,...,vj}的减少.

例如,如果f是乘法运算符,即f(x,y)= x*y,则

g(2,5) = v2 * v3 * v4 * v5

我需要在一大组对(i,j)上计算函数g,它们涉及向量V的重叠元素.

我想利用运算符f的关联性来使用运算符f的最小可能应用数来执行该计算,因为f在计算上非常昂贵.

例如,坚持上面的例子,其中f是整数乘法,给定一个包含5个条目的数组V和索引对(1,3),(2,4),(2,5),(1,4) ,我可以用6个乘法计算所有对:

V={1, 2, 0, 3, 5}

1. V12 = V1 * V2
2. V13 = V12 * V3   // pair (1,3)
3. V14 = V13 * V4   // pair (1,3)
4. V23 = V2 * V3
5. V24 = V23 * V4   // pair (2,4)
6. V25 = V24 * V5   // pair (2,5)

任何人都可以建议一个算法来推导出最优的计算图,就像我上面手动做的那样？我知道问题的解决方案并不是唯一的.任何最小的解决方案都会.即使是启发式伪最优解也可以.

Answer 1

这个问题有时被称为范围半群查询问题或部分和问题,并且有一些惊人的快速解决方案.这些幻灯片派生出一个解决方案,它对f进行nα(n)预处理应用,并支持对f进行α(n)调用的查询,其中α是逆Ackermann函数.还有一篇论文详述了更快的方法.希望这些可以让你开始朝着正确的方向前进!