Título: | ESTRATÉGIAS SEQÜENCIAIS E PARALELAS DE GRASP COM RECONEXÃO POR CAMINHOS PARA O PROBLEMA DE SÍNTESE DE REDES A 2-CAMINHOS | ||||||||||||||||||||||||||||||||||||
Autor: |
ISABEL CRISTINA MELLO ROSSETI |
||||||||||||||||||||||||||||||||||||
Colaborador(es): |
CELSO DA CRUZ CARNEIRO RIBEIRO - Orientador |
||||||||||||||||||||||||||||||||||||
Catalogação: | 09/JAN/2004 | Língua(s): | PORTUGUÊS - BRASIL |
||||||||||||||||||||||||||||||||||
Tipo: | TEXTO | Subtipo: | TESE | ||||||||||||||||||||||||||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||||||||||||||||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=4365&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=4365&idi=2 |
||||||||||||||||||||||||||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.4365 | ||||||||||||||||||||||||||||||||||||
Resumo: | |||||||||||||||||||||||||||||||||||||
Seja G= (V, E) um grafo não-orientado com custos não-
negativos em suas arestas e D um conjunto de pares
origem -
destino. Um 2-caminho entre nós (s,t)é um caminho de s a
t
formado por , no máximo, 2 arestas. O problema de síntese
de redes com 2-caminhos (2PNDP) consiste em encontrar um
subconjunto de arestas com custo mínimo que contenha um 2-
caminho entre as extremidades dea cada para origem-
destino
pertencente a D. Apicações deste problema encontram-se no
projeto de redes de comunicação, onde caminhos com poucas
arestas são desejáveis para garantir alta confiabilidade
e
pequenos atrasos. A metaheurística GRASP é um processo
multipartida para resolver problemas combinatórios, 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 número determinado de
iterações.Aplica-se a técnica de reconexão por caminhos
ao
final de cada iteração GRASP para melhorar a qualidade
das
soluções. Implementações paralelas de metaheurística são
muito robustas. A maior parte das implementações
paralelas
da metaheurística GRASP segue uma estratégia do tipo
independente , baseada na distribuição balanceada das
iterações pelos processadores. No caso de estratégias
colaboradtivas, os processadores trocam e compartilham
informações coletadas ao longo da trajetória que cada um
deles investiga. Neta tese são desenvolvidas heurísticas
seqüenciais e paralelas para 2PNDP. São analisadas
variantes e combinações de GRASP e reconexão por
caminhos , comparando-se os resultados obtidos pelos
algoritmos descritos na literatura. Heurísticas GRASP
paralelas com reconexão por caminhos são avaliadas e
comparadas para verificar qual o papel que a colaboração
entre os processadores desempenha na qualidade das
soluções
e nos tempos de processamento. Procura-se também estudar
a
melhor maneira de desenvolver implementações paralelas ,
para se utilizar da melhor forma possível os recursos
computacionais e reduzir conflitos de memória e
comunicação.
|
|||||||||||||||||||||||||||||||||||||
|