Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Algoritmi 2 => Topic started by: havoc on 10-12-2009, 20:13:26



Title: Esercizio LCS pag.302 15.4-4
Post by: havoc on 10-12-2009, 20:13:26
Il professore a lezione aveva proposto questo esercizio.
Ecco la mia soluzione (script python):
http://galileo.dmi.unict.it/utenti/havoc/lcs_length.py

Spero sia abbastanza comprensibile... l'ho fatta un po' di corsa nei ritagli di tempo!


Title: Re:Esercizio LCS pag.302 15.4-4
Post by: havoc on 11-12-2009, 11:39:38
Premessa: risparmiando spazio si elimina la possibilità di conoscere le LCS.
Riscrivo per comodità la formula della ricorsione:
c[i,j] = 0                                      se i = 0 oppure j = 0
c[i,j] = c[i-1,j-1]+1                      se Xi = Yj
c[i,j] = max(c[i,j-1], c[i-1,j])         altrimenti

Ragionando per righe e guardando la formula ci accorgiamo che per ogni riga ci serve conoscere solo la riga precedente. Sfruttando ciò riusciamo a costruire un algoritmo che conserva soltanto 2*min(m,n) locazioni usando due righe "a turno".

La spiegazione del punto successivo alla prossima puntata! (Cioè appena riesco a trovare un modo per spiegarlo bene)


Title: Re:Esercizio LCS pag.302 15.4-4
Post by: havoc on 12-12-2009, 20:37:31
Non sono riuscito a trovare un modo per spiegarlo bene, magari poi provo a fare qualche disegnino... questo è quanto sono riuscito a fare.

Nella precedente versione avevamo due righe: una utilizzata esclusivamente per consultazione e l'altra veniva invece riempita.
Ora invece utilizziamo un singolo array sia per consultazione che per memorizzazione.
Pensando alla tabella dell'algoritmo classico per ogni cella ci può servire il valore in alto, il valore a sinistra e il valore in alto a sinistra, che chiamerò rispettivamente val_n, val_w, val_nw (north, west, north-west).
All'inizio di ogni ciclo esterno l'array conterrà i valori "della riga precedente" e ad ogni iterazione del ciclo interno conserveremo ciò che ci servirà alla successiva iterazione così da poter sovrascrivere le locazioni.