[Algoritmi] Programmazione dinamica

[Howard_Wolowitz]

Innanzitutto buona serata!!
Ho i seguenti esercizi di programmazione dinamica sui quali vorrei se possibile un parere relativo allo svolgimento da me fornito di seguito.
1)Sia dato un grafo G(V, E) con V insieme dei vertici ed E insieme degli archi, ed una funzione [tex]col: E \rightarrow {rosso, nero}[/tex] che associa ad un arco di G un colore.
Scrivere l'equazione di ricorrenza per un algoritmo dinamico che calcoli il cammino minimo da un nodo [tex]i[/tex] ad un nodo [tex]j[/tex] formato da un uguale numero di archi rossi e neri.
2)Prese due sequenze [tex]X = [/tex] e [tex]Y = [/tex] di numeri naturali, calcolare la più lunga sottosequenza comune Z di X e Y, tale che Z alterni numeri pari a numeri dispari.
3)Presa una sequenza [tex]X = [/tex] di lettere dell'alfabeto italiano, calcolare la più lunga sottosequenza Z di X i cui simboli sono ordinati dalla 'z' alla 'a'.
Di segutio lo svolgimento degli esericizi di sopra:
1)
Scelgo di utilizzare per tale calcolo una versione modificata dell'algoritmo di Floyd Warshall e definisco pertanto mediante [tex]D(i,j,k,r,n)[/tex] come la distanza dal nodo i al nodo j passando per il k-esimo nodo con r archi rossi e n archi neri.
A questo punto dico che:
[img]http://latex.codecogs.com/gif.latex?D%28i%2Cj%2Ck%2Cr%2Cn%29%20%3D%20min%5Cbegin%7Bcases%7D%20D%28i%2Cj%2Ck-1%2Cr%2Cn%29%20%26%20%5Ctext%7B%20se%20k%20non%20appartiene%20ad%20alcun%20cammino%20tra%20i%20e%20j%20%7D%20%5C%5C%20D%28i%2Ck%2Ck-1%2Cr_%7B1%7D%2Cn_%7B1%7D%29%20+%20D%28k%2Cj%2Ck-1%2Cr_%7B2%7D%2Cn_%7B2%7D%29%20%26%20%5Ctext%7B%20se%20%7D%20%28r_1%20+%20r_2%20%3D%20r%29%20%5Cwedge%20%28n_1%20+%20n_2%20%3D%20n%29%20%5Cend%7Bcases%7D[/img]
e per i casi base pongo
[img]http://latex.codecogs.com/gif.latex?D%28i%2Cj%2C0%2C1%2C0%29%20%3D%20%5Cbegin%7Bcases%7D%20w_%7Bij%7D%20%26%20%5Ctext%7Bse%20%7D%20i%5Cneq%20j%20%5Cwedge%20col%28%28i%2Cj%29%29%20%3D%20rosso%5C%5C%200%20%26%20%5Ctext%7Bse%20%7D%20i%20%3D%20j%5C%5C%20%5Cinfty%20%26%20%5Ctext%7Baltrimenti%7D%20%5Cend%7Bcases%7D[/img]
[img]http://latex.codecogs.com/gif.latex?D%28i%2Cj%2C0%2C0%2C1%29%20%3D%20%5Cbegin%7Bcases%7D%20w_%7Bij%7D%20%26%20%5Ctext%7Bse%20%7D%20i%5Cneq%20j%20%5Cwedge%20col%28%28i%2Cj%29%29%20%3D%20nero%5C%5C%200%20%26%20%5Ctext%7Bse%20%7D%20i%20%3D%20j%5C%5C%20%5Cinfty%20%26%20%5Ctext%7Baltrimenti%7D%20%5Cend%7Bcases%7D[/img]
ed infine
[img]http://latex.codecogs.com/gif.latex?D%28i%2Cj%2C0%2Cr%2Cn%29%20%3D%200%20%5Ctext%7B%20%7D%20%5Cforall%20r%2C%20n%20%3A%20%28r%20%5Cneq%200%20%5Cwedge%20r%20%5Cneq%201%29%20%5Cwedge%20%28n%20%5Cneq%200%20%5Cwedge%20n%20%5Cneq%201%29[/img]
La distanza tra due nodi [tex]i[/tex] e [tex]j[/tex] sarà pertanto data da [tex]max{D(i,j,n,c,c)}[/tex] con [tex]n = \left|V\right|[/tex] con [tex]0 \leq c \leq max{(\left|R\right|,\left|N\right|)}[/tex]
2)Definisco [tex]c(i,j, PARI)[/tex] e [tex]c(i,j, DISPARI)[/tex] come le lunghezze delle sottosequenze terminanti rispettivamente con un numero pari e con un numero dispari tra le sottosequenze di [tex]X[/tex] di lunghezza [tex]i[/tex] e [tex]Y[/tex] di lunghezza [tex]j[/tex].
Ora pongo
[img]http://latex.codecogs.com/gif.latex?c%28i%2Cj%2CPARI%29%20%3D%20%5Cbegin%7Bcases%7D%201%20+%20c%28i-1%2Cj-1%2CDISPARI%29%20%26%20%5Ctext%7B%20se%20%7D%20PARI%28x_%7Bi%7D%29%20%5Cwedge%20x_%7Bi%7D%20%3D%20y_%7Bj%7D%20%5C%5C%20max%7B%5C%7Bc%28i%2Cj-1%2CPARI%29%2Cc%28i-1%2Cj%2CPARI%29%5C%7D%7D%20%26%20%5Ctext%7B%20altrimenti%20%7D%20%5Cend%7Bcases%7D[/img]
e
[img]http://latex.codecogs.com/gif.latex?c%28i%2Cj%2CDISPARI%29%20%3D%20%5Cbegin%7Bcases%7D%201%20+%20c%28i-1%2Cj-1%2CPARI%29%20%26%20%5Ctext%7B%20se%20%7D%20DISPARI%28x_%7Bi%7D%29%20%5Cwedge%20x_%7Bi%7D%20%3D%20y_%7Bj%7D%20%5C%5C%20max%7B%5C%7Bc%28i%2Cj-1%2CDISPARI%29%2Cc%28i-1%2Cj%2CDISPARI%29%5C%7D%7D%20%26%20%5Ctext%7B%20altrimenti%20%7D%20%5Cend%7Bcases%7D[/img]
Ed infine per i casi baso avrò:
[tex]c(i,0,PARI) = c(i,0,DISPARI) = 0[/tex][tex]\forall i : 0 \leq i \leq n[/tex]
[tex]c(0,j,PARI) = c(0,j,DISPARI) = 0[/tex][tex]\forall j : 0 \leq j \leq n[/tex]
La soluzione sarà pertanto uguale a:
[tex]max{\{c(i,j,PARI),c(i,j,DISPARI)\}}[/tex] con [tex]i,j : 0 \leq i \leq n \wedge 0 \leq j \leq m[/tex]
3)
Supposto che preso un carattere [tex]c[/tex] il suo predecessore sia identificato da [tex]c - 1[/tex] e che [tex]l(i,c)[/tex] indichi la lunghezza della sottosequenza più lunga di [tex]X[/tex] di lunghezza [tex]i[/tex] contenente le lettere ordinate a partire da [tex]c[/tex] segue che:
[img]http://latex.codecogs.com/gif.latex?l%28i%2Cc%29%20%3D%20%5Cbegin%7Bcases%7D%201%20+%20l%28i+1%2Cc-1%29%20%26%20%5Ctext%7B%20se%20%7D%20x_%7Bi%7D%20%3D%20c%20%5C%5C%20l%28i%20-%201%2C%20c%29%20%26%20%5Ctext%7B%20altrimenti%20%7D%20%5Cend%7Bcases%7D[/img]
e per li caso base
[img]http://latex.codecogs.com/gif.latex?l%28n%2Cc%29%20%3D%20%5Cbegin%7Bcases%7D%201%20%26%20%5Ctext%7B%20se%20%7D%20x_%7Bn%7D%20%3D%20c%20%5C%5C%200%20%26%20%5Ctext%7B%20altrimenti%20%7D%20%5Cend%7Bcases%7D[/img]
La soluzione è:
[tex]max{l(i,'z')}[/tex] con [tex]0 \leq i \leq n[/tex]

La mie domande in merito sono pertanto:
- sono corrette le ricorrenze?
- in caso contrario vedete altri metodi di scriverle?
Buona serata a tutti!!

[apatriarca]

Il primo problema devo ancora guardarlo con attenzione, ma inizio a commentare gli altri due problemi.

Nel secondo esercizio non capisco la tua definizione di \(c(i, j, PARI)\) e \(c(i,j,DISPARI)\) per cui non sono sicuro della correttezza della tua soluzione. Guardando la tua equazione di ricorrenza direi che probabilmente hai dimenticato di dire che stai calcolando la lunghezza della più lunga sotto-sequenza COMUNE, ma credo che l'equazione di ricorrenza sia comunque sbagliata. In effetti non è detto che la sotto-sequenza più lunga sia alla fine della stringa fino ad \(i\) o \(j\) in base alla tua definizione per cui non è sufficiente controllare che il numero sia pari o dispari e che siano uguali per incrementare il numero trovato. Hai almeno bisogno di definire una nuova funzione che restituisce la più lunga sotto-sequenza terminale comune che finisce con un numero pari o dispari.

Il terzo esercizio lo trovo un po' ambiguo. Tu sembri averlo interpretato come la ricerca di una sottosequenza del tipo z,v,u,t,s.. mentre leggendo l'esercizio io ho pensato che le lettere dovessero essere semplicemente ordinate in modo che lettere successive nella sotto-sequenza devono essere ordinate in modo "inverso" all'ordine dell'alfabeto (quindi anche qualcosa tipo z, f, e, a potrebbe andare bene nella mia interpretazione).

[Giova411]

Il terzo, se non sbaglio, si risolve come il "Longest Palindromic Subsequence".
http://users.eecs.northwestern.edu/~dda ... w6-sol.pdf
prendi spunto dal problema 6.7

Nel primo, secondo me, vuoi memorizzare troppi dati. L'idea di numerare ad esempio 0 i rossi ed 1 i neri (o viceversa) può essere utile.

[Howard_Wolowitz]

Innanzitutto grazie delle risposte!!
@apatriarca: per il secondo hai ragione in effetti a me interessa la lunghezza ed è quella che credo di calcolare con la ricorrenza riportata. In realtà per tutti e tre gli esercizi mi occupo del valore della soluzione ottima e mai della soluzione ottima in se... Ho riscritto gli esercizi presi da appunti e temi d'esame dove per soluzione si intende il valore della soluzione ottima e non la soluzione ottenuta dal 4° passo della programmazione dinamica.
Per il terzo pure, nel senso che mi sono accorto di avere preso un po' troppo alla lettera la consegna.
Detto ciò come faresti il secondo esercizio? E soprattutto in cosa non ti convince la ricorrenza, preso atto del fatto che ho erroneamente parlato di sottosequenza e non di lunghezza della stessa?

@Giova411: link interessante!! Come ti approcceresti al primo problema? Riesci ad indicarmi un 'punto di fallimento' della mia ricorrenza al fine di poter idearne una nuova?

Grazie ancora e buona serata!!

[Giova411]

In effetti dovresti riportare meglio il testo dell'esercizio. L'ha scritti un po' troppo veloce mi sa, sono stitici

Ti dico che, per me, la programmazione dinamica è molto difficile e non mi ritengo idoneo ad ideare formule valide.
A vederlo così il terzo è proprio identico all'esercizio del link quindi potresti implementarlo se vuoi esercitarti.

[apatriarca]

Non mi è chiara la differenza che poni tra "valore della soluzione ottima" e "soluzione ottima in se".. Ma ti ho già detto l'errore che vedo nelle ultime due ricorrenze (le sottosequenze di lunghezza massima che stai calcolando non terminano necessariamente in \(x_i\) ma potrebbero essere già terminate in precedenza per cui quando scrivi la ricorrenza in \(i\) in termini di \(i+1\) o \(i-1\) non è in generale sufficiente sommare uno se l'ultimo termine potrebbe far parte di una sottosequenza che ti interessa). Ti faccio un esempio (terzo esercizio):
X = "abedcedf"
l(6) = 3
l(7) = 3
anche che il sesto carattere è minore del settimo in base al nostro ordine.

[Howard_Wolowitz]

Ringrazio delle risposte e torno dopo una decina di giorni a proporre una nuova soluzione dell'esercizio 3.
Dagli appunti del docente un esercizio quale il terzo viene risolto con questa equazione di ricorrenza:
[img]http://latex.codecogs.com/gif.latex?L%28i%29%20%3D%201%20+%20max%5C%7BL%28j%29%20%7C%20x_j%20%3C%20x_i%20%5Cwedge%200%20%3C%20j%20%5Cleq%20n%20%5C%7D[/img]
e la soluzione è pertanto data da [img]http://latex.codecogs.com/gif.latex?max%5C%7BL%28i%29%20%7C%200%20%3Ci%20%5Cleq%20n%5C%7D[/img]
Ora io volevo proporre la seguente soluzione, più simile alle altre da me utilizzate, fino ad ora, in questo topic:
Supposto che [img]http://latex.codecogs.com/gif.latex?max%5C%7B%5Cvarnothing%5C%7D%20%3D%200[/img]
[img]http://latex.codecogs.com/gif.latex?c%28i%2C%20l%29%20%3D%20%5Cbegin%7Bcases%7D%201%20+%20max%5C%7Bc%28j%2C%20x_i%29%20%7C%200%20%3C%20j%20%5Cleq%20i%5C%7D%20%26%20%5Ctext%7B%20se%20%7D%20x_i%20%3E%20l%20%5C%5C%200%20%26%20%5Ctext%7B%20altrimenti%20%7D%20%5Cend%7Bcases%7D[/img]
dove [tex]i[/tex] e [tex]j[/tex] rappresentano le posizioni della sottosequenza [tex]X[/tex] in oggetto e [tex]l[/tex] una lettera dell'alfabeto con la quale eseguire il confronto.
Per ogni indice [tex]i[/tex] di [tex]X[/tex] definisco [img]http://latex.codecogs.com/gif.latex?c%28i%29%20%3D%201%20+%20max%5C%7Bc%28j%2C%20x_i%29%20%7C%200%20%3C%20j%20%3C%20i%29%5C%7D[/img]
Il caso base [img]http://latex.codecogs.com/gif.latex?c%280%29%20%3D%20c%280%2Cj%29%20%3D%200%20%5Cforall%20j%20%5Cin%20%5C%7Ba%2Cb%2Cc%2C...%2Cz%5C%7D[/img]
La soluzione è pertanto [img]http://latex.codecogs.com/gif.latex?max%5C%7Bc%28i%29%20%7C%200%20%3C%20i%20%5Cleq%20n%5C%7D[/img]
Opinioni su tale soluzione? Vi sembra conforme a quella del docente e soprattutto è corretta?
Grazie a tutti e buona serata!!