X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
ALGORITMOS DISTRIBUÍDOS DE
EMPARELHAMENTO MÁXIMO EM GRAFOS UMA AVALIAÇÃO EXPERIMENTAL
Anna Dolejsi Santos, Ariel A. Fonseca, Gabriel Argolo M. R., Lúcia M. A. Drummond,
Melba L. Gorza, Rafael M. Savelli
{annads, afonseca, grocha, lucia, mgorza, rsavelli}@ic.uff.br
Instituto de Computação
Universidade Federal Fluminense
Resumo
Neste trabalho foram implementados e avaliados experimentalmente dois algoritmos distribuídos aproximados que solucionam o problema de emparelhamento de peso máximo. Eles foram
propostos e analisados teoricamente por Wattenhofer et al. e Hoepman. O primeiro emprega um
modelo síncrono e o segundo um modelo assíncrono. Como utilizamos um ambiente assíncrono
real com MPI para troca de mensagens, o primeiro algoritmo precisou ser modificado para executar
em tal ambiente. Para as instâncias utilizadas nos experimentos, observamos que os algoritmos distribuídos apresentaram, na prática, resultados bem melhores do que os determinados teoricamente.
Além disso, através da comparação com as soluções exatas, obtidas do algoritmo seqüencial proposto por Gabow, verificamos que esses mostraram-se como uma boa alternativa.
Palavras-chave:
Problema de Emparelhamento, Algoritmo Distribuído, Algoritmo Aproximado
Abstract
In this work we implemented and experimentally evaluated two distributed approximation algorithms for solving the maximum weighted matching problem. They were proposed and theoretically
analyzed by Wattenhofer et al. and Hoepman, the former adopts a synchronous model while the
second an asynchronous one. As we used an asynchronous real environment employing MPI for
message passing, the first one had to be changed to be executed in such environment. Regarding the
instances used in the experiments, we observed that distributed algorithms show in practice better
results than the theoretical ones. Furthermore, through comparison with the exact solutions, yielded
by the Gabow´s sequential algorithm, we verified they represent a promising alternative.
Keywords:
Matching Problem, Distributed Algorithm, Approximation Algorithm
XXXIX SBPO
[1771]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
1
Introdução
Um emparelhamento M (G) de um grafo G = (V, E), onde V representa o conjunto de vértices
e E representa o conjunto de arestas, é dado por um subconjunto de arestas E(G) que não possuem
extremidades em comum. Um grafo cujas arestas possuem um peso associado é denominado grafo
com peso. Assim, o peso de um emparelhamento é dado pela soma dos pesos de suas arestas.
Um emparelhamento M (G) de G possui peso máximo quando seu peso é o maior dentre todos os
emparelhamentos obtidos a partir do grafo G.
A técnica de emparelhamento é utilizada em aplicações de diferentes áreas do conhecimento.
Suas aplicações mais comuns são nos problemas de atribuições pessoais (tarefas e competências) e
de escalonamento. Ela é usada também em redes ópticas como em [NPZ03], onde o autor soluciona
o problema de maximização do número de pedidos atendidos utilizando emparelhamento. Esta técnica também é aplicada na estratégia para consultas em datawarehouse [MGR02], e para solucionar
o mapeamento de seqüências em uma estrutura protéica [Tay02].
Existem, na literatura, diversas soluções para o problema de emparelhamento de peso máximo
que apresentam algoritmos seqüenciais, tais como [Edm65a], [Edm65b], [Gab90], [GT91], [Gab76]
e [GMG86]. Poucos estudos foram propostos utilizando uma abordagem distribuída. Alguns algoritmos distribuídos trabalham com grafos que não associam pesos às arestas, como em [KS00],
[CHS02] e [II86]. Em [KS00], Karaata e Saleh apresentam um algoritmo para emparelhamento máximo em árvores com complexidade de tempo O(|V |4 ). Um algoritmo distribuído determinístico
para grafos bipartidos e gerais é apresentado em [CHS02]. O algoritmo para grafos bipartidos executa em tempo linear e o algoritmo para grafos gerais apresenta complexidade de tempo O(|V |2 ).
Um algoritmo randômico foi proposto em [II86], com complexidade de tempo O(log|V |).
Considerando grafos com peso, Uehara e Chen [UC00] apresentaram um algoritmo distribuído com complexidade de tempo O(∆), onde ∆ é o grau máximo do grafo. Wattenhofer et al.
[WW04] propôs um algoritmo distribuído 5-aproximado com complexidade de tempo O(log 2 |V |).
Em [Hoe04], Hoepman apresentou uma variação do algoritmo seqüencial guloso de [Pre99], 2aproximado e com complexidade de tempo O(|E|).
Verificamos que os algoritmos distribuídos existentes para grafos com peso apresentam soluções
aproximadas e, além disso, os resultados descritos são apenas teóricos. A complexidade de tempo
determinada em [WW04] e [Hoe04] não implica que os algoritmos consomem esse tempo todo,
apenas quer indicar que não consomem mais do que esse tempo. Na verdade, na prática, o tempo
de execução possivelmente é muito menor. Do nosso conhecimento, esses algoritmos são os que
resolvem o problema de emparelhamento de peso máximo de forma distribuída com as menores
complexidades.
Implementamos os algoritmos descritos em [WW04] e [Hoe04] em um ambiente distribuído
real usando MPI [BDV94] para a troca de mensagens. O primeiro emprega um modelo síncrono
e o segundo um modelo assíncrono. Como utilizamos um ambiente assíncrono real, o primeiro
algoritmo precisou ser modificado para executar em tal ambiente. Utilizamos, nos nossos experimentos, as instâncias de grafos da biblioteca TSPLIB [TSP95] e comparamos a qualidade das
soluções desses algoritmos com as do algoritmo seqüencial exato proposto por Gabow [Gab73].
Também avaliamos o tempo de execução e o número de mensagens trocadas, comparando-os com
as correspondentes complexidades de tempo e mensagens.
O restante do artigo está organizado da seguinte forma: na Seção 2 temos as descrições dos
algoritmos distribuídos propostos em [WW04] e [Hoe04] e do algoritmo seqüencial exato introduzido por Gabow [Gab73]. Na Seção 3 são apresentados os resultados experimentais, o ambiente de
testes e os grafos utilizados nos experimentos. Finalmente, a Seção 4 conclui este trabalho.
XXXIX SBPO
[1772]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Procedimento Emparelhamento-Grafo (G) : M
G(1) := G, MG := 0;
para (i de 1 até log n passo 1) faça
(1)
Hi := Validação (G(i) );
(i)
G(i+1) := G(1) ;
Hi
j := 1;
enquanto (dH (j) (u) > 0) faça
(j+1)
(j)
(j)
(Hi
, MH ) := Emparelhamento-Uniforme(Hi );
(j)
MG := MG U MH ;
j := j + 1;
fim-enquanto;
remove todas as arestas adjacentes a MG de G(i+1)
fim-para;
retorne MG
Figura 1: Procedimento Principal do Algoritmo de Wattenhofer
2
2.1
Algoritmos para emparelhamento de peso máximo em grafos gerais
Algoritmo distribuído randômico de Wattenhofer et al.
O algoritmo randômico de Wattenhofer et al. é síncrono, 5-aproximado, possui complexidade de
tempo O(log2 |V |) e de mensagem O(|V |2 log2 |V |). Um algoritmo síncrono é aquele que possui
uma base de tempo global, ou seja, no intervalo de tempo (denominado pulso) p = 0, o vértice envia mensagens a seus vizinhos e no pulso p ≥ 1 todas as mensagens enviadas no pulso anterior são
recebidas e os vértices podem processá-las e enviar novas mensagens. Desta forma, a comunicação
é realizada em pulsos e os atrasos durante a transmissão e as perdas das mensagens são desprezados.
Isto torna o desenvolvimento dos algoritmos mais simples, porém esse modelo é menos realístico.
Para ser utilizado em nossos testes, este algoritmo teve que ser adaptado para um ambiente assíncrono real, o que introduziu novas mensagens. Desta forma, sempre que um vértice precisa enviar
uma informação para um conjunto limitado de vizinhos, os vizinhos que não pertencem ao conjunto
devem receber uma mensagem de controle (nova mensagem criada para ambiente assíncrono).
O algoritmo é composto por duas fases principais, denominadas validação e emparelhamento
maximal, que são executadas log n vezes. Sua entrada é composta por um grafo G = (V, E) e a
cada iteração são executadas as duas fases citadas anteriormente, gerando um novo subgrafo que
será utilizado na próxima iteração. Após a execução das log n iterações têm-se o emparelhamento
M (G) do grafo G. O procedimento principal do algoritmo, na sua versão síncrona, é apresentado
na Figura 1.
A fase de validação funciona da seguinte maneira: na fase i do algoritmo é gerado um subgrafo Hi de G(i) , onde G(i) = G quando i = 1, ou seja, na primeira fase, que é composto por
todas as arestas candidatas válidas de G(i) . Uma aresta e = (u, v) é uma candidata se seu peso,
w(e), for maior ou igual à metade do peso da aresta mais pesada incidente ao vértice u, ou seja,
w(e) ≥ 21 .wmax (u)E . Uma aresta e será uma candidata válida apenas se ela for candidata para
ambos vértices u e v. A fase de validação é descrita na Figura 2. Note que no modelo síncrono,
apresentado em [WW04], a mensagem “you are a candidate” será enviada para um vértice selecionado como candidato. Na versão assíncrona proposta neste trabalho, mesmo quando o vértice não
é um candidato, este deve receber uma mensagem com a indicação “you are not a candidate”. Esta
adaptação torna possível a execução dos experimentos em um ambiente real. O subgrafo Hi gerado
na primeira fase do algoritmo será a entrada para a segunda fase que é denominada emparelhamento
XXXIX SBPO
[1773]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Procedimento Validação (G(i) ) : H
(i)
VH := VG ; EH := {};
S := {v | e = {u, v} ² G(i) , w(e) ≥ 12 .wmax (u)E (i) }
G
para todo vértice v ² S faça
envie mensagem “you are a candidate” para o vértice v;
fim-para;
receba mensagem de todos os vizinhos de v em G(i) ;
se (recebeu mensagem “you are a candidate” do vértice v ² S) então
EH := EH U {u, v}
fim-se;
retorne H
Figura 2: Fase de Validação
(j)
Procedimento Seleção (H (j) ) : HS
(j)
(j)
(j)
VHS := VH ; EHS := {}
(j)
escolha aleatoriamente uma aresta e = {u, v}, e ² EH , chame a aresta e por chosen;
(j)
(j)
EHS := EHS U {e};
envie mensagem “you are chosen” para o vértice v;
receba mensagem de todos os vizinhos w em H (j) ;
se (recebeu mensagem do vértice w) então
(j)
(j)
EHS := EHS U {u, v}; chame a aresta {u, w} por imposed;
fim-se;
(j)
retorne HS
Figura 3: Subfase de Seleção
maximal. Esta fase é composta pelas seguintes subfases: seleção, eliminação, emparelhamento e
limpeza.
Na subfase de seleção, cada vértice u escolhe aleatoriamente uma aresta e = (u, v) do conjunto
Hi (gerado a partir da fase anterior) denominando-a chosen. Após esta seleção, o vértice u envia
uma mensagem para o vértice v informando que ele foi escolhido, e recebe todas as mensagens dos
vértices w que o escolheram, marcando então as arestas e = (u, w) como imposed. As arestas chosen e imposed são adicionadas ao conjunto das arestas selecionadas HS . Nesta subfase também foi
inserida uma nova mensagem para a versão assíncrona do algoritmo: “not chosen”. A mensagem
“chosen” é enviada para um vértice escolhido aleatoriamente e a “not chosen” é enviada para os
demais vértices. A Figura 3 mostra o procedimento de seleção.
Na subfase de eliminação, uma aresta imposed é escolhida aleatoriamente do conjunto HS
e incluída no novo conjunto HP . Após isso, são adicionadas ao conjunto HP todas as arestas
e = (u, w) cujo vizinho w em HS enviou uma mensagem para o vértice u. A aresta chosen existente
em HS também é inserida no conjunto HP . A subfase de eliminação é descrita na Figura 4. A nova
mensagem “not imposed”, inserida na versão assíncrona do algoritmo, é enviada para todos os
vértices cujas arestas não foram selecionadas.
Na subfase de emparelhamento, uma aresta e = (u, v) é escolhida aleatoriamente em HP e
uma mensagem é enviada ao vértice v informando que ele foi escolhido como parceiro de emparelhamento. Caso o vértice u receba a mesma mensagem do vértice v, então o vértice u também
foi escolhido pelo vértice v para o emparelhamento, e assim, a aresta e = (u, v) será colocada no
conjunto das arestas emparelhadas M (G). A subfase de emparelhamento é apresentada na Figura
XXXIX SBPO
[1774]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
(j)
Procedimento Eliminação (HS ) : P (j)
(j)
(j)
(j)
VP := VHS ; EP := {};
escolha aleatoriamente uma aresta imposed e = {u, v};
envie mensagem “this edge is in P (j) ” para o vértice v;
(j)
(j)
EP := EP U {e};
(j)
receba mensagem de todos os vizinhos w em HS ;
se (recebeu mensagem do vértice w) então
(j)
(j)
EP := EP U {u, w};
fim-se;
retorne P (j)
Figura 4: Subfase de Eliminação
(j)
Procedimento Emparelhamento (P (j) ) : MG
(j)
MG := {};
escolha aleatoriamente uma aresta incidente e = {u, v} em P (j) ;
envie mensagem “you are my matching partner” para o vértice v;
receba mensagem de todos os vizinhos w em P (j) ;
se (recebeu mensagem do vértice v) então
(j)
(j)
MG := MG U {e};
fim-se;
(j)
retorne MG
Figura 5: Subfase de Emparelhamento
Procedimento Limpeza (H (j) ) : H (j+1)
H (j+1) := H (j)
(j)
(j)
remova todas as arestas e ² MH de H (j+1) , EH (j+1) := EH \EM (j)
(j)
H
remova todas as arestas adjacentes a uma aresta em MH de H (j+1) ;
(j)
EH (j+1) := EH (j+1) \{e | e é adjacente em MH };
Retorne H (j+1)
Figura 6: Subfase de Limpeza
5. Observamos que no modelo síncrono, descrito em [WW04], a mensagem “you are my matching
partner” nem sempre é enviada. Na versão assíncrona, mesmo quando o vértice não é um candidato a emparellhamento, este deve receber uma mensagem com uma indicação “you are not my
matching partner”.
A última etapa é a execução da subfase de limpeza, onde todas as arestas existentes no emparelhamento M (G) e todas as arestas adjacentes a uma aresta em M (G) são removidas do conjunto
Hi . O procedimento de limpeza é descrito na Figura 6. Foram inseridas as mensagens “matching”
e “not matching”, na versão assíncrona do algoritmo. A mensagem “matching” é enviada por um
vértice a todos os outros quando este encontra-se emparelhado, caso contrário ele envia a mensagem
“not matching”.
O novo subgrafo gerado após a execução das duas fases de validação e emparelhamento maximal é usado como entrada para as mesmas. Este procedimento é repetido log n vezes.
XXXIX SBPO
[1775]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
R := {}
N := T (v )
c := candidato(v, N )
se c # {} então envie mensagem “req” para o vértice c
enquanto N # {} faça
receba mensagem m de u
se m = “req” então R := R U {u}
se m = “drop” então N := N \{u}
se u = c então c :=candidato(v, N )
se c # {} então envie mensagem “req” para c
se c # {} ∧ c ² R então para todo w ² N \{c} envie mensagem “drop” para w
N := {}
{se c # {} então (v, c) ² M }
Figura 7: Algoritmo Distribuído Guloso
2.2
Algoritmo distribuído guloso de Hoepman
Este algoritmo é uma derivação do algoritmo seqüencial proposto em [Pre99]. Ele é 2-aproximado e possui complexidades de tempo O(|E|) e de mensagens O(|V |).
O algoritmo funciona da seguinte maneira: inicialmente todos os vértices constroem um conjunto que incluem todos os seus vizinhos. Cada vértice seleciona a aresta incidente de maior peso
e envia uma mensagem “req” ao vizinho. Quando um vértice recebe uma mensagem “req” do
vizinho para o qual já tinha enviado a mesma mensagem, a aresta é marcada como pertencente ao
emparelhamento e ele envia a mensagem “drop” para todas as outras arestas incidentes. Ao receber
uma mensagem “drop” de um vizinho para o qual tinha enviado “req”, o vértice seleciona outro
vizinho cuja aresta incidente possui o maior peso, e repete os passos anteriores. O algoritmo termina a execução em cada vértice quando este já emparelhou ou não tem mais vizinhos para tentar
emparelhar. A Figura 7 apresenta o algoritmo.
2.3
Algoritmo seqüencial exato de Gabow
O algoritmo proposto em [Gab73] é uma implementação eficiente do algoritmo de Edmonds
[Edm65b], que é baseado no algoritmo de emparelhamento de cardinalidade máxima descrito em
[Edm65a]. O primeiro possui complexidade de tempo O(|V |3 ), enquanto o algoritmo apresentado
em [Edm65b] possui complexidade O(|V |4 ). O algoritmo constrói um emparelhamento inicial
aplicando o método guloso. Os vértices desemparelhados são chamados livres. Para cada vértice
livre é construída uma árvore de caminhos alternantes, ou seja, caminho composto por uma aresta
desemparelhada seguido por outra emparelhada. O emparelhamento do grafo é aumentado quando
um caminho aumentante é encontrado, ou seja, quando a árvore construída alcança um novo vértice
livre. Quando não existirem vértices livres no grafo modificado então o algoritmo é finalizado.
Para detectar caminhos alternantes de peso máximo, o algoritmo realiza transformações no peso
dos vértices durante a busca de caminhos aumentantes. Devido ao limite do número de páginas,
nós apresentamos somente uma breve descrição do algoritmo. Maiores detalhes são encontrados
em [Gab73].
3
Resultados Experimentais
Nesta seção são apresentados os resultados dos experimentos realizados em um ambiente real
utilizando os algoritmos descritos na seção anterior. Os grafos utilizados nos testes foram obtidos
XXXIX SBPO
[1776]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Host
Máquina 1
Máquina 2
Máquina 3
Máquina 4
Máquina 5
Processador
Pentium 4 2.8Ghz
Pentium 4 2.8Ghz
Pentium 4 2.8Ghz
AMD Athlon 1.4Ghz
AMD Athlon 1.4Ghz
Memória
512MB
512MB
512MB
256MB
256MB
Kernel
Fedora Core 2 kernel 2.6.8-1
Fedora Core 2 kernel 2.6.8-1
Fedora Core 2 kernel 2.6.8-1
Fedora Core 4 kernel 2.6.9-1
Fedora Core 4 kernel 2.6.15-1
Mpilam
7.0.4
7.0.4
7.0.4
7.0.6
7.0.6
Tabela 1: Configuração das Máquinas
Figura 8: Competitividade x Tamanho do Grafo
da biblioteca TSPLIB [TSP95].
O ambiente de testes utilizado é composto por cinco máquinas heterogêneas não dedicadas,
com sistema operacional Linux, utilizando o middleware MPILAM [BDV94] para troca de mensagens. A configuração das máquinas é mostrada na Tabela 1. Os grafos utilizados possuem entre
14 e 318 vértices. Para cada vértice foi criado um processo no ambiente MPI. Três critérios foram
utilizados para avaliação dos algoritmos: a qualidade da solução, ou seja, o peso máximo obtido no
emparelhamento, o tamanho da maior cadeia causal de mensagens enviadas e o número de mensagens trocadas. A definição de cadeia causal de mensagens pode ser entendida como uma seqüência
de mensagens do tipo “recebi uma mensagem e enviei outra em conseqüência”. Essa medida foi
utilizada para analisarmos o tempo global dos algoritmos distribuídos assíncronos desenvolvidos.
Foram realizadas três execuções para cada grafo. Como o tempo de execução considerado é o
tamanho da cadeia causal, não faz diferença o sistema estar dedicado.
Como o algoritmo em [Gab73] é seqüencial, apenas o primeiro critério pôde ser contabilizado.
Apesar do algoritmo [WW04] não garantir o término de sua execução, todos os casos testados
apresentaram uma solução.
Na Tabela 2, a primeira coluna descreve o nome da instância TSPLIB utilizada com o número
de vértices de cada grafo, nas colunas seguintes são apresentados o custo do emparelhamento, o número de mensagens e o tamanho da maior cadeia causal. O custo do emparelhamento é apresentado
para os três algoritmos. Utilizamos o resultado do algoritmo ótimo seqüencial como referência para
análise da qualidade das soluções dos algoritmos distribuídos. O número de mensagens e tamanho
da maior cadeia causal só fazem sentido para os algoritmos distribuídos.
Observamos que os algoritmos distribuídos apresentaram, para as instâncias testadas, um bom
desempenho quando comparados com o algoritmo seqüencial ótimo de Gabow [Gab73]. O algo-
XXXIX SBPO
[1777]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Figura 9: Tamanho da Cadeia Causal x Tamanho do Grafo
ritmo de Hoepman [Hoe04] alcançou, em média, 98, 77% do emparelhamento obtido pelo algoritmo ótimo. Já o algoritmo de Wattenhofer [WW04] obteve, em média, 91, 07% do emparelhamento ótimo. Note que o algoritmo de Hoepman é 2-aproximado e o algoritmo de Wattenhofer
é 5-aproximado. Utilizamos a “competitividade”, a razão entre o custo da solução obtida com o
algoritmo distribuído e o custo da solução ótima obtida pelo algoritmo seqüencial, para comparar
a qualidade das soluções dos dois algoritmos distribuídos. A Figura 8 apresenta a competitividade
em relação ao tamanho do grafo.
A Figura 9 mostra o tamanho da maior cadeia causal dos algoritmos distribuídos em relação ao
número de vértices dos grafos. Durante a realização dos testes não observamos variações na cadeia
causal superiores a 5%. Verificamos que o algoritmo proposto por Hoepman possui tamanho da
maior cadeia causal ascendente de acordo com o aumento do número de vértices do grafo.
O tempo de execução do algoritmo foi proporcional a |V | e a complexidade de tempo é O(|E|).
Como as instâncias utilizadas nos testes são grafos completos, é possível concluir que o tempo de
execução é bem menor do que a complexidade correspondente. Nos experimentos realizados com
o algoritmo de Wattenhofer, o tempo de execução obtido foi praticamente constante enquanto a
complexidade é O(log2 |V |).
A complexidade de tempo do algoritmo de Hoepman é pior do que a do algoritmo de Wattenhofer devido à quantidade de candidatos selecionados a emparelhar a cada iteração. No algoritmo de
Wattenhofer, um vértice seleciona os candidatos baseado no peso das arestas, ou seja, uma aresta
e = (u, v) é candidata se seu peso é maior ou igual à metade do peso da aresta mais pesada incidente ao vértice u. Assim, a cada iteração, pode-se ter mais de uma aresta candidata a emparelhar.
Já no algoritmo de Hoepman, apenas um vértice é escolhido, a cada iteração, como candidato a
emparelhar. A Figura 10 mostra o número de mensagens enviadas durante a execução em relação
ao tamanho do grafo.
Percebemos que, ao contrário do comportamento visto em relação à cadeia causal, o número
de mensagens enviadas pelo algoritmo de Wattenhofer cresce consideravelmente à medida que o
número de vértices do grafo aumenta. Isso acontece devido ao processo de seleção das arestas
candidatas, ao refinamento da solução final de emparelhamento e também pela inserção de novas
mensagens para a execução em um ambiente assíncrono real. Porém, no caso do algoritmo de
Hoepman cada vértice envia apenas uma mensagem a cada iteração do algoritmo, que é enviada
para o vértice vizinho conectado pela aresta de maior peso. Nos experimentos realizados, o número
de mensagens trocadas nas execuções dos algoritmos distribuídos foi proporcional a |V |2 , enquanto
XXXIX SBPO
[1778]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Grafo
burma14.tsp
ulysses16.tsp
ulysses22.tsp
Bayg29.tsp
swiss42.tsp
att48.tsp
eil51.tsp
berlin52.tsp
brazil58.tsp
st70.tsp
eil76.tsp
pr76.tsp
gr96.tsp
Rat99.tsp
kroA100.tsp
kroB100.tsp
kroC100.tsp
kroD100.tsp
kroE100.tsp
rd100.tsp
eil101.tsp
Lin105.tsp
pr107.tsp
pr124.tsp
bier127.tsp
ch130.tsp
pr136.tsp
gr137.tsp
pr144.tsp
ch150.tsp
kroA150.tsp
kroB150.tsp
pr152.tsp
U159.tsp
Rat195.tsp
D198.tsp
kroA200.tsp
kroB200.tsp
gr202.tsp
ts225.tsp
Tsp225.tsp
pr226.tsp
gr229.tsp
pr264.tsp
A280.tsp
pr299.tsp
lin318.tsp
linhp318.tsp
Gabow
4616
8255
11048
3311
3342
35190
1167
19856
96245
2660
1789
408076
270994
6136
126668
123566
127368
118732
128225
40984
2467
89421
462834
517712
420323
33713
623442
470823
600950
39255
191015
192662
747931
333213
16693
129823
254443
245530
182690
1163762
29680
1280811
1006093
909952
25291
565536
430187
430187
Emparelhamento
Hoepman Wattenhofer
4488
4366
8092
8071
10837
9898
3244
3091
3273
3044
34239
32342
1162
1053
19079
17836
89661
84411
2634
2372
1775
1607
402127
380221
266890
251286
6110
5791
124874
119275
122162
112182
125611
119128
117275
112111
126903
118562
40138
36572
2438
2257
88716
84388
462431
421297
498818
467284
411681
390341
33127
30954
617764
555630
465803
451618
590380
517346
39029
34750
189272
178200
190413
182230
739398
673527
328994
300557
16671
15808
127525
122843
252709
237089
243701
227994
178698
171483
1163758
1048022
29469
27448
1261340
1137336
988532
904838
906478
821930
25178
23473
560857
544669
426505
387488
426505
396514
Mensagem
Hoepman Wattenhofer
215
740
299
1079
552
2636
924
4322
1970
8612
2545
11410
2780
10248
3009
12250
3734
15219
5239
25962
6228
26838
6289
24437
9830
42820
10759
40568
10896
46928
10887
45827
10853
44156
10853
51922
10862
49244
10575
48189
10933
48522
12225
51570
12299
57838
16721
76835
17828
78662
18109
74942
19718
89072
20679
84490
22383
106071
23847
104547
24284
103306
24287
105836
25280
107741
26995
116802
41138
172472
44138
219736
42811
187260
42793
182732
44032
230884
53686
247296
54414
216888
55178
257352
56175
253110
74350
363560
83297
391845
96771
396634
107207
466996
107161
477682
Cadeia Causal
Hoepman Wattenhofer
16
17
17
22
23
27
32
22
53
36
56
36
55
23
58
37
62
41
73
27
80
35
80
38
112
35
102
32
106
36
109
36
124
32
110
40
114
32
108
36
108
29
121
47
121
33
162
35
156
41
141
33
139
29
154
43
161
33
160
33
178
33
185
29
173
36
183
39
235
30
243
47
219
40
237
34
225
50
270
38
277
37
279
36
252
44
295
39
311
41
362
48
345
53
356
48
Tabela 2: Resultados dos Algoritmos Distribuídos e do Algoritmo Seqüencial
XXXIX SBPO
[1779]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Figura 10: Número de Mensagens x Tamanho do Grafo
Figura 11: Comparação por Tipo de Mensagem do Algoritmo de Hoepman
que os resultados teóricos apresentam complexidades de mensagem O(|V |2 ) e O(|V |2 log2 |V |)
para os algoritmos de Hoepman e Wattenhofer, respectivamente. Ou seja, mesmo com a introdução
de novas mensagens no algoritmo de Wattenhofer, o número de mensagens trocadas foi menor do
que a complexidade descrita. Apresentamos nas Figuras 11 e 12 o percentual dos diferentes tipos
de mensagens enviadas por cada um dos algoritmos distribuídos.
O algoritmo de Hoepman possui dois tipos de mensagens, “req” e “drop”. Foram utilizadas três
instâncias da TSPLIB, que contém respectivamente 48, 150 e 318 vértices. Elas foram utilizadas por
possuírem um número pequeno, médio e grande de vértices. Nota-se que o número de mensagens
do tipo “drop” é muito maior que as do tipo “req”. Isto ocorre, pois cada vértice envia apenas uma
mensagem “req” a cada iteração, ou seja, o número de mensagens “req” que cada vértice envia
pode ser no máximo, o número de vizinhos do mesmo. Por outro lado, ao emparelhar, o vértice
envia uma mensagem “drop” para cada um de seus vizinhos. Para melhorar a complexidade de
mensagens deste algoritmo deve-se diminuir o número de mensagens “drop” enviadas.
A Figura 12 mostra a comparação entre os tipos de mensagens trafegadas no algoritmo de
Wattenhofer. Foram usadas as mesmas três instâncias descritas na Figura 11. Verificamos que as
mensagens “matching” e “not_matching” são predominantes, sendo que elas não existem no algoritmo síncrono original e foram introduzidas nos experimentos para execução em um ambiente
assíncrono real. A predominância dessas mensagens deve-se ao fato do algoritmo utilizar um refinamento do grafo para realizar o emparelhamento, que é feito durante a subfase de limpeza. Nesta
subfase cada vértice envia mensagens aos vizinhos informando se ele emparelhou ou não. O vértice
que não emparelhou deve participar do refinamento da próxima iteração. O algoritmo [WW04] foi
executado três vezes para cada instância de grafo resultando em uma variação em torno de 6% entre
os emparelhamentos obtidos.
XXXIX SBPO
[1780]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Figura 12: Comparação por Tipo de Mensagem do Algoritmo de Wattenhofer
4
Conclusões
Neste trabalho, observamos que os algoritmos distribuídos apresentaram na prática resultados
bem melhores do que os determinados teoricamente. O algoritmo proposto por Hoepman apresentou melhores resultados do que o algoritmo distribuído randômico de Wattenhofer. Considerando a
qualidade da solução, o algoritmo de Hoepman alcançou, em média, 98, 77% do emparelhamento
obtido pelo algoritmo ótimo. Já o algoritmo de Wattenhofer obteve, em média, 91, 07% do emparelhamento ótimo. O tempo de execução do algoritmo de Hoepman verificado experimentalmente
foi proporcional a |V |, enquanto a complexidade é O(|E|). Nos experimentos realizados com o
algoritmo de Wattenhofer obtivemos tempo de execução praticamente constante enquanto a complexidade é O(log2 |V |). Ao analisarmos a quantidade de mensagens trocadas pelo algoritmo de
Hoepman, verificamos que os resultados obtidos experimentalmente corresponderam à medida teórica O(|V |2 ). No algoritmo de Wattenhofer, tivemos que introduzir novas mensagens para adaptar
o algoritmo síncrono ao ambiente assíncrono real. Mesmo com esta adaptação, o número de mensagens trocadas nas execuções foi proporcional a |V |2 enquanto a complexidade é O(|V |2 log2 |V |).
Os algoritmos distribuídos para o problema de emparelhamento de peso máximo na prática se
mostraram uma boa alternativa, nas instâncias testadas, em relação ao método seqüencial, considerando que produziram soluções de boa qualidade em tempos razoáveis. Como continuação desse
trabalho, estamos desenvolvendo um algoritmo distribuído para fornecer a solução exata para este
problema.
Referências
[CHS02] Chattopadhyay, Subhendu; Higham, Lisa; Seyffarth, Karen (2002). Dynamic and selfstabilizing distributed matching. In Proceedings of the Annual ACM Symposium on Principles
of Distributed Computing (PODC), 290-297.
XXXIX SBPO
[1781]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
[Edm65a] Edmonds, Jack (1965). Paths, trees and flowers. Canadian Journal of Mathematics, 17,
449-467.
[Edm65b] Edmonds, Jack (1965). Maximum matching and a polyhedron with 0,1 - vertices. Journal of Research of the National Bureau of Standards, 69B, 125-130.
[Gab73] Gabow, Harold (1973). Implementation of algorithms for maximum matching on nonbipartite graphs. Tese de Doutorado Comput. Sci. Dep., Stanford University.
[Gab76] Gabow, Harold (1976). An efficient implementation of Edmonds’ algorithm for maximum
matching on graphs. J. Assoc. Comput. Mach., 23(2), 221-234.
[Gab90] Gabow, Harold (1990). Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 434-443.
[GT91] Gabow, Harold; Tarjan, Robert E. (1991). Faster scaling algorithms for general graph matching problems. Journal of the ACM, 38(4), 815-853.
[GMG86] Galil, Zvi; Micali, Silvio; Gabow, Harold (1986). An O(EVlog V ) algorithm for finding
a maximal weighted matching in general graphs. SIAM J. Comput., 15(1), 120-130.
[Hoe04] Hoepman, Jaap-Henk (2004). Simple distributed weighted matchings. eprint
cs.DC/0410047.
[II86] Israeli, Amos; Itai, Alon (1986). A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters, 22, 77-80.
[KS00] Karaata, Mehmet; Saleh, K. (2000). A distributed self-stabilizing algorithm for finding
maximal matching. Computer Systems Science end Engineering, 3, 175-180.
[MGR02] Melnik, Sergey; Garcia-Molina, Hector; Rahm, Erhard (2002). Similarity flooding: a
versatile graph matching algorithm and its application to schema matching. In Proceedings of
the IEEE CS International Conference on Data Engineering, 117-140.
[NPZ03] Nomikos, Christos; Pagourtzis, Aris; Zachos, Stathis (2003). Satisfying a maximum number of pré-routed requests in all-optical ring. Computer Networks, 42, 55-63.
[Pre99] Preis. Robert (1999). Linear time 21 approximation algorithm for maximum weighted matching in general graphs. Symposium on Theoretical Aspects of Computer Science. STACS 99,
LNCC 1563, Springer, 259-269.
[Tay02] Taylor, William (2002). Protein structure comparison using bipartite graph matching and
its application to protein structure classification. Molecular & Cellular Proteomics 1(4), 334339.
[TSP95] Reinelt, Gerhard (1995). http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html
[UC00] Uehara, Ryuhei; Chen, Zhi-Zhong (2000). Parallel approximation algorithms for maximum weighted matching in general graphs. Information Processing Letters, 76, 13-17.
[WW04] Wattenhofer, Mirjam; Wattenhofer, Roger (2004). Distributed weighted matching. In:
18th DISC, LNCS 3274, Springer, 335-348
XXXIX SBPO
[1782]