Caratteristiche di programmazione dinamica, esempio, vantaggi, svantaggi

IL Programmazione dinamica È un modello di algoritmo che risolve un problema complesso dividendolo in sottoproblemi, memorizzando i loro risultati per evitare di dover calcolare tali risultati.

Questo programma viene utilizzato quando i problemi possono essere divisi in sottoproblemi simili, in modo che i loro risultati possano essere riutilizzati. Per la maggior parte, questo programma viene utilizzato per l'ottimizzazione.

Programmazione dinamica. Subproblemi sovrapposti nella successione di Fibonacci. Fonte: Wikimedia Commons, AT: Utente: Dcoatzee, tracciato dall'utente: Stannered / Public Domain

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

Invece di calcolare lo stesso subproblema ancora e ancora, la tua soluzione può essere memorizzata in qualche memoria, quando si incontra per la prima volta questo subproblema. Quando appare di nuovo durante la soluzione di un altro sottoproblema, la soluzione già memorizzata in memoria verrà presa.

Questa è un'idea meravigliosa per correggere il tempo con la memoria, in cui quando si utilizza uno spazio aggiuntivo è possibile migliorare il tempo necessario per trovare una soluzione.

[TOC]

Caratteristiche della programmazione dinamica

Le seguenti caratteristiche essenziali sono quelle che un problema può essere applicato per 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 una sottostruttura ottimale verrà presentata sul percorso più breve che va da un vertice a un vertice t:

Cioè, su questo percorso più breve r puoi prendere qualsiasi vertice intermedio I. Se R è davvero il percorso più breve, allora può essere diviso in Subrutas R1 (da S a I) e R2 (da I a T), in modo che questi siano a loro volta i percorsi più brevi tra i vertici corrispondenti.

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

Sottoproblemi sovrapposti

Lo spazio dei sottoproblemi deve essere piccolo. Cioè, qualsiasi algoritmo ricorsivo che risolve un problema deve risolvere più volte gli stessi sottoproblemi, invece di generare nuovi sottoproblemi.

Ad esempio, per generare la serie Fibonacci, questa formulazione ricorsiva può essere considerata: Fn = F (N-1) + F (N-2), prendendo come caso base che f1 = f2 = 1. Quindi dovrai: F33 = F32 + F31 e F32 = F31 + F30.

Come si può vedere, F31 viene risolto nei sottomesoni ricorsivi di F33 e F32. Sebbene il numero totale di sottoproblemi sia davvero piccolo, se viene adottata una soluzione ricorsiva in quanto ciò finirà per risolvere gli stessi problemi ancora e ancora.

Può servirti: i 7 componenti di un sistema informativo

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

Approccio superiore

Se la soluzione a qualsiasi problema può essere formulata in modo ricorsivo usando la soluzione dei loro sottoproblemi e se questi sottoproblemi si sovrappongono, le soluzioni ai sottoproblemi possono essere facilmente memorizzate o memorizzate in una tabella in una tabella.

Ogni volta che viene ricercata la soluzione di un nuovo sottoproblema, verrà rivista nella tabella se precedentemente risolta. Nel caso in cui una soluzione venga memorizzata, verrà utilizzata invece di calcolarla di nuovo. In caso contrario, il subproblema verrà risolto, immagazzinando la soluzione nella tabella.

Approccio ascendente

Dopo che la soluzione di un problema è formulata in modo ricorsivo in termini di sottoproblemi, il problema può essere tentato in un verso l'alto: prima cercheranno di risolvere i sottoproblemi e utilizzare le loro soluzioni per raggiungere le soluzioni ai più grandi sottoproblemi.

Questo è di solito fatto anche sotto forma di una tabella, generando soluzioni iterative a sottoproblemi sempre più grandi utilizzando soluzioni a piccoli sottoproblemi. 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 appartenenza significativa di un problema che può essere risolto mediante programmazione dinamica è che dovrebbe avere sottovalutazioni sovrapposte. Questo è ciò che distingue la programmazione dinamica della tecnica di divisione e conquista, dove non è necessario archiviare i valori più semplici.

È simile alla ricorsione, poiché calcolando i casi di base, il valore finale può essere determinato induttivamente. Questo approccio ascendente funziona bene quando un nuovo valore dipende solo da valori precedentemente calcolati.

Esempio

Passaggi minimi per raggiungere 1

Per qualsiasi numero intero positivo "E" puoi eseguire uno 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).

Sulla base dei passaggi precedenti, è necessario trovare la quantità minima di questi passaggi da prendere e 1. Per 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).

Approccio

Potresti sempre pensare di scegliere il passo che rende N il più basso possibile e continuare così, fino a quando non raggiunge 1. Tuttavia, si può vedere che questa strategia non funziona qui.

Può servirti: software commerciale

Ad esempio, se E = 10, i passaggi sarebbero: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 passaggi). Tuttavia, il modo ottimale è: 10-1 = 9/3 = 3/3 = 1 (3 passaggi). Pertanto, tutti i passaggi possibili che possono essere effettuati per ciascun valore di N devono essere dimostrati, scegliendo l'importo minimo di tali possibilità.

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

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

Come nella memorizzazione, dove le soluzioni dei sottoproblemi che vengono risolti vengono conservati per usarle in seguito. O come nella programmazione dinamica, inizia dal basso, avanzando al dato E. Successivamente, entrambi i codici:

Memorizzazione

Programmazione verso l'alto dinamica

Vantaggi

Uno dei principali vantaggi dell'utilizzo della programmazione dinamica è che accelera l'elaborazione, poiché vengono utilizzati riferimenti precedentemente calcolati. Come è una tecnica di programmazione ricorsiva, riduce le linee del codice del programma.

Vorace AlgoritMOS vs Programmazione dinamica

Gli algoritmi voraci sono simili alla programmazione dinamica nel senso che entrambi sono strumenti per l'ottimizzazione. Tuttavia, l'algoritmo Voraz cerca una soluzione ottimale in ogni passaggio locale. Cioè, cerca una scelta avida con la speranza di trovare un ottimale globale.

Pertanto, gli algoritmi voraci possono prestare un presupposto che sembra ottimale in quel momento, ma ciò diventa costoso in futuro e non garantisce un ottimale globale.

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

Svantaggi

- È necessaria molta memoria per archiviare il risultato calcolato di ciascun sottoproblema, senza essere in grado di garantire che il valore memorizzato venga utilizzato o meno.

- Molte volte, il valore di output viene memorizzato senza mai essere utilizzato nei seguenti sottoproblemi durante l'esecuzione. Questo porta a un uso inutile della memoria.

- Nella programmazione dinamica le funzioni sono chiamate ricorsivamente. Questo fa sì che la memoria della batteria rimanga in costante aumento.

Ricursività vs programmazione dinamica

Se hai una memoria limitata per eseguire il codice e la velocità di elaborazione non è preoccupante, è possibile utilizzare la ricorsività. Ad esempio, se viene sviluppata un'applicazione mobile, la memoria è molto limitata per eseguire l'applicazione.

Può servirti: dispositivi misti: caratteristiche ed esempi

Se si desidera che il programma sia eseguito più velocemente e non ci sono restrizioni di memoria, è preferibile utilizzare la programmazione dinamica.

Applicazioni

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

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

Algoritmi di programmazione dinamica

La programmazione dinamica è piuttosto efficace e serve molto bene per una vasta gamma di problemi. Molti algoritmi possono essere visti come applicazioni di voraci algoritmi, come:

- Serie di numeri Fibonacci.

- Hanoi Towers.

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

- Zaino.

- Programmazione del progetto.

- Il percorso più breve di Dijkstra.

- Controllo e controllo del volo robotico.

- Problemi di ottimizzazione matematica.

- Tempo condiviso: programma il lavoro per massimizzare l'uso della CPU.

Serie di numeri Fibonacci

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

In terminologia matematica, la successione 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 = 1.

Approccio superiore

In questo esempio, una matrice di ricerca con tutti i valori iniziali viene inizializzata con -1. Ogni volta che è necessaria la soluzione a un sottoproblema, verrà prima ricercata in questa matrice di ricerca.

Se c'è il valore calcolato, quel valore verrà restituito. Altrimenti, il risultato verrà calcolato per archiviarlo nella matrice di ricerca e quindi essere in grado di riutilizzarlo in seguito.

Approccio ascendente

In questo caso, per la stessa serie Fibonacci, F (0), quindi F (1), F (2), F (3) e così via viene calcolato prima. Pertanto, saranno costruite le soluzioni dei sottoproblemi dal fondo.

Riferimenti

1. Vineet Choudhary (2020). Introduzione alla programmazione dinamica. Insider non sviluppatore.Preso da: svilupperinsider.co.
2. Alex Allain (2020). Programmazione dinamica in C++. Programmazione C. Tratto da: cprogramming.com.
3. After Academy (2020). Idea di programmazione dinamica. Preso da: AfterAcademy.com.
4. Aniruddha Chaudhari (2019). Programmazione dinamica e ricorsione | Diverso. Stack CSE. Preso da: CSestack.org.
5. Code Chef (2020). Per tutorial di programmazione dinamica. Preso da: Codhef.com.
6. Programmiz (2020). Programmazione dinamica. Tratto da: Programmiz.com.