文章基本信息

标题：Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
本地全文：下载
作者：M. G. Dorzán ; E. O. Gagliardi ; M. G. Leguizamón 等
期刊名称：Journal of Computer Science and Technology
印刷版ISSN：1666-6046
电子版ISSN：1666-6038
出版年度：2010
卷号：10
期号：2
出版社：Iberoamerican Science & Technology Education Consortium
摘要：Globally optimal triangulations are difficult to be foundby deterministic methods as, for most type of criteria, nopolynomial algorithm is known. In this work, we considerthe Minimum Weight Triangulation (MWT) problem of agiven set of n points in the plane. Our aim is to showhow the Ant Colony Optimization (ACO) metaheuristiccan be used to search for globally optimal triangulationsof minimum weight. We present an experimental studyfor a set of instances for MWT problem. We createthese instances since no reference to benchmarks for thisproblem were found in the literature. We assess throughthe experimental evaluation the applicability of the ACOmetaheuristic for MWT problem
关键词：Triangulation; Minimum Weight Triangula-;tion; Computational Geometry; ACO Metaheuristic