PROGRAMMAZIONE DINAMICA: CARATTERISTICHE, ESEMPIO, VANTAGGI, SVANTAGGI - TECNOLOGIA - 2024

La programmazione dinamica è un algoritmo modello che risolve un problema complesso suddividendolo in sottoproblemi, memorizzandone i risultati per evitare di dover ricalcolare i risultati.

Questa pianificazione viene utilizzata quando si hanno problemi che possono essere suddivisi in sottoproblemi simili, in modo che i loro risultati possano essere riutilizzati. Per la maggior parte, questa pianificazione viene utilizzata per l'ottimizzazione.

Programmazione dinamica. Sottoproblemi sovrapposti nella sequenza di Fibonacci. Fonte: Wikimedia commons, en: User: Dcoatzee, tracciato da User: Stannered / Public domain

Prima di risolvere il sottoproblema disponibile, l'algoritmo dinamico tenterà di esaminare i risultati dei sottoproblemi precedentemente risolti. Le soluzioni ai sottoproblemi vengono combinate per ottenere la soluzione migliore.

Invece di calcolare ripetutamente lo stesso sottoproblema, puoi memorizzare la tua soluzione in un po 'di memoria, quando incontri per la prima volta questo sottoproblema. Quando compare di nuovo durante la soluzione di un altro sottoproblema, verrà presa la soluzione già archiviata in memoria.

Questa è un'idea meravigliosa per fissare il tempo di memoria, in cui l'utilizzo di spazio aggiuntivo può migliorare il tempo necessario per trovare una soluzione.

Caratteristiche della programmazione dinamica

Le seguenti caratteristiche essenziali sono ciò con cui devi avere un problema prima di poter applicare la programmazione dinamica:

Sottostruttura ottimale

Questa caratteristica esprime che un problema di ottimizzazione può essere risolto combinando le soluzioni ottimali dei problemi secondari che lo compongono. Queste sottostrutture ottimali sono descritte dalla ricorsione.

Ad esempio, in un grafico verrà presentata una sottostruttura ottimale nel percorso più breve r che va da un vertice s ad un vertice t:

Cioè, in questo percorso più breve r può essere preso qualsiasi vertice intermedio i. Se r è veramente la rotta più breve, allora può essere divisa nelle subroutes r1 (da s a i) e r2 (da i a t), in modo tale che queste siano a loro volta le rotte più brevi tra i vertici corrispondenti.

Pertanto, per trovare i percorsi più brevi, la soluzione può essere facilmente formulata in modo ricorsivo, che è ciò che fa l'algoritmo di Floyd-Warshall.

Sottoproblemi sovrapposti

Lo spazio del sottoproblema deve essere piccolo. Cioè, qualsiasi algoritmo ricorsivo che risolva un problema dovrà risolvere gli stessi sottoproblemi più e più volte, invece di generare nuovi sottoproblemi.

Ad esempio, per generare la serie di Fibonacci possiamo considerare questa formulazione ricorsiva: Fn = F (n - 1) + F (n - 2), prendendo come caso base che F1 = F2 = 1. Avremo quindi: F33 = F32 + F31 e F32 = F31 + F30.

Come puoi vedere, F31 viene risolto nei sottoalberi ricorsivi sia di F33 che di F32. Sebbene il numero totale di sottoproblemi sia davvero piccolo, se adotti una soluzione ricorsiva come questa finirai per risolvere gli stessi problemi più e più volte.

Questo viene preso in considerazione dalla programmazione dinamica, quindi risolve ogni sottoproblema solo una volta. Ciò può essere ottenuto in due modi:

Approccio dall 'alto verso il basso

Se la soluzione a qualsiasi problema può essere formulata ricorsivamente utilizzando la soluzione dei suoi sottoproblemi e se questi sottoproblemi si sovrappongono, allora le soluzioni ai sottoproblemi possono essere facilmente memorizzate o archiviate in una tabella.

Ogni volta che viene cercata una nuova soluzione di sottoproblemi, la tabella verrà controllata per vedere se è stata risolta in precedenza. Nel caso in cui venga memorizzata una soluzione, verrà utilizzata invece di calcolarla di nuovo. Altrimenti, il sottoproblema verrà risolto, memorizzando la soluzione nella tabella.

Approccio dal basso verso l'alto

Dopo che la soluzione di un problema è stata formulata ricorsivamente in termini di sottoproblemi, si può tentare di riformulare il problema in modo ascendente: in primo luogo, proveremo a risolvere i sottoproblemi e useremo le loro soluzioni per arrivare a soluzioni ai sottoproblemi più grandi.

Questo viene generalmente fatto anche in forma tabellare, generando in modo iterativo soluzioni a sottoproblemi sempre più grandi utilizzando soluzioni a sottoproblemi più piccoli. Ad esempio, se i valori di F31 e F30 sono già noti, il valore di F32 può essere calcolato direttamente.

Confronto con altre tecniche

Una caratteristica significativa di un problema che può essere risolto con la programmazione dinamica è che dovrebbe avere sottoproblemi che si sovrappongono. Questo è ciò che distingue la programmazione dinamica dalla tecnica divide et impera, dove non è necessario memorizzare i valori più semplici.

È simile alla ricorsione, poiché nel calcolo dei casi base, il valore finale può essere determinato induttivamente. Questo approccio dal basso verso l'alto funziona bene quando un nuovo valore dipende solo da valori calcolati in precedenza.

Esempio

Passi minimi per raggiungere 1

Per qualsiasi numero intero positivo "e" è possibile eseguire uno qualsiasi dei tre passaggi seguenti.

- Sottrai 1 dal numero. (e = e-1).

- Se è divisibile per 2, è diviso per 2 (se e% 2 == 0, allora e = e / 2).

- Se è divisibile per 3, è diviso per 3 (se e% 3 == 0, allora e = e / 3).

In base ai passaggi precedenti, è necessario trovare il numero minimo di questi passaggi per portare e a 1. Ad esempio:

- Se e = 1, risultato: 0.

- Se e = 4, risultato: 2 (4/2 = 2/2 = 1).

- Quando e = 7, risultato: 3 (7-1 = 6/3 = 2/2 = 1).

Messa a fuoco

Si potrebbe pensare di scegliere sempre il passo che fa n il più basso possibile e continuare così, fino a raggiungere 1. Tuttavia, si può vedere che questa strategia qui non funziona.

Ad esempio, se e = 10, i passaggi sarebbero: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 passaggi). Tuttavia, la forma ottimale è: 10-1 = 9/3 = 3/3 = 1 (3 passi). Pertanto, è necessario provare tutti i passaggi possibili per ogni valore di n trovato, scegliendo il numero minimo di queste possibilità.

Tutto inizia con la ricorsione: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} se e> 1, prendendo come caso base: F (1) = 0. Avendo l'equazione di ricorrenza, puoi iniziare a codificare la ricorsione.

Tuttavia, si può vedere che ha sottoproblemi sovrapposti. Inoltre, la soluzione ottimale per un dato input dipende dalla soluzione ottimale dei suoi sottoproblemi.

Come nella memorizzazione, dove vengono memorizzate le soluzioni dei sottoproblemi risolti per un uso successivo. O come nella programmazione dinamica, inizi dal basso, procedendo fino alla e data. Quindi entrambi i codici:

Memorizzazione

Programmazione dinamica dal basso verso l'alto

Vantaggio

Uno dei principali vantaggi dell'utilizzo della programmazione dinamica è che velocizza l'elaborazione, poiché vengono utilizzati riferimenti precedentemente calcolati. Trattandosi di una tecnica di programmazione ricorsiva, riduce le righe di codice nel programma.

Algoritmi voraci vs programmazione dinamica

Gli algoritmi avidi sono simili alla programmazione dinamica in quanto sono entrambi strumenti per l'ottimizzazione. Tuttavia, l'algoritmo avido cerca una soluzione ottimale in ogni fase locale. Cioè, cerca una scelta avida nella speranza di trovare un ottimo globale.

Pertanto, algoritmi avidi possono fare un'ipotesi che sembra ottimale al momento, ma diventa costosa in futuro e non garantisce un ottimale globale.

D'altra parte, la programmazione dinamica trova la soluzione ottimale per i sottoproblemi e quindi effettua una scelta informata combinando i risultati di quei sottoproblemi per trovare effettivamente la soluzione ottimale.

svantaggi

- È necessaria molta memoria per memorizzare il risultato calcolato di ogni sottoproblema, senza poter garantire che il valore memorizzato verrà utilizzato o meno.

- Molte volte, il valore di output viene memorizzato senza mai essere utilizzato nei seguenti sottoproblemi durante l'esecuzione. Ciò porta a un utilizzo della memoria non necessario.

- Nella programmazione dinamica, le funzioni vengono chiamate in modo ricorsivo. Ciò mantiene la memoria dello stack in costante aumento.

Ricorsione vs programmazione dinamica

Se hai una memoria limitata per eseguire il codice e la velocità di elaborazione non è un problema, puoi usare la ricorsione. Ad esempio, se stai sviluppando un'applicazione mobile, la memoria è molto limitata per eseguire l'applicazione.

Se si desidera che il programma venga eseguito più velocemente e non abbia limitazioni di memoria, è preferibile utilizzare la programmazione dinamica.

applicazioni

La programmazione dinamica è un metodo efficace per risolvere problemi che altrimenti potrebbero sembrare estremamente difficili da risolvere in un ragionevole lasso di tempo.

Gli algoritmi basati sul paradigma di programmazione dinamica sono utilizzati in molte aree della scienza, inclusi molti esempi di intelligenza artificiale, dalla risoluzione dei problemi di pianificazione al riconoscimento vocale.

Algoritmi basati sulla programmazione dinamica

La programmazione dinamica è abbastanza efficace e funziona molto bene per un'ampia gamma di problemi. Molti algoritmi possono essere visti come applicazioni avide di algoritmi, come:

- Serie di numeri di Fibonacci.

- Torri di Hanoi.

- Tutte le coppie di percorsi più brevi attraverso Floyd-Warshall.

- Problema con lo zaino.

- Pianificazione del progetto.

- La via più breve attraverso Dijkstra.

- Controllo del volo e controllo della robotica.

- Problemi di ottimizzazione matematica.

- Multiproprietà: pianifica il lavoro per massimizzare l'utilizzo della CPU.

Serie di numeri di Fibonacci

I numeri di Fibonacci sono i numeri che si trovano nella seguente sequenza: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ecc.

Nella terminologia matematica, la sequenza Fn dei numeri di Fibonacci è definita dalla formula di ricorrenza: F (n) = F (n -1) + F (n -2), dove F (0) = 0 e F ( 1) = 1.

Approccio dall 'alto verso il basso

In questo esempio, un array di ricerca con tutti i valori iniziali viene inizializzato con -1. Ogni volta che è necessaria la soluzione a un sottoproblema, questa matrice di ricerca verrà cercata per prima.

Se il valore calcolato è presente, verrà restituito quel valore. In caso contrario, il risultato verrà calcolato per essere memorizzato nella matrice di ricerca in modo che possa essere riutilizzato in seguito.

Approccio dal basso verso l'alto

In questo caso, per la stessa serie di Fibonacci, viene calcolato prima f (0), poi f (1), f (2), f (3) e così via. Pertanto, le soluzioni dei sottoproblemi vengono costruite dal basso verso l'alto.

Riferimenti

1. Vineet Choudhary (2020). Introduzione alla programmazione dinamica. Developer Insider Tratto da: developerinsider.co.
2. Alex Allain (2020). Programmazione dinamica in C ++. Programmazione C. Tratto da: cprogramming.com.
3. Dopo Academy (2020). Idea di programmazione dinamica. Tratto da: afteracademy.com.
4. Aniruddha Chaudhari (2019). Programmazione dinamica e ricorsione - Differenza, vantaggi con l'esempio. CSE Stack. Tratto da: csestack.org.
5. Code Chef (2020). Tutorial per la programmazione dinamica. Tratto da: codechef.com.
6. Programiz (2020). Programmazione dinamica. Tratto da: programiz.com.