Aplicação de Otimização por Enxame de Partículas Aprimorada na Solução do Problema da Árvore de Steiner Euclidiano no Rⁿ

Dado um conjunto fixo de pontos em um espaço N-dimensional (N≥3) com métrica euclidiana, o Problema da Árvore de Steiner Euclidiano no Rⁿ consiste em encontrar uma árvore de menor comprimento que ligue todos estes pontos usando, se necessário, pontos extras (pontos de Steiner).

A busca desta solução é um problema NP-difícil. Este trabalho apresenta uma meta-heurística modificada baseada em Otimização por Enxame de Partículas Aprimorada para o problema considerado.

Finalmente, experimentos computacionais comparam o desempenho da heurística proposta, considerando a qualidade da solução e o tempo computacional, em relação a trabalhos anteriores na literatura.

Dissertação apresentada ao Programa de Pós-Graduação em Modelagem Computacional de Sistemas, da Universidade Federal do Tocantins, como requisito parcial para obtenção do título de Mestre em Modelagem Computacional de Sistemas.