Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
Given a fixed set of points in a N-dimensional space (𝑁≥3) with Euclidean metric, the Euclidean Steiner Tree Problem in ℝ𝑛 consists on finding a minimum length tree that spans all these points using, if necessary, extra points (Steiner points). The finding of such solution is a NP-hard problem. This...
| Autor principal: | Costa, Wilson Wolf |
|---|---|
| Grau: | Dissertação |
| Idioma: | pt_BR |
| Publicado em: |
Universidade Federal do Tocantins
2019
|
| Assuntos: | |
| Acesso em linha: |
http://hdl.handle.net/11612/1304 |
| Resumo: |
|---|
|
Given a fixed set of points in a N-dimensional space (𝑁≥3) with Euclidean metric, the Euclidean Steiner Tree Problem in ℝ𝑛 consists on finding a minimum length tree that spans all these points using, if necessary, extra points (Steiner points). The finding of such solution is a NP-hard problem. This work presents a modified metaheuristic based on Improved Particle Swarm Optimization to the problem considered. Finally, computational experiments compare the performance of the proposed heuristic, considering solution’s quality and computational time, regard to previous works in the literature. |