Programmazione Dinamica
Salve,
vorrei chiedere una mano. Tra tutte le tecniche di progettazione di algoritmi che ho potuto vedere ed usare, quella che mi crea più problemi è la Programmazione Dinamica.
Non riesco ad utilizzarla concreatemente nei problemi in cui la si può utilizzare.
Anche se un problema è simile ad uno già noto con soluzione, non riesco a redigere tutta la trafila di dimostrazioni, affermazioni, equazioni, che la PD necessita.
Quello che vorrei riuscire a fare con questo post con il vostro aiuto, è uno schema completo ma ad alto livello per poter applicare e capire la PD su di un problema.
La teoria la conosco, la pratica è di difficile utilizzo.
Essendo che i sotto-problemi cambiano sempre, ma sono simili vorrei generalizzare il tutto, perchè non trovo nulla di completo (solo pezzi di idee) che mi faccia capire davvero questa bella tecnica.
Tipo vorrei sapere cosa fate quando volete utilizzare la PD, quali sono i vostri passaggi/immagini mentali che fate su questa tecnica?
Ringrazio molto chi aiuta
vorrei chiedere una mano. Tra tutte le tecniche di progettazione di algoritmi che ho potuto vedere ed usare, quella che mi crea più problemi è la Programmazione Dinamica.
Non riesco ad utilizzarla concreatemente nei problemi in cui la si può utilizzare.
Anche se un problema è simile ad uno già noto con soluzione, non riesco a redigere tutta la trafila di dimostrazioni, affermazioni, equazioni, che la PD necessita.
Quello che vorrei riuscire a fare con questo post con il vostro aiuto, è uno schema completo ma ad alto livello per poter applicare e capire la PD su di un problema.
La teoria la conosco, la pratica è di difficile utilizzo.
Essendo che i sotto-problemi cambiano sempre, ma sono simili vorrei generalizzare il tutto, perchè non trovo nulla di completo (solo pezzi di idee) che mi faccia capire davvero questa bella tecnica.
Tipo vorrei sapere cosa fate quando volete utilizzare la PD, quali sono i vostri passaggi/immagini mentali che fate su questa tecnica?
Ringrazio molto chi aiuta
Risposte
Quanto è utile da 1 a 10 la PD?
Molti algoritmi di uso comune sono basati sulle idee della programmazione dinamica. Mi sembra quindi esagerato affermare che al di fuori dell'università la evitino. Si cerca però normalmente di ricorrere a soluzioni già pronte ed è alla fine abbastanza raro dover risolvere un problema completamente da zero nella programmazione di tutti i giorni. E per la maggior parte del codice non è neanche necessario ricorrere ad una soluzione ottimale. Ci sono quindi poche occasioni per affrontare un esercizio come quello richiesto negli esami. La parte di dimostrazione formale è sicuramente quella che più di ogni altro viene messa da parte.
Sfortunatamente non esiste un algoritmo per risolvere problemi (usando la programmazione dinamica o meno) e si può fare ricorso più che altro all'esperienza e a metodi euristici. Con un esempio sarebbe forse più facile cercare di descrivere il tipo di ragionamento usato per arrivare alla soluzione.
Essendo che i sotto-problemi cambiano sempre, ma sono simili vorrei generalizzare il tutto, perchè non trovo nulla di completo (solo pezzi di idee) che mi faccia capire davvero questa bella tecnica.
Sfortunatamente non esiste un algoritmo per risolvere problemi (usando la programmazione dinamica o meno) e si può fare ricorso più che altro all'esperienza e a metodi euristici. Con un esempio sarebbe forse più facile cercare di descrivere il tipo di ragionamento usato per arrivare alla soluzione.
Dynamic programming is easy to understand but hard to master.
Concordo con quanto detto da apatriarca: lavorare in generale non credo sia possibile, meglio affrontare un problema e caso mai vediamo di poter astrarre qualcosa dalla risoluzione dello stesso. Comunque sono tutt'altro che un esperto in programmazione dinamica, quindi il mio contributo alla discussione si fermerà probabilmente alla precedente citazione.
Concordo con quanto detto da apatriarca: lavorare in generale non credo sia possibile, meglio affrontare un problema e caso mai vediamo di poter astrarre qualcosa dalla risoluzione dello stesso. Comunque sono tutt'altro che un esperto in programmazione dinamica, quindi il mio contributo alla discussione si fermerà probabilmente alla precedente citazione.
Vi ringrazio delle risposte
L'avrò letta tante di quelle volte questa frase, mentre cercavo qualche buona soluzione
Si quando ho scritto che viene "evitata" non mi venivano in mente altri sinonimi...ma alla fine essendo uno studente il mondo enterprise lo conosco solo per "voci di corridoio".
Ma prendo come buono di cercare un problema, e cercare, insieme, di spiegare (spiegarmi) come affrontare e scarnare fino al midollo il problema con l'approccio dinamico. Ne ho in mente uno che mi aveva fatto pensare ed ho messo da parte, lo posterò in seguito, intanto grazie della disponibilità
Dynamic programming is easy to understand but hard to master.
L'avrò letta tante di quelle volte questa frase, mentre cercavo qualche buona soluzione
Si quando ho scritto che viene "evitata" non mi venivano in mente altri sinonimi...ma alla fine essendo uno studente il mondo enterprise lo conosco solo per "voci di corridoio".
Ma prendo come buono di cercare un problema, e cercare, insieme, di spiegare (spiegarmi) come affrontare e scarnare fino al midollo il problema con l'approccio dinamico. Ne ho in mente uno che mi aveva fatto pensare ed ho messo da parte, lo posterò in seguito, intanto grazie della disponibilità
"ham_burst":
Vi ringrazio delle risposte
Dynamic programming is easy to understand but hard to master.
L'avrò letta tante di quelle volte questa frase, mentre cercavo qualche buona soluzione
Si quando ho scritto che viene "evitata" non mi venivano in mente altri sinonimi...ma alla fine essendo uno studente il mondo enterprise lo conosco solo per "voci di corridoio".
Ma prendo come buono di cercare un problema, e cercare, insieme, di spiegare (spiegarmi) come affrontare e scarnare fino al midollo il problema con l'approccio dinamico. Ne ho in mente uno che mi aveva fatto pensare ed ho messo da parte, lo posterò in seguito, intanto grazie della disponibilità
Quale corso stai facendo?
Ecco un problema preso da un libro:
Quello che vorrei sapere è, appena leggete il problema, sapendo che l'approccio di risoluzione è quello dinamico, come ragionate, come dividete le idee, fate schemi, disegni, ecc... cioè tutta la concatenazione di ragionamenti che fate per arrivare ad un formalismo corretto.
Ringrazio per la pazienza e la disponibilità
@xls: se è per la PD ho giò seguito il corso in cui viene trattata. Ma che spiegava cosa è la PD e qualche esempio, che non permette di capire in fondo come usarla.
Stringhe primitive
Dato un insieme di $m$ stringhe dette primitive ed una stringa $X = x_1...x_n$, si vuole determinare se $X$ è ottenibile dalla concatenazione di stringhe primitive.
Ad esempio: dato l’insieme di primitive ${01, 10, 011, 101}$, per la stringa $X = 0111010101$ la risposta è sì (due possibili soluzioni sono $011-10-10-101$ e $011-101-01-01$) mentre per la stringa $X = 0110001$ la risposta è no.
Quello che vorrei sapere è, appena leggete il problema, sapendo che l'approccio di risoluzione è quello dinamico, come ragionate, come dividete le idee, fate schemi, disegni, ecc... cioè tutta la concatenazione di ragionamenti che fate per arrivare ad un formalismo corretto.
Ringrazio per la pazienza e la disponibilità
@xls: se è per la PD ho giò seguito il corso in cui viene trattata. Ma che spiegava cosa è la PD e qualche esempio, che non permette di capire in fondo come usarla.
Sapendo che un certo problema può essere risolto utilizzando la programmazione dinamica, inizio a chiedermi quali possano essere i possibili sotto-problemi da sfruttare. Seguono quindi le seguenti osservazioni.
1. In input ho una successione di simboli. I sotto-problemi lavoreranno quindi probabilmente su una sua qualche sotto-successione.
2. Il problema richiede di stabilire se la successione rispetti una qualche proprietà per cui anche i sotto-problemi saranno probabilmente dello stesso tipo.
3. Una stringa è data dalla concatenazione di stringhe primitive se e solo se è possibile suddividere la stringa in sottostringhe disgiunte tali che ogni stringa è una stringa positiva. In particolare ogni stringa di questo tipo dovrà iniziare o finire con una stringa primitiva e il resto della stringa potrà essere ottenuto attraverso una concatenazione di stringhe primitive.
Ho quindi ottenuto una proprietà da sfruttare: $P(X)$ è vero se almeno uno degli elementi dell'insieme ${P(Y) : X = PY$ dove $P$ è una stringa primitiva$}$ è vero. La dimostrazione non dovrebbe essere particolarmente difficile. Una possibile implementazione in haskell:
Ho mostrato il codice in questo linguaggio perché penso che imparare a scrivere in linguaggi funzionali come questo potrebbe aiutare nella risoluzione di problemi di questo tipo. Si è in effetti costretti ad usare una qualche forma di ricorsione.
1. In input ho una successione di simboli. I sotto-problemi lavoreranno quindi probabilmente su una sua qualche sotto-successione.
2. Il problema richiede di stabilire se la successione rispetti una qualche proprietà per cui anche i sotto-problemi saranno probabilmente dello stesso tipo.
3. Una stringa è data dalla concatenazione di stringhe primitive se e solo se è possibile suddividere la stringa in sottostringhe disgiunte tali che ogni stringa è una stringa positiva. In particolare ogni stringa di questo tipo dovrà iniziare o finire con una stringa primitiva e il resto della stringa potrà essere ottenuto attraverso una concatenazione di stringhe primitive.
Ho quindi ottenuto una proprietà da sfruttare: $P(X)$ è vero se almeno uno degli elementi dell'insieme ${P(Y) : X = PY$ dove $P$ è una stringa primitiva$}$ è vero. La dimostrazione non dovrebbe essere particolarmente difficile. Una possibile implementazione in haskell:
import Data.Maybe
import Data.List
isFromConcats :: Eq a => [[a]] -> [a] -> Bool
isFromConcats _ [] = True
isFromConcats ps xs = or (map (isFromConcats ps) suffixes)
where suffixes = catMaybes (map (\p-> stripPrefix p xs) ps)
main = do
print (isFromConcats ["01", "10", "011", "101"] "0111010101")
print (isFromConcats ["01", "10", "011", "101"] "0110001")
Ho mostrato il codice in questo linguaggio perché penso che imparare a scrivere in linguaggi funzionali come questo potrebbe aiutare nella risoluzione di problemi di questo tipo. Si è in effetti costretti ad usare una qualche forma di ricorsione.
ook, mi serviva proprio un ragionamento scritto a parole.
In base al problema ho visto che ci sono svariati modi per rappresentare i sotto-problemi e la dimostrazione formale. Quello delle stringhe ad esempio è differente da uno di ottimizzazione.
Se posso, perciò, vorrei chiederti se puoi abbozzare una soluzione anche di un problema di ottimizzazione. Questo perchè per generalizzare ho bisogno di vederne un altro scritto nel modo sopra.
Vorrei vedere come ragioni quando hai a che fare con sotto-problemi che variano in base ad un indice, classico della PD, e che c'è da massimizzare un valore.
Questo è un altro problema:
Mi sembra di averlo risolto con scelta greedy durante il corso, ma l'approccio PD è possibile.
La parte che vorrei vedere è come inizi il formalismo (sia formalmente che discorsivamente) per la dimostrazione della sotto-struttura e come alla fine lo trasformi nell'equazione di ricorrenza del problema.
Fatto questo, sempre se hai (avete) voglia, penso di aver abbastanza materiale per ragionare.
Per il linguaggio funzionale, ti ringrazio, (io conosco O'Caml) mi hai fatto pensare che ragionare con quella metodologia non è male.
Ma prima però bisogna trovare i sotto-problemi e la relazione che li lega, per poter scrivere la ricorsione corretta. (approccio top-down o bottom-up che sia).
Intanto ringrazio tantissimo per la disponibilità, mi servirà molto questo post
In base al problema ho visto che ci sono svariati modi per rappresentare i sotto-problemi e la dimostrazione formale. Quello delle stringhe ad esempio è differente da uno di ottimizzazione.
Se posso, perciò, vorrei chiederti se puoi abbozzare una soluzione anche di un problema di ottimizzazione. Questo perchè per generalizzare ho bisogno di vederne un altro scritto nel modo sopra.
Vorrei vedere come ragioni quando hai a che fare con sotto-problemi che variano in base ad un indice, classico della PD, e che c'è da massimizzare un valore.
Questo è un altro problema:
Siete a bordo di una modernissima auto elettrica su un’autostrada lunga $N$ km; prima che la vostra batteria si esaurisca (dopo $r$ km), dovete fermarvi in un’area di servizio e cambiarla con una nuova batteria.
Entrate in autostrada al km $0$ con la batteria carica, e dovete uscire al km $N$. Siano $D[1.....n]$ e $C[1....n]$ due vettori di interi, dove $D$ è la distanza dell’area di servizio $i$-esima dall’inizio dell’autostrada, e $C$ è il costo di una nuova batteria nell’area $i$. Progettate un algoritmo che minimizzi il costo totale del viaggio.
Mi sembra di averlo risolto con scelta greedy durante il corso, ma l'approccio PD è possibile.
La parte che vorrei vedere è come inizi il formalismo (sia formalmente che discorsivamente) per la dimostrazione della sotto-struttura e come alla fine lo trasformi nell'equazione di ricorrenza del problema.
Fatto questo, sempre se hai (avete) voglia, penso di aver abbastanza materiale per ragionare.
Per il linguaggio funzionale, ti ringrazio, (io conosco O'Caml) mi hai fatto pensare che ragionare con quella metodologia non è male.
Ma prima però bisogna trovare i sotto-problemi e la relazione che li lega, per poter scrivere la ricorsione corretta. (approccio top-down o bottom-up che sia).
Intanto ringrazio tantissimo per la disponibilità, mi servirà molto questo post
Non essendomi mai realmente occupato in ambito universitario di problemi di ottimizzazione non sono molto abile nella risoluzione di questo genere di problema. Intuitivamente credo che qualsiasi soluzione consideri la sottosuccessione $D[1..i]$ e trovi una qualche soluzione ottimale al problema per questa successione e che venga poi utilizzata per procedere oltre. Ho comunque l'impressione che fosse già uscito un problema simile. Dopo averci pensato un po' credo che tratterei il problema come la ricerca di un cammino minimo su un grafo i cui nodi sono le stazioni di servizio e gli archi i percorsi possibili alle successive stazioni di servizio senza aver bisogno di cambiare la batteria. Usando Dijkstra si arriva ad esempio alla soluzione cercata. Il mio è comunque un metodo di risoluzione un po' pragmatico che mi evita l'onere di una dimostrazione.
Il problema lo ho preso da un cumulo di problemi di ottimizzazione, il mio era un esempio non serve una soluzione.
Ma mi hai chiarito alcuni punti oscuri nel ragionamento, perciò grazie
Bhe il tuo metodo, anche se non usa programmazione dinamica, penso sia strausato in ogni ambito. Cioè ridursi ad un problema conosciuto e in cui è già dimostrato ogni teorema, e risolverlo con un algoritmo.
Tipo i problemi di flusso o programmazione lineare
Ma mi hai chiarito alcuni punti oscuri nel ragionamento, perciò grazie
Bhe il tuo metodo, anche se non usa programmazione dinamica, penso sia strausato in ogni ambito. Cioè ridursi ad un problema conosciuto e in cui è già dimostrato ogni teorema, e risolverlo con un algoritmo.
Tipo i problemi di flusso o programmazione lineare
Mi ero però fermato fin troppo presto nella soluzione del problema che in realtà è abbastanza semplice. L'idea dei grafi mi è venuta in mente pensando che dovevo trovare il percorso che minimizzasse una certa quantità. Il passaggio da questo all'idea di avere un grafo e di dover trovare il percorso di lunghezza minima non era poi molto lontano. Ma Dijkstra è forse esagerato per questo problema. Il grafo è infatti abbastanza semplice. Ogni arco entrante in un certo nodo $i$, avrà ad esempio sempre peso $C_i$. Il percorso più corto da un nodo $j$ al nodo $i$ sarà quindi sempre quello diretto. Per questo motivo il percorso al nodo $i$, $P_i = i + \min \{ P_j : D_i - D_j < r, i > j \}$. $P_N$ sarà a questo punto la soluzione finale.
Vedendo questo post passato, dove hanno scritto dei miei miti 
, volevo provare a fare una versione con memoization con la variante che, anziché dire true o false, dia proprio il numero di modi che risultano dalla concatenazione.
Ossia se ho primitive tipo:
AB BA ABB BAB
Poi provo la stringa casuale:
ABBBABABAB
Dovrei ottenere 3 modi
(ossia tre modi: ABB − BA − BA − BAB, oppure ABB − BA − BAB − AB e ABB − BAB − AB − AB )
Sempre con le stesse primitive di sopra, provando invece:
ABBAAAB
Ottengo 0 modi.
Il mio codice non è efficente perché lento LENTO LENTO
Chiedo il vostro aiuto... (Il problema chiaramente è dato dalla ricorsione penso)
Se le stringhe (di numero) aumentano diventa un codice molto scarso
, volevo provare a fare una versione con memoization con la variante che, anziché dire true o false, dia proprio il numero di modi che risultano dalla concatenazione.Ossia se ho primitive tipo:
AB BA ABB BAB
Poi provo la stringa casuale:
ABBBABABAB
Dovrei ottenere 3 modi
(ossia tre modi: ABB − BA − BA − BAB, oppure ABB − BA − BAB − AB e ABB − BAB − AB − AB )
Sempre con le stesse primitive di sopra, provando invece:
ABBAAAB
Ottengo 0 modi.
Il mio codice non è efficente perché lento LENTO LENTO
#include <iostream>
#include <vector>
using namespace std;
string X;
vector < string > P;
int modi = 0;
void dfs (string s){
if (s.length () >= X.length ()){
if (s == X) modi++;
return;
}
for (int i = 0; i < P.size (); i++){
dfs (s + P[i]);
}
}
int main (){
int N;//numero di primitive
cout << "Inserisci il numero di primitive: \n";
cin >> N;
string temp;
cout << "Inserisci le primitive (separate da uno spazio): \n";
for (int i = 0; i < N; i++){
cin >> temp;
P.push_back (temp);
}
cout << "Inserisci la stringa: \n";
cin >> X;
dfs ("");
cout << "Numero: " << modi << endl;
}
Chiedo il vostro aiuto... (Il problema chiaramente è dato dalla ricorsione penso)
Se le stringhe (di numero) aumentano diventa un codice molto scarso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo