TSP冰晶算法

摘要：

TSP即旅行商问题,是一个典型的NP困难问题,随问题规模的增加,获得最优解的代价呈指数级增长.受自然智能的启发,冰晶算法首次模拟湖水降温时,湖面冰晶的生长过程,在亚稳态区内维持适宜的饱和度来尝试解决TSP问题.冰晶生长的过程就是TSP路径形成的过程,试验表明,这是一种快速有效的TSP问题近似算法,可在O(knlogn)时间复杂度下获得可行解,同时该算法适用于并行计算,可对开环、动态、大规模的TSP问题实时求解.

关键词：旅行商问题、冰晶、树枝晶、凸壳、非确定多项式

所属期刊栏目：3

分类号：TP301.5(计算技术、计算机技术)

资助基金：教育部科学技术研究重点项目207148

在线出版日期：2008-06-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：167-172