Programmazione dynamic e memoization: approcci bottom-up vs top-down

Non sono sicuro di aver compreso correttamente l’approccio dall’alto verso il basso con la memoizzazione e il metodo bottom-up.

In basso: è dove si guardano prima i sottoproblemi “più piccoli” e poi si risolvono i sottoproblemi più grandi usando la soluzione al problema più piccolo.

Top-down: risolvi il problema in modo naturale e controlla se hai già calcolato la soluzione per il sottoproblema.

Sono un po ‘confuso. Qualcuno può spiegarlo? E qual è la differenza?

    rev4: un commento molto eloquente da parte dell’utente Sammaron ha notato che, forse, questa risposta precedentemente confusa dall’alto verso il basso e dal basso verso l’alto. Mentre originariamente questa risposta (rev3) e altre risposte dicevano che “bottom-up è la memoizzazione” (“assume i sottoproblemi”), potrebbe essere l’inverso (cioè “dall’alto in basso” potrebbe essere “assumere i sottoproblemi” e ” dal basso verso l’alto “può essere” comporre i sottoproblemi “). In precedenza, ho letto sulla memoizzazione come un tipo diverso di programmazione dynamic rispetto a un sottotipo di programmazione dynamic. Stavo citando quel punto di vista, nonostante non l’abbia sottoscritto. Ho riscritto questa risposta per essere agnostico della terminologia fino a quando i riferimenti adeguati possono essere trovati in letteratura. Ho anche convertito questa risposta in una wiki della comunità. Si prega di preferire fonti accademiche. Elenco di riferimenti: {Web: 1 , 2 } {Letteratura: 5 }

    Ricapitolare

    La programmazione dynamic consiste nell’ordinare i calcoli in modo da evitare il ricalcolo del lavoro duplicato. Hai un problema principale (la radice del tuo albero di sottoproblemi) e sottoproblemi (sottoalberi). I sottoproblemi tipicamente si ripetono e si sovrappongono .

    Ad esempio, considera il tuo esempio preferito di Fibonnaci. Questo è l’albero completo di sottoproblemi, se abbiamo fatto una chiamata ricorsiva ingenua:

    TOP of the tree fib(4) fib(3)...................... + fib(2) fib(2)......... + fib(1) fib(1)........... + fib(0) fib(1) + fib(0) fib(1) fib(1) fib(0) fib(1) fib(0) BOTTOM of the tree 

    (In alcuni altri rari problemi, questo albero potrebbe essere infinito in alcuni rami, rappresentando la non-terminazione, e quindi il fondo dell’albero potrebbe essere infinitamente grande. Inoltre, in alcuni problemi potresti non sapere come appare l’intero albero prima di Quindi, potresti aver bisogno di una strategia / un algoritmo per decidere quali sottoproblemi rivelare.)


    Memoizzazione, tabulazione

    Esistono almeno due principali tecniche di programmazione dynamic che non si escludono a vicenda:

    • Memoizzazione – Questo è un approccio laissez-faire: si presuppone di aver già calcolato tutti i sottoproblemi e di non avere idea di quale sia l’ordine di valutazione ottimale. In genere, si esegue una chiamata ricorsiva (o un equivalente iterativo) dalla radice e si spera che si avvicini all’ordine di valutazione ottimale o si ottenga una prova che si arriverà all’ordine di valutazione ottimale. Si farebbe in modo che la chiamata ricorsiva non ricalcoli mai un sottoproblema poiché si memorizzano nella cache i risultati e quindi i sottostrutture duplicati non vengono ricalcolati.

      • esempio: se stai calcolando il fib(100) Fibonacci sequence fib(100) , chiameresti questo, e chiamerebbe fib(100)=fib(99)+fib(98) , che chiamerebbe fib(99)=fib(98)+fib(97) , … ecc., che chiamerebbe fib(2)=fib(1)+fib(0)=1+0=1 . Allora risolverebbe fib(3)=fib(2)+fib(1) , ma non ha bisogno di ricalcolare fib(2) , perché lo abbiamo memorizzato nella cache.
      • Questo inizia nella parte superiore dell’albero e valuta i sottoproblemi delle foglie / sottostrutture di nuovo verso la radice.
    • Tabulazione – Si può anche pensare alla programmazione dynamic come un algoritmo di “riempimento del tavolo” (sebbene solitamente multidimensionale, questa “tabella” può avere geometria non euclidea in casi molto rari *). Questo è come la memoizzazione ma più attivo e comporta un ulteriore passaggio: devi scegliere, prima del tempo, l’ordine esatto in cui eseguirai i tuoi calcoli. Questo non dovrebbe implicare che l’ordine debba essere statico, ma che tu abbia molta più flessibilità della memoizzazione.

      • esempio: se stai eseguendo fibonacci, puoi scegliere di calcolare i numeri in questo ordine: fib(2) , fib(3) , fib(4) … memorizzando nella cache ogni valore in modo da poter calcolare i successivi più facilmente. Puoi anche pensare a come riempire un tavolo (un’altra forma di memorizzazione nella cache).
      • Personalmente non sento molto la parola ‘tabulazione’, ma è un termine molto dignitoso. Alcune persone considerano questa “programmazione dynamic”.
      • Prima di eseguire l’algoritmo, il programmatore prende in considerazione l’intero albero, quindi scrive un algoritmo per valutare i sottoproblemi in un ordine particolare verso la radice, generalmente compilando una tabella.
      • * nota a piè di pagina: a volte la ‘tabella’ non è una tabella rettangular con connettività a griglia di per sé. Piuttosto, può avere una struttura più complicata, come un albero o una struttura specifica per il dominio del problema (ad esempio, città all’interno di una distanza percorsa su una mappa), o anche un diagramma a traliccio, che, pur essendo simile a una griglia, non ha una struttura di connettività up-down-left-right, ecc. Ad esempio, user3290797 ha collegato un esempio di programmazione dynamic per trovare il set indipendente massimo in un albero , che corrisponde a riempire gli spazi vuoti in un albero.

    (In generale, in un paradigma di “programmazione dynamic”, direi che il programmatore considera l’intero albero, quindi scrive un algoritmo che implementa una strategia per valutare i sottoproblemi in grado di ottimizzare le proprietà desiderate (di solito una combinazione di complessità temporale) e la complessità dello spazio). La tua strategia deve iniziare da qualche parte, con qualche particolare sottoproblema e forse può adattarsi in base ai risultati di tali valutazioni. Nel senso generale della “programmazione dynamic”, potresti provare a mettere in cache questi sottoproblemi, e altro ancora in generale, cerca di evitare di rivisitare i sottoproblemi con una sottile distinzione, forse essendo il caso di grafici in varie strutture di dati.Molto spesso, queste strutture di dati sono al centro come matrici o tabelle.Le soluzioni ai sottoproblemi possono essere buttate via se non ne abbiamo bisogno più.)

    [In precedenza, questa risposta faceva una dichiarazione sulla terminologia top-down vs bottom-up; ci sono chiaramente due approcci principali chiamati Memoization e Tabulation che possono essere in bijection con quei termini (sebbene non del tutto). Il termine generale che la maggior parte delle persone usa è ancora “Programmazione Dinamica” e alcune persone dicono “Memoizzazione” per riferirsi a quel particolare sottotipo di “Programmazione Dinamica”. Questa risposta rifiuta di dire quale sia top-down e bottom-up fino a quando la comunità non troverà riferimenti adeguati nei documenti accademici. In definitiva, è importante capire la distinzione piuttosto che la terminologia.]


    Pro e contro

    Facilità di codifica

    La memoizzazione è molto facile da codificare (generalmente è ansible * scrivere un’annotazione “memoizer” o una funzione wrapper che lo fa automaticamente per te) e dovrebbe essere la prima linea di approccio. Il rovescio della medaglia è che devi elaborare un ordine.

    * (questo è in realtà solo facile se stai scrivendo la funzione tu stesso, e / o codifica in un linguaggio di programmazione impuro / non funzionale … per esempio se qualcuno ha già scritto una funzione fib precompilata, necessariamente fa chiamate ricorsive a se stessa, e non puoi memorizare magicamente la funzione senza garantire che quelle chiamate ricorsive chiamino la tua nuova funzione memoized (e non la funzione originale non commemora))

    ricorsività

    Nota che sia dall’alto verso il basso che dal basso verso l’alto può essere implementato con ricorsione o riempimento di tabelle iterativo, sebbene non sia naturale.

    Preoccupazioni pratiche

    Con la memoizzazione, se l’albero è molto profondo (ad esempio fib(10^6) ), si esaurirà lo spazio di stack, poiché ogni calcolo ritardato deve essere messo in pila e ne avrai 10 ^ 6.

    ottimalità

    L’approccio potrebbe non essere ottimale nel tempo se l’ordine in cui si verificano (o tentare di) visitare i sottoproblemi non è ottimale, in particolare se esiste più di un modo per calcolare un sottoproblema (normalmente il caching risolverebbe questo, ma è teoricamente ansible che il caching potrebbe non in alcuni casi esotici). La Memoizzazione di solito aggiunge complessità temporale alla tua complessità spaziale (ad esempio con la tabulazione hai più libertà di scartare calcoli, come usare la tabulazione con Fib ti permette di usare lo spazio O (1), ma la memoizzazione con Fib usa O (N) impilare lo spazio).

    Ottimizzazioni avanzate

    Se stai anche facendo un problema estremamente complicato, potresti non avere altra scelta che fare tabulazione (o almeno assumere un ruolo più attivo nel guidare la memoizzazione dove vuoi che vada). Inoltre, se ti trovi in ​​una situazione in cui l’ottimizzazione è assolutamente critica e devi ottimizzare, la tabulazione ti consentirà di fare ottimizzazioni che la memorizzazione non ti permetterebbe altrimenti di fare in modo sano. A mio modesto parere, nella normale ingegneria del software, nessuno di questi due casi è mai venuto fuori, quindi userei solo la memoizzazione (“una funzione che memorizza le sue risposte nella cache”) a meno che qualcosa (come lo spazio dello stack) renda necessaria la tabulazione … anche se tecnicamente per evitare uno stack blowout puoi 1) aumentare il limite di dimensioni dello stack in lingue che lo consentono, o 2) mangiare un fattore costante di lavoro extra per virtualizzare il tuo stack (ick) o 3) programma in stile di passaggio continuo, che in effetti virtualizza anche il tuo stack (non è sicuro della complessità di questo, ma fondamentalmente si prenderà effettivamente la catena di chiamate posticipata dalla pila di dimensione N e di fatto la si attacca in N funzioni di thunk successivamente nidificate … anche se in alcune lingue senza un’ottimizzazione delle chiamate di coda potresti dover trampolino per evitare lo scoppio di una pila).


    Esempi più complicati

    Qui elenchiamo esempi di particolare interesse, che non sono solo problemi generali di DP, ma distinguono in modo interessante memoria e tabulazione. Ad esempio, una formulazione potrebbe essere molto più semplice dell’altra oppure potrebbe esserci un’ottimizzazione che richiede fondamentalmente una tabulazione:

    • l’algoritmo per calcolare edit-distance [ 4 ], interessante come un esempio non banale di un algoritmo di riempimento di tabelle bidimensionale

    Top down e bottom up DP sono due modi diversi per risolvere gli stessi problemi. Si consideri una soluzione di programmazione memoized (dall’alto verso il basso) vs dynamic (dal basso verso l’alto) per calcolare i numeri di Fibonacci.

     fib_cache = {} def memo_fib(n): global fib_cache if n == 0 or n == 1: return 1 if n in fib_cache: return fib_cache[n] ret = memo_fib(n - 1) + memo_fib(n - 2) fib_cache[n] = ret return ret def dp_fib(n): partial_answers = [1, 1] while len(partial_answers) <= n: partial_answers.append(partial_answers[-1] + partial_answers[-2]) return partial_answers[n] print memo_fib(5), dp_fib(5) 

    Personalmente trovo la memoizzazione molto più naturale. Puoi prendere una funzione ricorsiva e memorizzarla con un processo meccanico (prima la risposta di ricerca nella cache e restituirla se ansible, altrimenti calcolarla in modo ricorsivo e poi prima di tornare, si salva il calcolo nella cache per un uso futuro), mentre si fa dal basso verso l'alto la programmazione dynamic richiede la codifica di un ordine in cui vengono calcolate le soluzioni, in modo tale che nessun "grosso problema" venga calcolato prima del problema più piccolo da cui dipende.

    Una caratteristica chiave della programmazione dynamic è la presenza di sottoproblemi sovrapposti . In altre parole, il problema che si sta tentando di risolvere può essere suddiviso in sottoproblemi e molti di questi sottoproblemi condividono problemi secondari. È come “Dividi e conquista”, ma finisci per fare la stessa cosa molte, molte volte. Un esempio che ho usato dal 2003 quando insegnavo o spiegavo questi argomenti: puoi calcolare i numeri di Fibonacci in modo ricorsivo.

     def fib(n): if n < 2: return n return fib(n-1) + fib(n-2) 

    Usa la tua lingua preferita e prova a eseguirla per fib(50) . Ci vorrà molto, molto tempo. Circa tanto tempo quanto fib(50) ! Tuttavia, si sta facendo un sacco di lavoro non necessario. fib(50) chiamerà fib(49) e fib(48) , ma poi entrambi finiranno per chiamare fib(47) , anche se il valore è lo stesso. Infatti, fib(47) sarà calcolato tre volte: da una chiamata diretta da fib(49) , da una chiamata diretta da fib(48) , e anche da una chiamata diretta da un'altra fib(48) , quella che era generato dal calcolo di fib(49) ... Quindi vedete, abbiamo sottoproblemi sovrapposti .

    Ottime notizie: non è necessario calcolare lo stesso valore molte volte. Una volta eseguito il calcolo una volta, memorizza il risultato nella cache e la volta successiva utilizza il valore memorizzato nella cache! Questa è l'essenza della programmazione dynamic. Puoi chiamarlo "top-down", "memoization" o qualsiasi altra cosa tu voglia. Questo approccio è molto intuitivo e molto facile da implementare. Basta scrivere prima una soluzione ricorsiva, testarla su piccoli test, aggiungere memoization (memorizzazione nella cache di valori già calcolati) e --- bingo! --- hai fatto.

    Di solito è anche ansible scrivere un programma iterativo equivalente che funzioni dal basso verso l'alto, senza ricorsione. In questo caso, questo sarebbe l'approccio più naturale: loop da 1 a 50, calcolando tutti i numeri di Fibonacci mentre si va.

     fib[0] = 0 fib[1] = 1 for i in range(48): fib[i+2] = fib[i] + fib[i+1] 

    In qualsiasi scenario interessante, la soluzione bottom-up è solitamente più difficile da comprendere. Tuttavia, una volta compreso, di solito ottieni un'immagine molto più chiara di come funziona l'algoritmo. In pratica, quando si risolvono problemi non banali, raccomando innanzitutto di scrivere l'approccio top-down e testarlo su piccoli esempi. Quindi scrivi la soluzione dal basso e confronta i due per assicurarti di ottenere la stessa cosa. Idealmente, confronta automaticamente le due soluzioni. Scrivi una piccola routine che genera molti test, idealmente - tutti piccoli test fino a determinate dimensioni --- e convalida che entrambe le soluzioni danno lo stesso risultato. Successivamente, utilizza la soluzione bottom-up in produzione, ma mantieni il codice top-bottom, commentato. Ciò renderà più semplice per gli altri sviluppatori capire che cosa stai facendo: il codice bottom-up può essere abbastanza incomprensibile, persino tu lo hai scritto e anche se sai esattamente cosa stai facendo.

    In molte applicazioni l'approccio bottom-up è leggermente più veloce a causa del sovraccarico delle chiamate ricorsive. Anche l'overflow dello stack può essere un problema in alcuni problemi e si noti che questo può dipendere molto dai dati di input. In alcuni casi potresti non essere in grado di scrivere un test che provoca un overflow dello stack se non capisci abbastanza bene la programmazione dynamic, ma un giorno potrebbe accadere ancora.

    Ora, ci sono problemi in cui l'approccio top-down è l'unica soluzione fattibile perché lo spazio dei problemi è così grande che non è ansible risolvere tutti i sottoproblemi. Tuttavia, il "caching" funziona ancora in un tempo ragionevole perché l'input richiede solo una frazione dei sottoproblemi da risolvere --- ma è troppo difficile definire esplicitamente quali sottoproblemi è necessario risolvere e quindi scrivere un bottom- soluzione. D'altra parte, ci sono situazioni in cui sai che dovrai risolvere tutti i sottoproblemi. In questo caso vai avanti e usa il bottom-up.

    Personalmente utilizzerei l'alto-basso per l'ottimizzazione del paragrafo, ovvero il problema dell'ottimizzazione del wrap di Word (consulta gli algoritmi di interruzione di riga di Knuth-Plasm, almeno TeX lo usa, e alcuni software di Adobe Systems usano un approccio simile). Vorrei usare bottom-up per la trasformazione di Fourier veloce .

    Prendiamo come esempio le serie Fibonacci

     1,1,2,3,5,8,13,21.... first number: 1 Second number: 1 Third Number: 2 

    Un altro modo per dirlo,

     Bottom(first) number: 1 Top (Eighth) number on the given sequence: 21 

    Nel caso del primo cinque numero di fibonacci

     Bottom(first) number :1 Top (fifth) number: 5 

    Ora vediamo come esempio un algoritmo ricorsivo della serie Fibonacci

     public int rcursive(int n) { if ((n == 1) || (n == 2)) { return 1; } else { return rcursive(n - 1) + rcursive(n - 2); } } 

    Ora se eseguiamo questo programma con i seguenti comandi

     rcursive(5); 

    se osserviamo da vicino l’algoritmo, per generare il quinto numero è necessario il 3 ° e il 4 ° numero. Quindi la mia ricorsione inizia effettivamente dalla parte superiore (5) e poi arriva fino ai numeri inferiore / inferiore. Questo approccio è in realtà un approccio dall’alto verso il basso.

    Per evitare di eseguire lo stesso calcolo più volte, utilizziamo le tecniche di programmazione dynamic. Memorizziamo il valore calcolato in precedenza e lo riutilizziamo. Questa tecnica è chiamata memoization. Ci sono altre cose nella programmazione dynamic oltre alla memorizzazione che non è necessaria per discutere del problema corrente.

    Dall’alto al basso

    Consente di riscrivere il nostro algoritmo originale e aggiungere tecniche memorizzate.

     public int memoized(int n, int[] memo) { if (n <= 2) { return 1; } else if (memo[n] != -1) { return memo[n]; } else { memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo); } return memo[n]; } 

    E eseguiamo questo metodo come seguendo

      int n = 5; int[] memo = new int[n + 1]; Arrays.fill(memo, -1); memoized(n, memo); 

    Questa soluzione è ancora dall'alto in basso mentre l'algoritmo parte dal valore più alto e passa in fondo ad ogni passaggio per ottenere il nostro valore più alto.

    Dal basso verso l'alto

    Ma la domanda è, possiamo iniziare dal basso, come dal primo numero di Fibonacci, poi proseguire fino a salire. Lo riscriviamo usando queste tecniche,

     public int dp(int n) { int[] output = new int[n + 1]; output[1] = 1; output[2] = 1; for (int i = 3; i <= n; i++) { output[i] = output[i - 1] + output[i - 2]; } return output[n]; } 

    Ora, se esaminiamo questo algoritmo, in realtà partiamo da valori più bassi, quindi passiamo all'inizio. Se ho bisogno del 5 ° numero di Fibonacci, in realtà sto calcolando il 1 °, poi il secondo e il terzo fino al 5 ° numero. Queste tecniche in realtà si chiamavano tecniche bottom-up.

    Gli ultimi due, gli algoritmi soddisfano pienamente i requisiti di programmazione dynamic. Ma uno è top-down e un altro è dal basso verso l'alto. Entrambi gli algoritmi hanno una complessità spaziale e temporale simile.

    La programmazione dynamic è spesso chiamata Memoization!

    1.Memoization è la tecnica top-down (inizia a risolvere il problema dato scomposizione) e la programmazione dynamic è una tecnica dal basso verso l’alto (inizia a risolvere dal sotto-problema banale, verso il problema dato)

    2.DP trova la soluzione partendo dal / i caso / i base / i e procede verso l’alto. DP risolve tutti i problemi secondari, perché lo fa dal basso verso l’alto

    A differenza di Memoization, che risolve solo i problemi secondari necessari

    1. La DP ha il potenziale per trasformare soluzioni di forza bruta esponenziale in algoritmi tempo-polinomiali.

    2. DP può essere molto più efficiente perché è iterativo

    Al contrario, Memoization deve pagare il sovraccarico (spesso significativo) dovuto alla ricorsione.

    Per essere più semplice, Memoization utilizza l’approccio top-down per risolvere il problema, ovvero inizia con il problema principale (principale), quindi lo suddivide in sotto-problemi e risolve allo stesso modo questi sotto-problemi. In questo approccio lo stesso sotto-problema può verificarsi più volte e consumare più cicli della CPU, quindi aumentare la complessità del tempo. Mentre nella programmazione dynamic, lo stesso problema secondario non verrà risolto più volte, ma il risultato precedente verrà utilizzato per ottimizzare la soluzione.

    Il semplice approccio dall’alto verso il basso utilizza la ricorsione per richiamare più volte i problemi sub
    dove come approccio dal basso usare il singolo senza chiamare nessuno e quindi è più efficiente.

    Di seguito è riportata la soluzione basata su DP per il problema di modifica della distanza, che è dall’alto in basso. Spero che aiuterà anche a capire il mondo della programmazione dynamic:

     public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle. int m = word2.length(); int n = word1.length(); if(m == 0) // Cannot miss the corner cases ! return n; if(n == 0) return m; int[][] DP = new int[n + 1][m + 1]; for(int j =1 ; j <= m; j++) { DP[0][j] = j; } for(int i =1 ; i <= n; i++) { DP[i][0] = i; } for(int i =1 ; i <= n; i++) { for(int j =1 ; j <= m; j++) { if(word1.charAt(i - 1) == word2.charAt(j - 1)) DP[i][j] = DP[i-1][j-1]; else DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this. } } return DP[n][m]; } 

    Puoi pensare alla sua implementazione ricorsiva a casa tua. È abbastanza buono e impegnativo se non hai ancora risolto qualcosa del genere.