edit: Les ordres de la croissance dans cette réponse sont nécessaires, en plus de la accepté de répondre dans l'ordre à exécuter le CST ou la matrice de la chaîne de multiplication
Fait intéressant, un algorithme de compression peut être ce que vous voulez: un algorithme de compression vise à réduire la taille de ce qu'il se comprime, et si la seule façon de le faire, c'est la substitution, vous pouvez le tracer et d'obtenir les sous-composants de votre algorithme. Cela peut ne pas donner de bons résultats, bien que pour de petites entrées.
Ce sous-ensembles de vos opérations sont commutatives sera un facteur important dans le choix d'un tel algorithme. [edit: OP dit pas opérations sont commutatives dans sa situation]
Nous pouvons aussi définir une solution optimale, si l'on ignore les effets tels que la mise en cache:
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.
Il y a la question de savoir si une approche gourmande est faisable pour pas: si l'on DOIT compresser répétition de sous-chaînes à chaque étape. Cela peut ne pas être le cas, par exemple,
aaaaabaab
compressing 'aa' results in ccabcb and compressing 'aab' is now impossible
Toutefois, j'ai un pressentiment que, si nous essayons de tous les ordres de la compression des sous-chaînes, nous allons probablement pas dans cette question trop souvent.
Ainsi, après avoir écrit ce que nous voulons (les coûts) et considérés comme possiblement questions, nous avons déjà une force brute de l'algorithme qui peut faire cela, et il sera exécuté pour un très petit nombre de matrices:
# 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
Remarque: selon une autre réponse par Asgeir, ceci est connu comme la Matrice de la Chaîne d'Multiplication problème d'optimisation. Nick Fortescue notes c'est connu aussi, plus généralement, comme http://en.wikipedia.org/wiki/Common_subexpression_elimination -- ainsi, on pourrait trouver un médicament générique du CST ou la Matrice de la Chaîne d'-algorithme de Multiplication/bibliothèque de la littérature, et de brancher le coût des ordres de grandeur je l'ai mentionné plus tôt (vous aurez besoin de ces nomatter la solution que vous utilisez). Notez que le coût des calculs ci-dessus (multiplication, puissance, etc.) supposons qu'ils sont fait de manière efficace avec l'état-of-the-art des algorithmes; si ce n'est pas le cas, remplacer les exposants avec les valeurs appropriées qui correspondent à la manière dont les opérations seront effectuées.
