Algoritmi - Programmazione Dinamica

Forum - Algoritmi - Programmazione Dinamica

tuttodiMC (Normal User)
Expert

Messaggi: 327
Iscritto: 29/10/2012

Postato alle 16:39
Mercoledì, 04/03/2015

Salve a tutti. Pochi giorni fa ho preso parte ad una delle lezioni preparatorie alla selezione regionale delle olimpiadi di informatica, organizzate dalla mia scuola in collaborazione col dipartimento di Informatica dell' università de L'Aquila.

Il professore quel giorno ha spiegato la programmazione dinamica per l'ottimizzazione di algoritmi ricorsivi. Non avendo capito immediatamente l'argomento trattato ho fatto qualche ricerca in internet dove veniva detto che questo tipo di programmazione si basa più sull'approccio bottom-up che sul top-down. Ho provato ad utilizzare questa tecnica di programmazione riuscendo a creare solo una versione quasi istantantea della funzione ricorsiva della successione di fibonacci Fn = F(n-1)+F(n-1).

Vorrei però capire meglio il funzionamento di questa tecnica perchè mi sarebbe molto utile per risolvere alcuni problemi di projecteuler.net. Qualcuno riesce a darmi una spiegazione semplice?

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 18:42
Mercoledì, 04/03/2015

Ciao!
Ti avverto fin da subito che di programmazione dinamica non me ne intendo gran che.
Tuttavia il concetto che stalla alle base è che se risolvo un sotto-problema conviene salvarlo in modo tale da averlo già risolto per il futuro.

Qui puoi trovare una pagina che avevo scritto tempo fa: http://xbarbox.pierotofy.it/zaino.html
Il problema dello zaino è un ottimo esempio un po' più avanzato di Fibonacci per capire bene la programmazione dinamica.

A proposito di project euler c'è un bellissimo esempio sulla congettura di collatz https://projecteuler.net/problem=14

Questo è un esempio valido per la programmazione dinamica in quanto un sotto problema può tornare utile a un problema di "livello superiore".
Infatti, se definisco collatz(n) come la lunghezza della sequenza di collatz a partire da n, posso definire il problema ricorsivamente in questo modo:

se n pari => collatz(n) = 1 + collatz(n/2)
se n dispari => collatz(n) = 1 + collatz(3*n + 1)
con caso base collatz(1) = 1

Per esempio collatz(16) è istantaneo da calcolare se conosco collatz(8) in quanto collatz(16) = 1 + collatz(8).
Quindi un metodo rapido consiste nel salvarti in un vettore tutti i risultati di collatz(i) in posizione i del vettore.

Spero di essere stato chiaro e di aiuto! In bocca al lupo per le olimpiadi! :k:

Ultima modifica effettuata da XBarboX il 04/03/2015 alle 18:43

dnha (Member)
Pro

Messaggi: 137
Iscritto: 24/07/2014

Postato alle 20:41
Mercoledì, 04/03/2015

Testo quotato

Postato originariamente da tuttodiMC:
Pochi giorni fa ho preso parte ad una delle lezioni preparatorie alla selezione regionale delle olimpiadi di informatica [...] Il professore quel giorno ha spiegato la programmazione dinamica per l'ottimizzazione di algoritmi ricorsivi.

E siamo in due

Quanto odio gli esercizi del tipo:

Codice sorgente - presumibilmente C++

#include <stdio.h>
 
int max(int a, int b) {
        if(a > b) return a;
        return b;
}
int f(int a, int b) {
        if (a == b) return b;
        if (a < 0) return -b; 
        return max(f(a-1, 2*b), f(a-1, 2*b+1));
}
void main() {
        printf("%d", f(8, 0));
}

Ultima modifica effettuata da dnha il 04/03/2015 alle 20:41

tuttodiMC (Normal User)
Expert

Messaggi: 327
Iscritto: 29/10/2012

Postato alle 13:30
Giovedì, 05/03/2015

Per quanto riguarda il problema 14 di projecteuler l'ho già debitamente risolto senza utilizzare la programmazione dinamica. Invece devo utilizzarla per risolvere il problema 15, https://projecteuler.net/problem=15, dato che ho ottenuto ricorsivamente la soluzione al problema verificando l'esempio riportato, tuttavia, la durata dell'esecuzione per la risoluzione del problema vero e proprio è veramente lunga.