[Programmazione dinamica]Coppie a differenza minima
TESTO:
Data una sequenza di n interi non negativi P, trovare la coppia (P, P[j]) di elementi di P con i < j tale che la differenza P[j] - P sia massima.
Un algoritmo funzionante l'ho anche trovato che lo risolve in tempo lineare come richiesto, il problema è che non riesco a definire un opportuno spazio dei sottoproblemi e soprattutto una relazione di ricorrenza per la differenza. Qualcuno mi aiuta?
Data una sequenza di n interi non negativi P, trovare la coppia (P, P[j]) di elementi di P con i < j tale che la differenza P[j] - P sia massima.
Un algoritmo funzionante l'ho anche trovato che lo risolve in tempo lineare come richiesto, il problema è che non riesco a definire un opportuno spazio dei sottoproblemi e soprattutto una relazione di ricorrenza per la differenza. Qualcuno mi aiuta?
Risposte
Che algoritmo hai trovato? Io ho trovato il seguente:
Sia $P_s \in NN$ l’elemento $s$-esimo della sequenza. Sia $m_s$ il minimo tra gli elementi della sottosequenza formata dai primi $s$ elementi. Siano $I_s$ e $J_s$ rispettivamente gli elementi della sottosequenza formata dai primi $s$ elementi e che rispettano la condizione del problema ($(I_n, J_n)$ è la coppia che il problema chiede di trovare).
Iniziamo considerando la sottosequenza iniziale formata da $2$ elementi:
$I_2 = P_1$
$J_2 = P_2$
$m_2 = min(P_1, P_2)$
Supponiamo quindi di aver analizzato tutta la sottosequenza iniziale formata da $k$ elementi e di voler calcolare i valori per la sottosequenza di $k+1$ elementi.
$(I_{k+1}, J_{k+1}) = \{((I_k, J_k), text{se } (J_k - I_k) >= (P_{k+1} - m_k)),((m_k, P_{k+1}), text{altrimenti}):}$
$m_{k+1} = min(m_k, P_{k+1})$
Sia $P_s \in NN$ l’elemento $s$-esimo della sequenza. Sia $m_s$ il minimo tra gli elementi della sottosequenza formata dai primi $s$ elementi. Siano $I_s$ e $J_s$ rispettivamente gli elementi della sottosequenza formata dai primi $s$ elementi e che rispettano la condizione del problema ($(I_n, J_n)$ è la coppia che il problema chiede di trovare).
Iniziamo considerando la sottosequenza iniziale formata da $2$ elementi:
$I_2 = P_1$
$J_2 = P_2$
$m_2 = min(P_1, P_2)$
Supponiamo quindi di aver analizzato tutta la sottosequenza iniziale formata da $k$ elementi e di voler calcolare i valori per la sottosequenza di $k+1$ elementi.
$(I_{k+1}, J_{k+1}) = \{((I_k, J_k), text{se } (J_k - I_k) >= (P_{k+1} - m_k)),((m_k, P_{k+1}), text{altrimenti}):}$
$m_{k+1} = min(m_k, P_{k+1})$
Mi sa che è esattamente questo, solo che non riuscivo ad esprimere la relazione di ricorrenza. Ti posto lo pseudocodice in caso avessi mal interpretato quello che hai scritto:
Solo che il mio docente vuole a tutti i costi farti ragionare in divde & conquer quando per la PD puoi benissimo ragionare direttamente in Bottom-Up, quindi ho bisogno di dimostrare una proprietà di sottostruttura ottima e di scrivere una relazione di ricorrenza per i sottoproblemi, cosa che non riesco a fare, anzi semplicemente ho ragionato come te solo che non riesco a dimostrare la proprietà di sottostruttra.
LDP(P) n := length(P) c[2] := p[2] - p[1] i := p[1] j := p[2] m := min(i, j) for k:= 3 to n do if p[k] - m > j - i then c[k] := p[k] - m j := p[k] i := m else c[k] := c[k-1] if (p[k] < m) then m := p[k] return c and (i, j)
Solo che il mio docente vuole a tutti i costi farti ragionare in divde & conquer quando per la PD puoi benissimo ragionare direttamente in Bottom-Up, quindi ho bisogno di dimostrare una proprietà di sottostruttura ottima e di scrivere una relazione di ricorrenza per i sottoproblemi, cosa che non riesco a fare, anzi semplicemente ho ragionato come te solo che non riesco a dimostrare la proprietà di sottostruttra.
Io è da molto tempo che non mi occupo di queste cose, ma programmando in haskell sono abbastanza abituato a definire i problemi in questo modo. In effetti normalmente l’implementazione di questi codici nei linguaggi più comuni o anche in pseudocodice si differenzia molto dalle relazioni di ricorrenza e in generale dalla loro definizione in termini più matematici. Per dimostrare la proprietà di sottostruttura puoi semplicemente partire dal caso base del quale è immediato dimostrare la proprietà di sottostruttura ottima, dopodiché supponi che sia vero fino alla sottosequenza di lunghezza $k$ e verifichi che la definizione per quella di lunghezza $(k+1)$ genera una soluzione ottima per il sottoproblema. Vista la generalità di $k$ la dimostrazione vale per tutte le sottosequenze e in particolare per la sequenza completa.
Nel tuo pseudocodice non credo sia necessario definire c come un array. Il tuo algoritmo è identico al mio.
Nel tuo pseudocodice non credo sia necessario definire c come un array. Il tuo algoritmo è identico al mio.
"apatriarca":
Io è da molto tempo che non mi occupo di queste cose, ma programmando in haskell sono abbastanza abituato a definire i problemi in questo modo. In effetti normalmente l’implementazione di questi codici nei linguaggi più comuni o anche in pseudocodice si differenzia molto dalle relazioni di ricorrenza e in generale dalla loro definizione in termini più matematici. Per dimostrare la proprietà di sottostruttura puoi semplicemente partire dal caso base del quale è immediato dimostrare la proprietà di sottostruttura ottima, dopodiché supponi che sia vero fino alla sottosequenza di lunghezza $k$ e verifichi che la definizione per quella di lunghezza $(k+1)$ genera una soluzione ottima per il sottoproblema. Vista la generalità di $k$ la dimostrazione vale per tutte le sottosequenze e in particolare per la sequenza completa.
Nel tuo pseudocodice non credo sia necessario definire c come un array. Il tuo algoritmo è identico al mio.
Il fatto è che mi hanno insegnato che la proprietà di sottostruttura ottima viene dimostrata in questo modo: Si parte da un problema a taglia più elevata e si suppone di avere una soluzione ottima per tale problema. Successivamente si divide il problema originario in più sottoproblemi e si dimostra (in genere per assurdo) che la proprietà di ottimalità vale anche per i sottoproblemi.
Non vedo perché limitarsi ad un singolo metodo di dimostrazione quando in questo caso è molto più semplice lavorare in modo differente. Mi sembra solo un modo per complicarsi la vita. Il metodo da te descritto dimostra inoltre solo che se la soluzione del problema è ottimale allora lo è anche quella dei sottoproblemi, mentre quello da me descritto dimostra anche l'implicazione inversa che mi sembra più importante. Con il tuo metodo manca la dimostrazione che se i sottoproblemi hanno soluzione ottima, allora anche quella del problema è ottima. Ma forse hai solo dimenticato un passaggio oppure ho frainteso qualcosa.
"apatriarca":
Non vedo perché limitarsi ad un singolo metodo di dimostrazione quando in questo caso è molto più semplice lavorare in modo differente. Mi sembra solo un modo per complicarsi la vita. Il metodo da te descritto dimostra inoltre solo che se la soluzione del problema è ottimale allora lo è anche quella dei sottoproblemi, mentre quello da me descritto dimostra anche l'implicazione inversa che mi sembra più importante. Con il tuo metodo manca la dimostrazione che se i sottoproblemi hanno soluzione ottima, allora anche quella del problema è ottima. Ma forse hai solo dimenticato un passaggio oppure ho frainteso qualcosa.
No è esattamente come hai detto tu. Forse però non è di interesse dimostrare che è condizione necessaria e sufficiente (usa questo metodo anche Introduction to Algorithms), purtroppo mi sono iscirtto ad ingegneria che è una delle facoltà più dogmatiche tra quelle scientifiche, sbagliando, ma ho intenzione di rimediare, per ora mi tocca fare come mi chiedono e sperare di riuscirci. Cmq sto esame di dati e algoritmi 2 ho difficoltà a passarlo proprio perché mi impongono di ragionare in un certo modo, e non sono l'unico ad avere queste difficoltà. Di solito lo passano senza problemi (e senza studiare niente) gente che ragiona prettamente in D&C, gli altri lo rifanno n volte prima di passarlo, e magari lo passano la n+1-esima studiando 1/10 delle altre volte.
Il metodo da me descritto e il tuo sono del tutto equivalenti, cambia solo l’ordine in cui dimostri le cose. Nel tuo caso dimostri prima che se vale per $k > 1$ vale anche per $k-1$ e poi dimostri il caso base (ma nella tua descrizione secondo me mancava un passaggio). Nel metodo da me descritto parto dal caso base e dimostro poi che se vale per $k$ vale anche per $k+1$. Si tratta in entrambi i casi di una dimostrazione per induzione (anche se normalmente in matematica si parte dal caso base). La dimostrazione per assurdo, se piace al tuo professore, dell'ottimalità dei sottoproblemi è possibile: basta supporre che ci sia una coppia diversa da $(I_k, J_k)$ e $(m_k, P_k)$ che sia ottimale e poi osservare che la differenza è sempre inferiore. Gli algoritmi di programmazione dinamica come questo usano comunque spesso l'approccio bottom-up, non capisco come mai costringere ad usare quello top-down.
Io mi sono iscritto a matematica (dopo essermi laureato in ingegneria) in parte per questo motivo.
Io mi sono iscritto a matematica (dopo essermi laureato in ingegneria) in parte per questo motivo.
"apatriarca":
Il metodo da me descritto e il tuo sono del tutto equivalenti, cambia solo l’ordine in cui dimostri le cose. Nel tuo caso dimostri prima che se vale per $k > 1$ vale anche per $k-1$ e poi dimostri il caso base (ma nella tua descrizione secondo me mancava un passaggio). Nel metodo da me descritto parto dal caso base e dimostro poi che se vale per $k$ vale anche per $k+1$. Si tratta in entrambi i casi di una dimostrazione per induzione (anche se normalmente in matematica si parte dal caso base). La dimostrazione per assurdo, se piace al tuo professore, dell'ottimalità dei sottoproblemi è possibile: basta supporre che ci sia una coppia diversa da $(I_k, J_k)$ e $(m_k, P_k)$ che sia ottimale e poi osservare che la differenza è sempre inferiore. Gli algoritmi di programmazione dinamica come questo usano comunque spesso l'approccio bottom-up, non capisco come mai costringere ad usare quello top-down.
Io mi sono iscritto a matematica (dopo essermi laureato in ingegneria) in parte per questo motivo.
Forse perché puoi anche utilizzare la tecnica di memoizzazione, ovvero parti dalla relazione di ricorrenza pura e semplice, scrivi l'algoritmo divide & conquer ma memorizzi i risultati dei sottoproblemi in un'apposita struttura dati. Così facendo se ci sono sottoproblemi sovrapposti (ovvero riutilizzati) non serve ricalcolarli ma basta estrarne il risultato dalla struttura dati. Questa seconda scelta l'avrei usata prettamente per il problema della moltiplicazione di catene di matrici perché effettivamente scrivere il codice bottom-up di quell'algoritmo è un pochino incasinato perché i risultati non vengono prelevati "in ordine" dalla matrice (ovvero partendo dall'elemento (0.0) e procedendo a ricavare un'intera riga o colonna) ma procedono in diagonale. Per gli altri problemi classici è vero che il bottom-up è sicuramente più semplice, ad esempio per gli algoritmi APSP è sicuramente più facile scrivere la versione bottom-up che quella memoizzata.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo