Ir para o conteúdo
GovBR

Autores

4735
Vinícius Leal do Forte
2095,44,878
4736
2095,44,878
4737
2095,44,878

Informações:

Publicações do PESC

Título
Algoritmos de Otimização Aplicados ao Problema de Steiner em N Dimensões.
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
1/2/2010
Resumo
O Problema de Steiner Euclidiano em n dimensões consiste em, dado um conjunto de pontos em um espaço euclidiano n-dimensional, encontrar a rede de tamanho mínimo que os interconecta, podendo ser adicionados pontos extras à rede. Existem diversos algoritmos exatos e heurísticos para a resolução do PSE para n=2. No entanto, poucos algoritmos foram desenvolvidos para n≥3. Nesta disertação, apresentamos novos algoritmos para o problema n-dimensional baseados na metaheurística Busca Local Iterativa (ILS) e em heurísticas de relaxação dinâmica anteriormente propostas na literatura. Resultados computacionais são apresentados e utilizados para analisar a qualidade das soluções produzidas pelos algoritmos.
Abstract
 The Euclidean Steiner Tree problem in n dimensions consists in, given a set of points in an n-dimesional Euclidean space, to find a network which spans these points with minimal length, being allowed to add extra points to the network. There exists several exact and heuristic algorithms to solve the PSE when n=2. However, only a few algorithms were developed for n≥3. In this dissertation, we present new algorithms for the n-dimensional problem which are based on the Iterated Local Search (ILS) metaheuristic and on a dynamic relaxation heuristic previously proposed in the literature. Computational results are presented and used to analyze the quality of the solutions produced by the algorithms.
Topo
Conteúdo acessível em Libras usando o VLibras Widget com opções dos Avatares Ícaro, Hosana ou Guga. Conteúdo acessível em Libras usando o VLibras Widget com opções dos Avatares Ícaro, Hosana ou Guga.