1. Inicio
  2. Atrás
Título: Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
Autores: Dorzán, María Gisela
Gagliardi, Edilma Olinda
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
Fecha: 2010-06-14
2010
Publicador: Unversidad Nacional de La Plata
Fuente:


Tipo: Articulo
Articulo
Tema: triangulación
triangulation;
triangulação de peso mínimo
triangulación de peso mínimo
geometría computacional
metaheurística ACO
minimum weight triangulation
ACO metaheuristic
computational geometry
geometria computacional
meta-heurística ACO
Ciencias Informáticas
Informática
Descripción: Globally optimal triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) problem of a given set of n points in the plane. Our aim is to show how the Ant Colony Optimization (ACO) metaheuristic can be used to search for globally optimal triangulations of minimum weight. We present an experimental study for a set of instances for MWT problem. We create these instances since no reference to benchmarks for this problem were found in the literature. We assess through the experimental evaluation the applicability of the ACO metaheuristic for MWT problem.
Idioma: Inglés