Definizione
Il paradigma divide et impera anche conosciuto come divide and conquer consiste nella creazione di algoritmi che dividono il problema principale in sotto problemi di difficolta inferiore.
In particolare è possibile trovare tre fasi:
Fase 1 (divide)
La prima fase consiste nel dividere un problema dato in istanze o sottoproblemi più piccoli. Questo è ripetuto anche per i sotto problemi che verranno ulteriormente divisi in sottoproblemi più piccoli fino a raggiungere una fase in cui non sono più possibili ulteriori divisioni.
Fase 2 (impera)
La seconda fase consiste nel risolvere i sottoproblemi generati nella prima fase. Questa comporta la risoluzione di molti sottoproblemi in modo ricorsivo.
Tuttavia, a volte non è necessario risolvere i sottoproblemi poiché sono già segnati come risolti di per sé dopo la fase di divisione, vedi Programmazione Dinamica.
Fase 3 (combina)
La fase finale consiste nel combinare ricorsivamente le soluzioni dei sottoproblemi fino a raggiungere uno stadio in cui si ottiene una soluzione al problema originale.
Esempio (problema della selezione)
Data una lista A
di n
interi distinti, ed un intero k
, con , vogliamo sapere quale elemento occuperebbe la posizione k
se il vettore venisse ordinato.
Individuiamo alcuni casi particolari:
- Per abbiamo il minimo di
A
- Per avremo il massimo di
A
- Per avremo il mediano di
A
Soluzione Base
Una semplice soluzione con complessità è:
def sol1(A, k):
A.sort()
return A[k-1]
Vedremo che utilizzando un algoritmo che si basa sul paradigms divide et impera è possibile risolvere questo problema in .
Approccio basato sul divide et Impera:
- Scegliere nella lista
A
l’elemento in posizioneA[0]
che chiameremo perno. - Partendo dalla lista
A
costruiamo due listeA1
eA2
, la prima contiene gli elementi diA
minori del perno e la seconda i maggiori.
Dove si trova l’elemento di rango k
, ci sono tre casi:
- Se allora l’elemento di rango
k
è nel vettoreA1
. - Se allora l’elemento di rango
k
è proprio il perno. - Se allora l’elemento di rango
k
è inA2
, è l’elemento di rangok−|A1|−1
inA2
.
Quindi soltanto nel secondo casa abbiamo una risposta definitiva:
- Nel caso 1 dobbiamo richiamare l’algoritmo sulla lista
A1
invece cheA
. - Nel caso 2 dobbiamo richiamare l’algoritmo sulla lista
A2
inviteece cheA
ed in particolare il rango non sarà piùk
mak−|A1|−1
.
def selezione2(A,k):
if len(A) == 1: return A[0]
perno = A[0]
A1, A2 = [], []
for i in range(len(A)):
if A[i] < perno:
A1.append(A[i])
else:
A2.append(A[i])
if len(A1) >= k:
return selezione2(A1, k)
elif len(A1) == k-1:
return perno
return selezione2(A2, k - len(A1) - 1)
Costo Computazionale Caso Peggiore
Questa procedura che tripartisce la lista può però restituire una partizione massimamente sbilanciata in cui si ha ad esempio , |, questo accade quando il perno risulta l’elemento minimo nella lista.
Nel caso in cui questo evento sfortunato si ripete ad ogni partizione creata dall’algoritmo allora la complessità dell’algoritmo al caso pessimo è descritta da:
il cui risultato è
Costo Computazionale Generale
Più in generale il costo di questo algoritmo è rappresentato dalla seguente funzione:
Dove
m
è .Quindi se venisse sempre scelto un perno che garantisca un equilibrio fra le liste che crea l’algoritmo avremo che:
allora la complessità
T(n)
dell’algoritmo sarebbe:Naturalmente aspettarsi che il perno venga scelto sempre in una posizione tale da rendere le liste perfettamente bilanciate è irrealistico, potremmo allora accontentarci di chiedere che la scelta del perno garantisca partizioni non troppo sbilanciate come ad esempio quelle per cui:
In questo caso si ha che:
Che risulta ancora
Soluzione Probabilistica
Proviamo quindi a scegliere il perno a caso in modo equiprobabile tra gli elementi della lista, in questo modo anche se la scelta non produce una lista perfettamente bilanciata avremo comunque una complessità lineare.
def selezione2R(A, k):
if len(A)==1: return A[0]
perno = A[randint(0, len(A) - 1)]
A1, A2 = [], []
for x in A:
if x < perno:
A1.append(x)
elif x > perno:
A2.append(x)
if len(A1) >= k:
return selezione2R(A1, k)
elif len(A1) == k - 1:
return perno
return selezione2R(A2, k - len(A1) - 1)
Con questo algoritmo abbiamo che con alta probabilità il costo è lineare mentre al caso peggiore, che accade con una probabilità molto piccola è di . Per questo si dice che il costo medio è lineare.
Dimostrazione
Soluzione Deterministica
Per questo problema esiste una soluzione deterministico che garantisce una complessità anche per il caso pessimo.
Questo modo noto come mediano dei mediani, garantisce che il perno scelto produce sempre due sotto liste A1
e A2
, ciascuna delle quali ha non più di elementi.
L’algoritmo è basato sul paradigma divide et impera e segue questi passi:
- Divide l’insieme
A
, contenenten
elementi, in gruppi da 5 elementi ciascuno. L’ultimo gruppo potrebbe avere meno di 5 elementi. - Trova il mediano all’interno di ciascuno di questi gruppi.
- Calcola il mediano
p
dei mediani ottenuti al passo precedente. - Usa
p
come elemento pivot per l’insiemeA
.
Esempio
1) Si divide l’insieme in gruppi da 5 elementi (tranne ultimo):
2) Troviamo il mediano (si ordinano le sotto liste e si sceglie l’elemento centrale):
3) si calcola il mediano dei mediani, ripetendo ricorsivamente l’algoritmo, in questo caso essendo soltanto
4
mediani abbiamo un solo gruppo di4
elementi:
- , una volta ordinato
Quindi il perno è l’elemento
11
def selezione(A, k):
if len(A) <= 120:
A.sort()
return A[k - 1]
B = [sorted(A[5*i:5*i+5])[2] for i in range(len(A)//5)]
perno = selezione(B, ceil(len(A)/10))
A1, A2 = [], []
for x in A:
if x < perno:
A1.append()
elif x > perno:
A2.append()
if len(A1) >= k:
return selezione(A1, k)
elif len(A1) == k - 1:
return perno
return selezione(A2, k - len(A1) - 1)
Questo algoritmo quindi risolve il problema in modo lineare anche al caso pessimo, però a causa delle grandi costanti nascoste nell’, in realtà l’algoritmo probabilistico visto precedentemente si comporta meglio.