Algoritmi e ricerca operativa - Appunti

Appunti algoritmi 2LCS (Longest Common Subsequence)

Definizione di sottosequenza

Una sottosequenza di una data sequenza è la sequenza stessa alla quale sono stati tolti zero o più elementi. Formalmente, data una sequenza X, un’altra sequenza Z è una sottosequenza di X tale che per ogni j = 1,2,...,k si ha. Per esempio, X = <B,C,D,B> è una sottosequenza di X = <A,B,C,B,D,A,B> con la corrispondente sequenza di indici <2, 3, 5, 7>.

Sottosequenza comune

Date due sequenze X e Y, diciamo che una sequenza Z è una sottosequenza comune di X e Y se Z è una sottosequenza di entrambe le sequenze. Per esempio, se X = <A, B, C, B, D, A, B> e Y = <B, D, C, A, B, A>, la sequenza <B,C,A> è una sottosequenza comune di X e Y. Tuttavia, questa sequenza non è la più lunga sottosequenza comune perché ha lunghezza 3, e la sequenza <B,C,B,A> ha lunghezza 4. Quest’ultima sequenza è una LCS di X e Y.

Problema della più lunga sottosequenza comune

Nel problema della più lunga sottosequenza comune sono date due sequenze X e Y e si vuole trovare una sottosequenza di lunghezza massima che è comune a X e Y. Una tecnica a forza bruta per risolvere il problema della LCS consiste nell’enumerare tutte le sottosequenze di X e controllare le singole sottosequenze per vedere se sono anche sottosequenze di Y, tenendo traccia della più lunga sottosequenza trovata. Ogni sottosequenza di X corrisponde a un sottoinsieme degli indici {1,2,...,m} di X. Ci sono 2^m sottosequenze di X, quindi questo approccio richiede un tempo esponenziale, rendendolo poco conveniente per le sequenze lunghe.

Proprietà della sottostruttura ottima

Tuttavia, il problema della LCS gode della proprietà della sottostruttura ottima. Le classi naturali di sottoproblemi corrispondono a coppie di “prefissi” delle due sequenze di input. Più precisamente, data una sequenza X, definiamo l’i-esimo prefisso di X, per i=0,1,...,m. Per esempio, se X = <A, B, C, B, D, A, B>, allora X₄ = <A, B, C, B> e X₀ è la sequenza vuota.

Teorema sulla sottostruttura ottima di una LCS

Teorema: Siano X e Y le sequenze; sia Z una qualsiasi LCS di X e Y.

• Se x_m = y_n, allora z_k = x_m = y_n e Z è una LCS di X_m-1 e Y_n-1.
• Se x_m ≠ y_n, allora z_k ≠ x_m implica che Z è una LCS di X_m-1 e Y_n.
• Se x_m ≠ y_n, allora z_k ≠ y_n implica che Z è una LCS di X_m e Y_n-1.

Il teorema dimostra che una LCS di due sequenze contiene al suo interno una LCS di prefissi delle due sequenze.

Calcolo della LCS

Il teorema implica che ci sono uno o due sottoproblemi da esaminare per trovare una LCS di X e Y. Se x_m = y_n, basta trovare una LCS di X_m-1 e Y_n-1 e concatenarci l’elemento x_m = y_n, ottenendo così una LCS di X e Y. Se x_m ≠ y_n, allora dobbiamo risolvere due sottoproblemi: trovare una LCS di X_m-1 e Y_n e trovare una LCS di X_m e Y_n-1. La più lunga di queste due LCS è una LCS di X e Y. La sottostruttura ottima del problema della LCS permette di derivare la formula ricorsiva.

Definiamo c[i,j] come la lunghezza di una LCS delle sequenze X_i e Y_j:

• c[i, j] = c[i-1, j-1] + 1 se x_i = y_j
• c[i, j] = max{c[i-1, j], c[i, j-1]} se x_i ≠ y_j

Procedura ricorsiva esponenziale

Procedura: calcola_lcs_lungh(i,j,x,y)

BEGIN
  if i=0 or j=0 then return 0
  else if x[i]=y[j] then return calcola_lcs_lungh(i-1,j-1,x,y)+1
  else
    c1 = calcola_lcs_lungh(i-1,j,x,y)
    c2 = calcola_lcs_lungh(i,j-1,x,y)
    return max{c1,c2}
END

Questa procedura ha tempo esponenziale a causa delle stesse chiamate ricorsive con gli stessi valori in più posizioni dell’albero di ricorsione. Devo realizzare una versione in grado di memorizzare i valori precedenti senza ricalcolarli ogni volta.

Ottimizzazione con programmazione dinamica

Numero chiamate ricorsive distinte per calcolare c[n,m]: 0<i<n e 0<j<m → (n+1)(m+1) chiamate ricorsive distinte → Θ(nm) sottoproblemi distinti (tempo polinomiale). Per memorizzare i valori intermedi uso una o più matrici.

• Matrice C = contiene i valori della lunghezza della sequenza comune più lunga per ogni coppia di indici i,j.
• Matrice B = contiene indicazioni su come ricomporre la LCS.

Procedura: lcs_lungh(X,Y)

BEGIN
  n = length(X)
  m = length(Y)
  // riempio la prima colonna di 0
  for i=0 to n
    C[i,0]=0
  end for
  // riempio la prima riga di 0
  for j=0 to m
    C[0,j]=0
  end for
  for i=1 to n
    for j=1 to m
      if X[i]=Y[j]
        C[i,j]=C[i-1,j-1]+1
        B[i,j]='↖'
      else if C[i-1,j] ≥ C[i,j-1]
        C[i,j]=C[i-1,j]
        B[i,j]='↑'
      else
        C[i,j]=C[i,j-1]
        B[i,j]='←'
END

Il costo dell’algoritmo lcs_lungh è Θ(nm) perché il calcolo di ogni posizione della tabella richiede un tempo Θ(1). La tabella restituita dalla procedura lcs_lungh può essere utilizzata per costruire rapidamente una LCS delle sequenze X e Y.

Procedura per la stampa della LCS

Iniziamo da B[n,m] e attraversiamo la tabella seguendo le frecce. Ogni volta che incontriamo una freccia '↖' nella posizione B[i,j] significa che x_i = y_j è un elemento della LCS.

Procedura: stampa_lcs(B,X,Y,i,j)

BEGIN
  if i=0 or j=0 then return
  else if B[i,j]='↖' then
    stampa_lcs(B,X,Y,i-1,j-1)
    print X[i]
  else if B[i,j]='↑' then
    stampa_lcs(B,X,Y,i-1,j)
  else
    stampa_lcs(B,X,Y,i,j-1)
END

La procedura stampa_lcs impiega un tempo Θ(n+m), perché almeno uno dei valori i e j diminuisce in ogni stadio della ricorsione.

Esempio

Le tabelle C e B calcolate da lcs_lungh con le sequenze X =<A,B,C,B,D,A,B> e Y = <B,D,C,A,B,A>. La casella nella riga i e colonna j contiene il valore di C[i,j] e la freccia appropriata come valore di B[i,j]. Il valore 4 in C[7,6] è la lunghezza di una LCS <B,C,B,A> di X e Y. Per ricostruire gli elementi di una LCS, basta seguire le frecce B[i,j] partendo dall’angolo inferiore destro della tabella. Ogni freccia sul percorso corrisponde a una posizione '↖' (evidenziata) per la quale x_i = y_j è un elemento di una LCS.

LCS di lunghezza ≥ k

Input: 2 stringhe X e Y e un numero positivo k. Output: c[i,j,z] : {0,1} se esiste una sottosequenza comune a X e Y di lunghezza ≥ z terminante con X_i = Y_j ∈ z {0, ..., k}.

Soluzione C[m,n,k] = 1 se esiste, 0 se non esiste. Tempo di calcolo: Θ(nm).

HCS (Heaviest Common Subsequence)

Serve a determinare la sottosequenza più pesante, quindi ad ogni elemento assegno un peso w.

Es.: X = <A,B,C,B,D,A,B>, Y = <B,D,C,A,B,A>

• LCS 1 = <B,C,B,A>, LCS 2 = <B,D,A,B>
• w(A) = w(B) = w(C) = 1, w(D) = 3

Quindi, la sottosequenza 1 ha peso 4, la sottosequenza 2 ha peso 6. Non è detto che la sottosequenza più pesante sia la più lunga.

Caratterizzazione HCS: Z = <Z₁, ..., Z_k> = HCS(X,Y). Se X_m = Y_n allora Z = X_m = Y_n Z_k = HCS(X_m-1, Y_n-1) Indico con c[i,j] il peso di una HCS di X_i e Y_i. Posso costruire la seguente ricorrenza:

• 0 se i=0 o j=0
• w(X_i) + c[i-1, j-1] se X_i = Y_i
• max{c[i-1, j], c[i, j-1]} se X_i ≠ Y_i

Tempo di calcolo: Θ(nm).

Knapsack (problema dello zaino)

Input: {1, 2, ..., n} n articoli, v₁, v₂, ..., v_n valori associati agli articoli, w₁, w₂, ..., w_n pesi/ingombri associati agli articoli, W = capacità massima. Output: riempire lo zaino massimizzando il valore totale degli elementi selezionati. Risolviamo con la programmazione dinamica.

M[i] = massimo ottenibile da sottoinsiemi di {1,2,...,i}.

• Se w_i > W, M[i] = M[i-1] perché non posso aggiungere l’elemento i allo zaino.
• Se w_i ≤ W, riempendo questo non ho informazioni sufficienti: non so quanto manca per riempire lo zaino. Introduco la capacità libera = q. Quindi definisco la nuova variabile M[i,q] = valore massimo degli oggetti compresi tra {1,...,i} che possono essere contenuti in un box grande q, cioè nella capacità libera.

• Ø se i=0 o q=0
• M[i,q] = M[i-1,q] se w_i > q
• max{M[i-1,q-w_i]+v_i, M[i-1,q]} se w_i ≤ q

Algoritmo:

FOR i:=1 to n DO
  FOR q:=1 to W DO
    IF wi > q then M[i,q]:=M[i-1,q]
    ELSE M[i,q]:= max{M[i-1,q-wi]+vi, M[i-1,q]}
END

Algoritmi sui grafi

• BFS (visita in ampiezza) per calcolare il numero di vertici raggiungibili da V
• DFS (visita in profondità) per calcolare le componenti connesse – numero di componenti e loro dimensione
• Per ordinamento topologico
• Per vedere se il grafo è connesso o aciclico
• FLOYD WARSHALL per calcolare il costo dei cammini minimi di G.

Terminologia dei grafi

Un grafo orientato G è una coppia (V,E) dove V è un insieme finito ed E una relazione binaria su V (relazione binaria R su due insiemi A e B è un sottoinsieme del prodotto cartesiano AxB tale che aRb). In un grafo non orientato G = (V,E) l’insieme di archi E è formato da coppie non ordinate di vertici, cioè un arco è un insieme {u,v} con u,v ∈ V e u ≠ v. Se (u,v) è un arco di un grafo orientato G=(V,E) si dice che (u,v) è incidente o esce da u e incidente o entra in v. Se (u,v) è un arco di un grafo non orientato G=(V,E) si dice che (u,v) è incidente sui vertici u e v. Se (u,v) è un arco di un grafo G=(V,E) si dice che il vertice v è adiacente a u.

Il grado di un vertice in un grafo non orientato è il numero di archi incidenti su di esso. Un cammino di lunghezza k da un vertice u a un vertice u’ è una sequenza di vertici <v₀,v₁,v₂,...,v_k> tali che u=v₀ e u’=v_k. La lunghezza di un cammino corrisponde al suo numero di archi. In un grafo non orientato, un cammino forma un ciclo se k≥3 e i vertici sono distinti e v₀=v_k. Un grafo senza cicli si definisce aciclico.

Un grafo non orientato è connesso se ogni coppia di vertici è collegata in un cammino. Un grafo orientato è fortemente connesso se ogni vertice è raggiungibile da ogni altro. Se G è un grafo non orientato, aciclico e sconnesso, allora è una foresta.

Rappresentazione dei grafi

Un grafo G = (V,E) può essere rappresentato tramite:

• Liste di adiacenza
• Matrice di adiacenza

Entrambi i metodi possono essere applicati ai grafi orientati e non orientati. La rappresentazione con liste di adiacenza di un grafo G = (V,E) consiste in un array Adj di |V| liste, una per ogni vertice in V. Per ogni u ∈ V, la lista di adiacenza Adj[u] contiene tutti i vertici v tali che esista un arco (u,v) ∈ E. Ovvero Adj[u] contiene tutti i vertici adiacenti a u in G. Un vettore V contiene per ogni vertice v del grafo un puntatore alla lista dei vertici adiacenti a v = Adj(v).

Se G è un grafo orientato, la somma delle lunghezze di tutte le liste di adiacenza è |E|, perché un arco della forma (u,v) è rappresentato inserendo v in Adj[u]. Se G è un grafo non orientato, la somma delle lunghezze di tutte le liste di adiacenza è 2|E|, perché se (u,v) è un arco non orientato, allora u appare nella lista di adiacenza di v e viceversa. Per i grafi orientati e non orientati, la quantità di memoria richiesta per la rappresentazione con liste di adiacenza è Θ(V+E).

Svantaggio dell’utilizzo delle liste di adiacenza: per determinare se esiste un arco nel grafo, nel caso peggiore ho Θ(|Adj[u]|) in quanto devo scorrere tutta la lista di adiacenza. Un rimedio a questo svantaggio è l’utilizzo della rappresentazione con una matrice di adiacenza, al costo di usare una maggiore quantità di memoria. Per la rappresentazione con matrice di adiacenza di un grafo G = (V,E) si suppone che i vertici siano numerati V=v₁,v₂,...,v_n. Questa rappresentazione consiste in una matrice A = (a_ij) di dimensione nxn dove a_ij = 1 se esiste un arco (v_i,v_j) ∈ E, altrimenti a_ij = 0.