编辑:除了接受的答案之外,还需要此答案中的增长顺序才能运行 CSE 或矩阵链乘法
有趣的是,压缩算法可能是您想要的:压缩算法旨在减小其压缩内容的大小,如果它唯一能做到这一点的方法是替换,您可以跟踪它并获得算法所需的子组件。尽管对于小输入,这可能不会给出很好的结果。
在选择这种算法时,哪些操作子集是可交换的将是一个重要的考虑因素。[编辑:OP说在他/她的情况下没有操作是可交换的]
如果我们忽略缓存等影响,我们还可以定义一个最佳解决方案:
input: [some product of matrices to compute]
given that multiplying two NxN matrices is O(N^2.376)
given we can visualize the product as follows:
[[AxB][BxC][CxD][DxE]...]
we must for example perform O(max(A,B,C)^2.376) or so operations in order to combine
[AxB][BxC] -> [AxC]
The max(...) is an estimate based on how fast it is to multiply two square matrices;
a better estimate of cost(A,B,C) for multiplying an AxB * BxC matrix can be gotten
from actually looking at the algorithm, or running benchmarks if you don't know the
algorithm used.
However note that multiplying the same matrix with itself, i.e. calculating
a power, can be much more efficient, and we also need to take that into account.
At worst, it takes log_2(power) multiplies each of O(N^2.376), but this could be
made more efficient by diagonalizing the matrix first.
关于贪婪方法是否可行的问题是:是否应该在每一步压缩重复的子字符串。情况可能并非如此,例如
aaaaabaab
compressing 'aa' results in ccabcb and compressing 'aab' is now impossible
但是我有一种预感,如果我们尝试所有压缩子字符串的顺序,我们可能不会经常遇到这个问题。
因此,在写下我们想要的(成本)并考虑了可能存在的问题之后,我们已经有了一个可以做到这一点的蛮力算法,并且它将运行在非常少量的矩阵上:
# pseudocode
def compress(problem, substring)
x = new Problem(problem)
x.string.replaceall(substring, newsymbol)
x.subcomputations += Subcomputation(newsymbol=substring)
def bestCompression(problem)
candidateCompressions = [compress(problem,substring) for each substring in problem.string]
# etc., recursively return problem with minimum cost
# dynamic programming may help make this more efficient, but one must watch
# out for the note above, how it may be hard to be greedy
注意:根据 Asgeir 的另一个回答,这被称为矩阵链乘法优化问题。Nick Fortescue 指出,这也更普遍地称为http://en.wikipedia.org/wiki/Common_subexpression_elimination - 因此可以从文献中找到任何通用 CSE 或矩阵链乘法算法/库,并插入成本我之前提到的数量级(您将需要那些知道您使用哪种解决方案的人)。请注意,上述计算(乘法、求幂等)的成本假设它们是使用最先进的算法有效完成的;如果不是这种情况,请将指数替换为与执行操作的方式相对应的适当值。