水流启发式算法求解Euclid TSP  

A Water-Flow Heuristic Algorithm to Euclid TSP

作　　者：郝志峰[1] 刘海[1] 林智勇[1] 

机构地区：[1]华南理工大学应用数学系

出　　处：《计算机科学》2002年第7期140-141,145,共3页Computer Science

基　　金：国家自然科学基金(19901009); 广东省自然科学基金(970472;000463); 中国科学院软件研究所计算机科学开放实验室(SYSKF0105)资助项目

摘　　要：1.思想来源旅行商问题(TSP)可以简单表述如下:给定一组N个城市和它们之间的两两距离,找出一个闭合的旅程,使得每个城市刚好经过一次且总的旅程距离最短。旅行商问题已经被证实是一个NP难解问题。虽然欧氏平面上的TSP有PTAS,但运算时间和精度呈指数函数关系,所以找一个快速的近似算法仍然具有很大的意义。近年来提出的逼近最优解的算法如遗传算法、模拟退火算法、神经网络算法本质上都是进行随机搜索,本文是用确定性的启发式算法求解TSP。This paper is enlightened by the surface tension in the process of water-flow, Firstly, it constructs a protruding polygon which passes through some points, and adds other points to the loop according to multifarious heuristic information one by one. The results show the algorithm can approach optimal answer well in a minute. Additionally , we obtain two optimal loop theorem of TSP under certain conditions, and prove them to provide the theoretical base of the algorithm.

关 键 词：旅行商问题 水流启发式算法 EuclidTSP NP问题 

分 类 号：O224[理学—运筹学与控制论]