Mindestanzahl von Operationen eine assoziative Operationen auf überlappende Sätze zu einer Domäne D gehören, eine Reihe von Elementen (zB ganze Zahlen)</p> <pre><code>V = {v1, v2, ..., vN} </code></pre> <p>Sei f (x, y) werden, um ein Binäroperator

Question

Let V auszuführen z = f (x, y) definiert in [DxD] -> D.

f ist assoziativ und kommutativ.

f unterstützt keine Umkehrung in seiner vollständigen Domäne, d.h. wenn das Ergebnis z und eines der Argumente x oder y bekannt ist, ist es nicht immer möglich, das andere Argument zu erhalten.

Bei einem geordneten Indexpaar (i, j) ist der Operator g (i, j) definiert als die Reduktion des mit dem Operator f erhaltenen Unterfeldes {vi, ..., vj}.

Wenn beispielsweise f den Multiplikationsoperator ist, dh, f (x, y) = x * y, dann

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

ich brauche die funktionelle g auf einer großen Menge von Paaren (i zu berechnen, j), die überlappende Elemente des Vektors V beinhalten. Ich möchte die Assoziativität des Operators f ausnutzen, um diese Berechnung mit der minimal möglichen Anzahl von Anwendungen des Operators f durchzuführen, da f rechnerisch sehr teuer ist .

Zum Beispiel, bei dem obigen Beispiel, wo f ist ganzzahlige Multiplikation, gegeben ein Array V mit 5 Einträgen und den Paaren von Indizes (1,3), (2,4), (2,5), (1,4), kann ich alle Paare mit 6 multiplicatons berechnen:

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) 

kann jemand einen Algorithmus schlägt die optimale Berechnung Diagramm abzuleiten, wie ich manuell oben tat? Ich weiß, dass die Lösung des Problems nicht einzigartig ist. Jede minimale Lösung würde ausreichen. Selbst eine heuristische pseudo-optimale Lösung würde ausreichen.

Answer 1

Dieses Problem wird manchmal als Bereichssigigroup-Abfrageproblem oder Partialsummenproblem bezeichnet, und es gibt einige erstaunlich schnelle Lösungen. These slides herleiten eine Lösung, die n α (n) vorverarbeitenden Anwendungen von f und unterstützt Abfragen machen α (n) Aufrufe an f, wobei α ist die inverse Ackermann-Funktion. Es gibt auch ein Papier, das eine even faster approach ausführlich beschreibt. Hoffentlich können diese Sie in die richtige Richtung bringen!