Tra i classici problemi nello studio
degli algoritmi si può collocare di diritto quello sulla ricerca
dell’accoppiamento in un grafo. La sua importanza è dovuta al fatto
che, come problema, si presta molto alla ricerca di efficienti soluzioni.
Soluzioni che peraltro richiedono degli algoritmi, idee o strategie per
niente banali e che hanno sollecitato, più volte nel passato, a
delle vere e proprie conquiste concettuali. L’accoppiamento in un grafo
si presenta qualche volta come un’importante tassello per la risoluzione
di fondamentali problemi, spesso come subroutine di algoritmi più
ampi. Dopo il caso seriale, anche da un punto di vista computazionale parallelo
si è avuto un grande interesse per tale argomento e conseguentemente
sono stati formulati importanti teoremi ed elaborati algoritmi sempre più
efficienti. A differenza degli algoritmi sequenziali sull’accoppiamento
che sono di tipo combinatoriale, nel caso parallelo vengono spesso usati
il concetto di casualità e strumenti noti dell’algebra lineare.
L’ingrediente principale di questo nuovo approccio è senza dubbio
il teorema di Tutte permettendoci di stabilire che un grafo ammette un
accoppiamento perfetto se e solo se esiste una particolare matrice non
singolare di elementi indeterminati. Nei paragrafi seguenti verranno illustrati
algoritmi per la risoluzione del problema dell’accoppiamento massimale
per grafi generali e successivamente un algoritmo sull’accoppiamento perfetto
per grafi bipartiti. Entrambi gli algoritmi sono di tipo combinatoriale.
Successivamente verrà introdotto il problema dell’accoppiamento
perfetto nel caso di un grafo bipartito e quindi massimo e perfetto
nel caso generale di un grafo non bipartito elaborati però con un
metodo probabilistico. Questi ultimi casi hanno dato modo di sviluppare
importanti strumenti probabilistici utilizzati anche in altri tipi di problemi
come per esempio il lemma di Isolamento. In base ai modelli di macchine
e in base ai metodi di realizzazione si distinguono vari tipi di complessità.
L’attenzione prestata nei successivi paragrafi è ristretta ad algoritmi
di tipo NC e RNC. La classe NC per configurazioni parallele consiste
di problemi risolvibili in tempo polinomiale logaritmico. Il numero dei
processori per un problema di questo tipo varia anch’esso in modo polinomiale.
Si indicherà con NC2 la classe dei problemi risolvibile con circuiti
boolani uniformi di profondità e spazio polinomiale.
Analogamente per la classe NCk. Nella letteratura dei computer paralleli
si incontrano una grande quantità di modelli diversi. Spesso la
differenza è nei metodi di accesso alla memoria. Accesso di lettura
e scrittura organizzata in modo da evitare spiacevoli conseguenze di conflittualità.
Quindi modelli a partizione di memoria o modelli ad accesso casuale in
locazioni comuni. Comunque, la classe dei problemi paralleli NC in ogni
caso non cambia. Non è invece possibile affermare lo stesso per
le sotto classi NCk. Si parlerà di classe RNC cioè Random
NC quando i problemi sono risolvibili da circuiti probabilistici con profondità
polinomiale logaritmiche e tempo polinomiale.
Un algoritmo parallelo per l’Accoppiamento
Massimale
La strategia di questo algoritmo
è data da una elaborazione iterativa di varie fasi. In ogni fase,
viene trovato nel grafo corrente un "ampio" accoppiamento e successivamente
vengono cancellati i vertici accoppiati in modo da ottenere un nuovo grafo
pronto per la fase successiva. L’algoritmo termina la sua esecuzione quando
il grafo corrente è vuoto oppure quando questo possiede solo vertici
isolati. A questo punto, l’unione degli accoppiamenti trovati in ogni fase
costituisce l’accoppiamento massimale corrispondente al grafo di partenza.
In ogni fase, l’algoritmo sfoltisce gli archi accoppiati dal grafo corrente
finché ogni vertice ha al più grado 3. L’insieme dei vertici
di grado non nullo, detto S, forma un ricoprimento di G’ che rappresenta
il grafo appena potato dall’ultima fase. Da questo viene trovato un accoppiamento
M’ fra gli archi rimasti tale che |M'| >=|S|/4 . Su questo algoritmo una
prima limitazione è data dal numero di fasi eseguite. Per scoprire
questa complessità è utile il lemma seguente :
Lemma 1:
L’algoritmo richiede al più
O(logn) fasi.
Il prossimo algoritmo è la
descrizione di una fase del problema dell’accoppiamento massimale. Tale
fase consiste di iterazioni. In ogni iterazioni gli archi vengono
potati usando l’algoritmo del circuito di Eulero come subroutine.
Si indica con H il grafo all’inizio della iterazione e con
d(H) si denota il massimo grado di un vertice appartenente
ad H.
Algoritmo :
Passo 1: Si trova l’intero
k tale che .
Passo 2: Si trova l’insieme
dei vertici di H che hanno grado nel dominio
. Questi saranno chiamati vertici attivi.
Passo 3: Si costruisce
il grafo H’ formato da tutti gli archi di H che
sono
incidenti su almeno un vertice attivo.
Passo 4: Si riduce
H’ in un grafo di grado uniforme conglobando in un nuovo
vertice v* e un arco da esso un qualsiasi vertice di grado scompagnato.
Passo 5: Si trova un
circuito di Eulero in ogni componente connessa di H’.
Passo 6: Si eliminano
gli archi alternati del circuito in ogni componente
connessa e poi si cancella v*.
I circuiti di Eulero possono essere
trovati in O(log n) tempo usando O(m) processori
su una macchina di tipo CRCW-PRAM. In conclusione, l’algoritmo richiede
così O[ (log n)**3] tempo e O(m)
processori.
Teorema 1 (Tutte) :
Dato un grafo G=(V,E) ed A
la sua matrice di Tutte allora |A|<>0 se e solo se esiste un accoppiamento
perfetto in G.
Il teorema di Tutte è molto
utile per vedere se un dato grafo ammette un accoppiamento perfetto. La
difficoltà principale è che il determinante |A| può
avere molti termini esponenziali riducendo l’efficienza della computazione.
Il lemma seguente mostra che se le variabili sono sostituite da un ampio
e polinomiale insieme di interi allora con molta probabilità la
matrice sostituita sarà non singolare. Se |A|=0 allora si
dirà singolare.
Lemma 3 (Isolamento):
Sia (S,F) un sistema di insieme
ai cui elementi sono assegnati dei pesi di valore intero scelti uniformemente
e indipendentemente nell’intervallo [1,2n]. Allora la probabilità
che ci sia un unico insieme in F di peso minimo è alta :
Pr[unico insieme in F di peso minimo]>=1/2
.
Per calcolare |B| e
adj(B)
rispetto all’inversa 1/B si usa un noto algoritmo casuale d’inversione
della matrice. Per invertire una matrice nxn i cui ingressi
sono interi da m-bit occorre O[(log n)**2] tempo con
la necessità di O([(n)**3,5]m) processori.
Sebbene la versione sequenziale
di questo algoritmo è meno efficiente rispetto ad un convenzionale
algoritmo per l’accoppiamento, essa detiene il vantaggio di essere facile
da programmare specie se è già disponibile una subroutine
per l’inversione della matrice.
Discussione e problemi relativi
all’algoritmo parallelo per l’accoppiamento massimo
Nel paragrafo precedente si è
visto come trovare l’accoppiamento perfetto di peso minimo in un grafo
una volta assegnato il peso w(e) con l’arco e appartenente
ad E nel caso unario. Questo problema si può
considerare del tipo RNC2. Per quanto riguarda la complessità per
l’analogo problema sugli archi pesati nel caso binario non si è
ancora arrivati ad una stima precisa.
Il problema di trovare un accoppiamento
massimo in un grafo può essere così semplicemente ridotto
a cercare l’accoppiamento perfetto di peso minimo con dei ritocchi. Si
estende G con un grafo completo affidandosi a nuovi archi. Si assegna un
peso di valore 0 ad ogni arco di G e un peso di valore
1 ai nuovi archi. Dopodiché si ricerca l’accoppiamento perfetto
di peso minimo.
Per il problema dell’accoppiamento
con i vertici pesati si ha come ingresso il grafo ed un peso positivo
per ogni vertice. Il problema è quindi quello di trovare un
accoppiamento in per cui il peso dei vertici è massimo.
Si definisce peso dei vertici di un accoppiamento come la somma dei pesi
dei vertici che ricoprono l’accoppiamento. Da notare che l’accoppiamento
desiderato sarà massimo. Si esclude che non possa esserlo in quanto
eventualmente potrebbe essere aumentato in un massimo. La soluzione perciò
consiste di trovare il vettore di accoppiamento massimo più
pesante e un accoppiamento perfetto in . Questo ordinando i vertici
in ordine decrescente di peso.
L’algoritmo sull’accoppiamento massimo
visto precedentemente è detta soluzione di Monte Carlo. Il
senso di questa definizione è dovuto al fatto che tale algoritmo
qualche volta può dare una risposta sbagliata cioè può
calcolare un accoppiamento che non è massimo oppure può generare
un sottoinsieme di archi che non sono neanche accoppiati. L’intenzione
è quella di formulare un algoritmo parallelo che estende la risoluzione
di Monte Carlo. Una esecuzione che si basa su una limitazione superiore
della grandezza dell’accoppiamento massimo in un grafo. Questo algoritmo
produce un numero di uscite >= alla dimensione dell’accoppiamento
massimo e con alta probabilità la soluzione è corretta.
I due algoritmi possono essere avviati simultaneamente finché la
dimensione dell’accoppiamento trovato col primo algoritmo è in accordo
con il numero di uscite del secondo algoritmo. Questo è l’algoritmo
di Las Vegas ed elabora una soluzione in un tempo O[(log n)**2].
Praticamente, per trovare un accoppiamento
massimo in un grafo con un algoritmo parallelo di Monte Carlo lo spazio
limite superiore è dato da un tempo [O(log n)**2] e O[(n**2)M(n)]
processori.
|
Introduzione
/ Indice