numero minimo di operazioni per eseguire un operazioni associative su gruppi sovrapposti

Question

Sia V un array di elementi appartenenti a un dominio D (ad esempio numeri interi)

V = {v1, v2, ..., vN} 

Sia f (x, y) sia un operatore binario z = f (x, y) definito in [DxD] -> D.

f è associativo e commutativo.

f non supporta inverso sul suo dominio completo, cioè se il risultato z e uno degli argomenti x o y è noto, non è sempre possibile ottenere l'altro argomento.

Data una coppia ordinata di indici (i, j), l'operatore g (i, j) è definito come la riduzione del sottararray {vi, ..., vj} ottenuto con l'operatore f.

Ad esempio, se f è l'operatore di moltiplicazione, cioè f (x, y) = x * y, poi

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

devo calcolare la g funzionale su un grande insieme di coppie (i, j), che coinvolgono elementi sovrapposti del vettore V.

Vorrei approfittare dell'associatività dell'operatore f per eseguire questo calcolo con il numero minimo possibile di applicazioni dell'operatore f, perché f è computazionalmente molto costoso .

Ad esempio, attenersi all'esempio sopra, dove f è la moltiplicazione intera, dato un array V con 5 voci e le coppie di indici (1,3), (2,4), (2,5), (1,4), posso calcolare tutte le coppie con 6 multiplicatons:

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) 

qualcuno può suggerire un algoritmo per ricavare il grafico ottimale calcolo, come ho fatto manualmente sopra? So che la soluzione al problema non è unica. Qualunque soluzione minima farebbe. Anche una soluzione euristica pseudo-ottimale farebbe.

Answer 1

Questo problema è talvolta chiamato problema dell'interrogazione semigruppo intervallo o problema sommario parziale e vi sono alcune soluzioni sorprendentemente veloci. These slides ricavare una soluzione che n α (n) esegue la pre-elaborazione delle applicazioni di f e supporta le query che effettuano chiamate α (n) in f, dove α è la funzione inversa di Ackermann. C'è anche una carta che dettaglia un even faster approach. Speriamo che questi possano iniziare nella giusta direzione!