TSP冰晶算法

• 作者: 周蓝海 蔡东风
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: 旅行商问题 冰晶 树枝晶 凸壳 非确定多项式
• 年，卷（期）: 2008,（2）
• 页码范围: 167-172
• 页数: 6页
• 分类号: TP301.5
• 字数: 4890字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-4785.2008.02.012

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蔡东风	沈阳航空工业学院知识工程中心	105	916	14.0	27.0
2	周蓝海	沈阳航空工业学院知识工程中心	5	9	2.0	3.0