水流启发式算法求解Euclid TSP

摘要：

@@ 1.思想来源
旅行商问题(TSP)可以简单表述如下:给定一组N个城市和它们之间的两两距离,找出一个闭合的旅程,使得每个城市刚好经过一次且总的旅程距离最短.旅行商问题已经被证实是一个NP难解问题.虽然欧氏平面上的TSP有PTAS[4],但运算时间和精度呈指数函数关系,所以找一个快速的近似算法仍然具有很大的意义.

机标关键词：水流、启发式算法、求解、旅行商问题、运算时间、思想来源、欧氏平面、距离最短、近似算法、函数关系、城市、简单表、指数、精度、闭合

所属期刊栏目：29

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金19901009;广东省自然科学基金970472,000463;中国科学院软件研究所计算机科学重点实验室基金SYSKF0105

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

页数：共3页

页码：140-141,145