Busca em arvore geradora minima de forma paralela

Implementação Paralela de uma Metaheurística GRASP com
Path-Relinking para o Problema da Árvore Geradora de Custo
Mínimo com Grupamentos
Fabiano Vieira de Alvarenga1, Marcelo Lisboa Rocha1
Marluce Rodrigues Pereira2
1

Departamento de Ciência da Computação – Fundação UNIRG
Alameda Madrid Nº 545, Jardim Sevilha, CEP 77410-470, Gurupi – TO – Brasil
{fabianovieiraa, marcelolisboarocha}@yahoo.com.br
2

Departamento de Ciência da Computação – UFLA
Caixa Postal 37, CEP 37200-000, Lavras – MG – Brasil [e-mail] Resumo
A metaheurística GRASP é um processo iterativo, cujas iterações consistem de duas fases: uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um determinado número de iterações. Neste trabalho, a metaheurística GRASP é aplicada conjuntamente à técnica path-relinking a um problema variante da
Árvore Geradora Mínima (AGM), denominado
Árvore Geradora de custo Mínimo com Grupamentos
(AGMG). O objetivo é reduzir o tempo computacional e melhorar a qualidade das soluções GRASP através de uma implementação paralela desta metaheurística.
Os resultados obtidos mostraram speedup linear para esta implementação.

1. Introdução
Os problemas de otimização combinatória possuem alta complexidade em sua solução, sendo em geral
NP-Difíceis. Assim sendo, não é interessante a aplicação de técnicas exatas para solução de todos os problemas de otimização, principalmente quando se considera instâncias de grandes dimensões [4]. Assim, é comum a utilização de técnicas heurísticas ou metaheurísticas, tais como Algoritmos Genéticos [6] e
Greedy Randomized Adaptive Search Procedure
(GRASP) [3], para resolvê-los.
As metaheurísticas consistem em um processo iterativo ou refinamento de solução de problema que buscam organizar e direcionar heurísticas subordinadas, pela combinação de diferentes

conceitos. Podem manipular uma solução completa, incompleta ou um conjunto de