一連の操作が与えられた場合：
a * b * a * b * a * a * b * a * b
サブストリングの再利用を可能にするために最適なサブディビジョンを取得する方法はありますか。
作る
a * b * a * b * a * a * b * a * b => c * a * c、ここでc = a * b * a * b
そしてそれを見て
a * b * a * b => d * d、ここでd = a * b
全体として、8つの初期操作をここで説明する4つに減らしますか？
（c =（d = a * b）* d）* a * c
もちろん、目標は操作の数を最小限に抑えることです
ある種の接尾辞木を検討しています。
私は特に線形時間ヒューリスティックまたはソリューションに興味があります。'*'演算は、実際には行列の乗算です。
この全体の問題は、「共通部分式の除去」または CSEとして知られています。これは、関数型プログラミング言語のコンパイラの実装者が直面する「グラフ削減」と呼ばれる問題のわずかに小さいバージョンです。「共通部分式除去アルゴリズム」をグーグルで検索すると、多くの解決策が得られますが、特に行列の乗算によって与えられる制約については何もわかりません。
多くの参照を提供するためにリンクされたページ。
私の古い答えは以下です。ただし、もう少し調査した結果、解決策は単純にsuffix treeを構築することです。これは O(N) 時間で実行できます (ウィキペディアのページには多くの参照があります)。これを行うと、サブ式（質問のc、dなど）はサフィックスツリーのノードにすぎません-それらを引き出すだけです。
ただし、グラフ削減の優先順位により、ここで許可できる最適化が許可されない可能性があるため、 MarcoS はLongest Repeating Substring の提案で何かに取り組んでいると思います。
アルゴリズムのスケッチ:
optimise(s):
let sub = longestRepeatingSubstring(s).
optimisedSub = optimise(sub)
return s with sub replaced by optimisedSub
最長の繰り返し部分文字列の各実行には、時間 N がかかります。作成したサフィックス ツリーを再利用して、時間 N ですべてを解決できる可能性があります。
編集: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 による別の回答によると、これは Matrix Chain Multiplication 最適化問題として知られています。Nick Fortescue は、これはより一般的にはhttp://en.wikipedia.org/wiki/Common_subexpression_eliminationとしても知られていると述べています。したがって、一般的な CSE または Matrix-Chain-Multiplication アルゴリズム/ライブラリを文献から見つけて、コストを差し込むことができます。前述の桁数(どのソリューションを使用する場合でも必要になります)。上記の計算 (乗算、累乗など) のコストは、最先端のアルゴリズムを使用して効率的に実行されていることを前提としていることに注意してください。そうでない場合は、指数を操作の実行方法に対応する適切な値に置き換えます。
算術演算を最小限に抑えたい場合は、O(n log n) に減らすことができる行列連鎖乗算を確認する必要があります。
頭の上から、問題はNPにあるようです。行っている置換に応じて、他の置換が可能または不可能になります。たとえば、文字列
d*e*a*b*c*d*e*a*b*c*d*e*aにはいくつかの可能性があります。
最長の共通文字列を取ると、次のようになります。
f = d*e*a*b*c代わりf*f*e*aに、最後に 3 つの乗算と中間の 4 つの乗算 (合計 7 つ) を残すことができます。
代わりに次のように代入
すると、合計 6 つの乗算を使用して
さらに代用できる which がf = d*e*a得られます。f*b*c*f*b*c*fg = f*b*cg*g*f
この問題には他にも代用できるものがありますが、今はそれらをすべて数えている時間はありません。
完全に最小限の置換を行うには、最も長い共通部分文字列だけでなく、各部分文字列が繰り返される回数も把握する必要があると推測しています。それでも、実際の乗算よりも高速になる可能性があります。
これは最も長く繰り返される部分文字列の問題ではありませんか？