edit: порядки роста в этом ответе необходимы в дополнение к принятому ответу для запуска умножения 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
Примечание: согласно другому ответу Асгейра, это известно как задача оптимизации матричного умножения цепей. Ник Фортескью отмечает, что это также более широко известно как http://en.wikipedia.org/wiki/Common_subexpression_elimination - таким образом, можно найти любой универсальный алгоритм / библиотеку CSE или Matrix-Chain-Multiplication из литературы, и подключить стоимость заказов Величина, о которой я упоминал ранее (вам понадобятся те средства, которые вы используете). Обратите внимание, что стоимость вышеуказанных вычислений (умножение, возведение в степень и т. Д.) Предполагает, что они выполняются эффективно с использованием современных алгоритмов; если это не так, замените экспоненты соответствующими значениями, которые соответствуют способу выполнения операций.