Accelerare una funzione con la programmazione dinamica

Question

ho questo programma

//h is our N 
    static int g=0; 
    int fun(int h){ 
     if(h<=0){ 
        g++; 
        return g; 
        } 
    return g+fun(h-1)+fun(h-4); 
    } 

E 'possibile accelerarlo utilizzando la programmazione dinamica?

ho capito che questa funzione viene eseguito in O (2^n)

sono supposto per ridurre il tempo di esecuzione per la programmazione dinamica, ma non capisco il concetto.

Basta chiedere una spinta nella giusta direzione.

Answer 1

Anche se non posso dare una risposta alla tua domanda attuale, sono incuriosito da qualcosa di completamente diverso, vale a dire la dichiarazione

return g+fun(h-1)+fun(n-4); 

Ovviamente, la funzione ha l'effetto collaterale di cambiare la variabile statica globale g . Non sono sicuro al 100% se l'espressione dell'istruzione return valuta effettivamente in modo chiaramente definito o se il risultato potrebbe essere indefinito.

Potrebbe essere un buon esercizio pensare all'ordine in cui vengono eseguite quelle chiamate di funzione e come questo influisce su g e quindi sul risultato della funzione.

Answer 2

Sì, è possibile utilizzare DP per velocizzarlo ed evitare l'utilizzo dello stack CPU, ma concordo con stakx sull'effetto collaterale della modifica della variabile statica globale g. È meglio fornire un'espressione matematica perché la funzione ricorsiva di cui sopra potrebbe dare un risultato diverso a seconda del conteggio delle chiamate dell'ordine &.

Answer 3

Se definiamo che l'ordine di sommatoria in g + fun (h-1) + fun (n-4) è da sinistra a rigth, questo è un problema ben definito. Con che ottengo i valori per il divertimento (n), n = 1, ..., 15: valore

3, 6, 10, 15, 33, 74, 154, 295, 575, 1143, 2269, 4414, 8508, 16396, 31634 

ritorno di divertimento (n) viene valutato come sequenza di sommatorie con elementi non-discendenti. Ogni summomm è per uno più grande del precedente (return g ++;) o uguale al precedente (restituisce g + fun() + fun()). La sequenza di esecuzione delle istruzioni di ritorno dipende solo dal parametro di input fun(). Quindi, con g impostato sul valore iniziale! = 0 otteniamo gli stessi summms come con g = 0, ma ogni summand è più grande per lo stesso valore iniziale. Con questo, il divertimento (n) con g iniziale> 0 si valore che è g * numero di istruzioni return eseguite di dimensioni superiori con g iniziale = 0.

definire una (n) come numero di istruzioni eseguite ritorno tornare durante l'esecuzione di fun (n) e G (n) numero di dichiarazioni di reso eseguite in se la clausola (uguale al numero di esecuzioni di istruzioni g ++). Per A e G tiene:

A(n) = A(n-1) + A(n-4) + 1 
G(n) = G(n-1) + G(n-4) 
A(n) = 1 and G(n) = 1, for n <= 0 

Da queste osservazioni si può vedere che per n> 0 vale:

fun(n) = fun(n-1) + G(n-1) * A(n-4) + fun(n-4) 

implementazione di Python Semplice:

def x(h): 
    Rg = { -3:1, -2:1, -1:1, 0:1 } 
    Ra = { -3:1, -2:1, -1:1, 0:1 } 
    F = { -3:1, -2:1, -1:1, 0:1 } 
    for i in xrange(1, h+1): 
    F[i] = F[i-1] + Rg[i-1]*Ra[i-4] + F[i-4] 
    print i, F[i] 
    Rg[i] = Rg[i-1] + Rg[i-4] 
    Ra[i] = Ra[i-1] + Ra[i-4] + 1 

@stakx: per l'espressione g + fun (h-1) + fun (h-4) non possiamo avere garanzia di valutazione, specialmente non in C.

Answer 4

OK. Partiamo dal divertimento (una versione serializzata in cui l'ordine di valutazione è forzato). attenzione

int fun(int h){ 
    if(h<=0){ 
     g++; 
     return g; 
    } 
    int tmp1 = g; 
    int tmp2 = fun(h-1); 
    int tmp3 = fun(h-4); 
    return tmp1+tmp2+tmp3; 
} 

Let su G e dimenticare il risultato attuale della funzione

Ora è facile per modificare la funzione di passare in g come parametro e di restituire il nuovo valore di g di conseguenza.

int gun(int h, int g0){ 
    if(h<=0){ 
     return g0+1; 
    } 
    int tmp1 = g0; 
    int tmp2 = gun(h-1, g0); 
    int tmp3 = gun(h-4, tmp2); 
    return tmp3; 
} 

What can be simplified into: 

int gun(int h, int g0){ 
    if(h<=0){ 
     return g0+1; 
    } 
    return gun(h-4, gun(h-1, g0)); 
} 

Ora torniamo al divertimento:

int fun2(int h, int g0){ 
    if(h<=0){ 
     return g0+1; 
    } 
    return g0+fun2(h-1, g0)+fun2(h-4, gun(h-1,g0)); 
} 

fun2 fa esattamente la stessa cosa come il divertimento iniziale, ma ora come abbiamo rimosso l'effetto collaterale e la funzione dipende solo dal suo parametro, possiamo Memoize risultati (archivia i risultati già calcolati in un array), che dovrebbe accelerare il calcolo.

Possiamo ancora semplificare un po 'la pistola. Il parametro G0 non è realmente necessario, impostiamo a 0.

int gun2(int h){ 
    if(h<=0){ 
     return 1; 
    } 
    return gun2(h-4) + gun2(h-1); 
} 

Possiamo anche definire un fun3 con il parametro G0 fisso a 0, d'ora in poi un po 'più semplice, ma ha ancora chiamare fun2. Non vedo ancora come semplificare ulteriormente, ma probabilmente è possibile.

int fun3(int h){ 
    if(h<=0){ 
     return 1; 
    } 
    return fun3(h-1)+fun2(h-4, gun2(h-1)); 
}