Algoritmi e strutture di dati - esempio tesina find-maximum-subarray

Elaborato di algoritmi e strutture dati

Trovare una soluzione ed analizzarla al problema del Find-Max-Subarray

Indice

• Introduzione al problema
• Soluzione
• Soluzione brute force con tempo di esecuzione cubico
• Soluzione brute force con tempo di esecuzione quadratico
• Soluzione ricorsiva
• Soluzione lineare
• Analisi della complessità
• Complessità brute force con tempo di esecuzione cubico
• Complessità brute force con tempo di esecuzione quadratico
• Complessità algoritmo ricorsivo
• Complessità FIND-MAX-CROSSING-SUBARRAY
• Complessità FIND-MAXIMUM-SUBARRAY
• Complessità algoritmo lineare
• Analisi della correttezza
• Correttezza brute force con tempo di esecuzione cubico
• Correttezza brute force con tempo di esecuzione quadratico
• Correttezza algoritmo ricorsivo
• Correttezza FIND-MAX-CROSSING-SUBARRAY
• Correttezza FIND-MAXIMUM-SUBARRAY
• Correttezza algoritmo lineare
• Simulazione dell'algoritmo
• Simulazione brute force con tempo di esecuzione cubico
• Simulazione brute force con tempo di esecuzione quadratico
• Simulazione algoritmo ricorsivo
• Simulazione algoritmo lineare
• Appendice
• Bibliografia

Introduzione al problema

Si vuole analizzare il problema del massimo sottoarray. Nella nostra analisi descriveremo attentamente il problema, presentando più soluzioni per esso, analizzando la complessità delle soluzioni trovate ed, infine, implementandole in un apposito linguaggio di programmazione. Il problema del massimo sottoarray è il seguente: “Sia dato un vettore A di n elementi, determinare il sottoarray contiguo e non vuoto di A tale che la somma dei suoi elementi sia massima”. Chiameremo questo sottoarray massimo sottoarray. Il problema non sussiste se A è composto solo da elementi positivi, in questo caso il massimo sottoarray è l’intero vettore A oppure se è composto solo da elementi negativi, il problema del massimo sottoarray diventa il problema di determinare il valore massimo.

Soluzione

Presenteremo alcune soluzioni che risolvono questo problema, iniziando prima a descrivere le soluzioni con una complessità maggiore, fino a concludere analizzando una soluzione lineare al problema.

A. Soluzione brute force con tempo di esecuzione cubico

È facile trovare una soluzione a forza bruta per questo problema, basta valutare tutti i possibili sottoarray contigui di A e verificare quale di essi ha gli elementi la cui somma è maggiore. Presentiamo il pseudo-codice di un algoritmo che risolve questo problema.

BF_FIND_MAX_SUBARRAY(A, L, R)
1 maxSum = -inf
2 for j = L to R
3 for k = j to R
4 sum = 0
5 for i = j to k
6 sum = sum + X[i]
7 If (maxSum < sum)
8 maxSum = sum;
9 maxL = k;
10 maxR = i;
11 return (maxL, maxR, max-sum)

Questa procedura non fa altro che valutare le somme dei valori di tutti i possibili sottoarray, ogni volta che trova un sottoarray la cui somma dei valori è massima, aggiorna maxSum e gli indici che indicano il sottoarray massimo.

B. Soluzione a brute force in un tempo quadratico

La seguente soluzione presentata, è sempre a forza bruta, però, più intelligente si basa sull’idea che è possibile analizzare in uno solo scorrimento diversi sotto-vettori. Infatti, la somma degli elementi di A[i .. j] è la somma degli elementi di A[i .. j-1] e A[j]. Quindi posso valutare la somma degli elementi del sotto-vettore A[i .. j] semplicemente sommando ad A[i .. j-1] il valore A[j]. Se questo nuovo valore sarà il massimo trovato me lo conservo (come mi conservo anche gli indici del sotto-vettore) e continuo ad iterare finché j non sarà uguale ad h, a questo punto incremento i e ricomincio. Termino il ciclo quando i sarà uguale ad h. A questo punto ho valutato tutti i possibili sub-array.

Smart-BF-Subarray(A, l, h)
1 max-sum= -inf
2 for i = l to h
3 s-temp = 0
4 for j = l to h
5 if (j >= i)
6 s-temp = s-temp + A[j]
7 if (max-sum < s-temp)
8 max-sum = s-temp
9 max-l = i
10 max-h = j
11 return(max-l, max-h, max-sum)

C. Soluzione ricorsiva

Una soluzione più efficiente può essere trovata utilizzando la versione ricorsiva dell’algoritmo. Vediamo come possiamo risolvere il problema del massimo sub-array utilizzando il metodo del divide et impera:

• Array di partenza A [l .. R];
• Definisco mid = floor((R+L)/2);
• Divido A in due sotto-array A[l .. mid] e A[mid+1 .. R];
• Il massimo sub-array deve trovarsi esattamente in una delle seguenti posizioni:
  • Interamente nel sotto-array di sx;
  • Interamente nel sotto-array di dx;
  • Che passa per il punto di mezzo.

Possiamo allora trovare i massimi sottoarray del sottoarray di sx e di dx in modo ricorsivo, in quanto questi due sotto-problemi sono istanze più piccole del problema di trovare un massimo sottoarray. Quindi, quello che rimane da fare è di trovare un massimo sottoarray che passa per il punto di mezzo e, fra i tre sottoarray, prendere quello con somma maggiore.

Massimo sotto-vettore passante per il centro

Find-Max-Crossing-SubArray(A, l, m, h)
left-sum = -inf
sum = 0
for i = m downto l
    sum = sum + A[i]
    if sum > left-sum
        left-sum = sum
        max-left = i
right-sum = -inf
sum = 0
for j = m + 1 to h
    sum = sum + A[j]
    if sum > right-sum
        right-sum = sum
        max-right = j
return(max-left, max-right, left-sum + right-sum)

Questa procedura opera nel seguente modo, il primo for trova il massimo sotto-array nella metà di sinistra. Poiché questo sottoarray deve contenere A[m], il ciclo for inizia con l’indice i a mid e procede per valori decrescenti dell’indice fino ad arrivare a l (low), cosicché ogni sottoarray che considererà è della forma A[i .. m]. Le prime 2 righe inizializzano le variabili left-sum, che contiene la somma più grande fino ad ora trovata, e sum, che contiene la somma degli elementi di A[i .. m]. Quando troviamo (riga 5) un sottoarray A[i .. m] con una somma maggiore di left-sum, aggiorniamo left-sum con la somma di questo sottoarray e poi aggiorniamo max-left, per memorizzare l’indice.

Il secondo ciclo for esegue, in modo duale, lo stesso procedimento sul sotto-array dx. Disponendo ora della procedura Find-Max-Crossing-SubArray, possiamo scrivere lo pseudocodice di un algoritmo divide ed impera per risolvere il problema del massimo sotto-array.

Trova il massimo sub-array

Find-Max-Subarray(A, l, h)
1 if h == l
2     return (l, h, A[l])
3 else
4     m = floor((l + h) / 2)
5     (left-l, left-h, left-sum) = Find-Max-Subarray(A, l, m)
6     (right-l, right-h, right-sum) = Find-Max-Subarray(A, m + 1, h)
7     (cross-l, cross-h, cross-sum) = Find-Max-Crossing-Subarray(A, l, m, h)
8     if (left-sum >= right-sum and left-sum >= cross-sum)
9         return (left-l, left-h, left-sum)
10    else if (right-sum >= left-sum and right-sum >= cross-sum)
11        return (right-l, right-h, right-sum)
12    else
13        return (cross-l, cross-h, cross-sum)

La chiamata iniziale di FIND_MAXIMUM-SUBARRAY(A, 1, A.length) troverà un massimo sottoarray di A[1 .. n]. Come FIND-MAX-CROSSINF-SUBARRAY, anche la procedura ricorsiva FIND-MAXIMUM-SUBARRAY restituisce una tupla contenente gli indici che delimitano un massimo sub-array, insieme con la somma dei valori di un massimo sottoarray. La riga 1 verifica il caso base, dove il sottoarray ha un solo elemento. Un sottoarray con un solo elemento ha un unico sottoarray – sé stesso – e quindi la riga 2 restituisce una tupla con gli indici iniziale e finale dell’unico elemento, insieme con il suo valore. Le righe 3-11 gestiscono il caso ricorsivo. La riga 3 esegue la parte divide, calcolando l’indice m nel punto di mezzo. Chiamiamo A[l .. m] il sottoarray sx e A[m+1 .. h] il sotto-array dx. Poiché adesso sappiamo che il sottoarray A[l .. h] contiene almeno due elementi, ciascuno dei sottoarray sx e dx deve avere almeno un elemento. Le righe 4-5 eseguono la parte impera, trovando ricorsivamente i massimi sottoarray all’interno dei sottoarray sx e dx, rispettivamente. Le righe 6-11 formano la parte combina. La riga 6 trova un massimo sottoarray che passa per il punto di mezzo. La riga 7 verifica se il sottoarray sx contiene un sottoarray con la somma massima e la riga 8 restituisce tale sottoarray, altrimenti, la riga 9 verifica se il sottoarray dx contiene un sottoarray con la somma massima, e la riga 10 restituisce tale sottoarray. Se nessuno dei due, sx e dx, contiene un sottoarray con la somma massima, allora un massimo sottoarray dovrà passare per il punto di mezzo, e la riga 11 lo restituisce.

D. Soluzione Lineare

Come ultima soluzione al problema, mostriamo un algoritmo che lo risolve in maniera lineare con costanti moltiplicative molto piccole (come poi si vedrà, questa versione è quella che è sempre preferibile come scelta).

Algoritmo Lineare

Linear(A, l, h)
1 int maxSum = -inf;
2 i = j
3 thisSum = 0;
4 for j = l to h
5     thisSum += A[j];
6     if thisSum > maxSum
7         maxSum = thisSum;
8         maxL = i;
9         maxR = j;
10    else if thisSum < 0
11        i = j + 1;
12        thisSum = 0;
return(maxL, maxR, maxSum);

L’algoritmo somma sequenzialmente tutti gli elementi dell’array mantenendo la somma massima trovata finora. Se la somma corrente diventa negativa, l’algoritmo la resetta e inizia a calcolare la somma dei successivi elementi.