主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
邹鹏,周智,陈国良,顾钧.求解TSP问题的多级归约算法.软件学报,2003,14(1):35-42
求解TSP问题的多级归约算法
A Multilevel Reduction Algorithm to TSP
投稿时间:2001-07-17  修订日期:2001-12-27
DOI:
中文关键词:  TSP(traveling salesman problem)  NP-hard  部分解  归约  多级归约算法
英文关键词:TSP (traveling salesman problem)  NP-hard  partial tour  reduction  multilevel reduction algorithm
基金项目:(Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030403 (国家重点基础研究发展规划(973))
作者单位
邹鹏 中国科学技术大学,计算机科学技术系,安徽,合肥,230026
国家高性能计算中心,合肥,安徽,合肥,230026 
周智 中国科学技术大学,计算机科学技术系,安徽,合肥,230026
国家高性能计算中心,合肥,安徽,合肥,230026 
陈国良 中国科学技术大学,计算机科学技术系,安徽,合肥,230026
国家高性能计算中心,合肥,安徽,合肥,230026 
顾钧 中国科学技术大学,计算机科学技术系,安徽,合肥,230026
国家高性能计算中心,合肥,安徽,合肥,230026
香港科技大学,计算机科学与技术系,香港 
摘要点击次数: 3212
全文下载次数: 4629
中文摘要:
      TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.
英文摘要:
      The TSP (traveling salesman problem) is one of the typical NP-hard problems in combinatorial optimization problem. The fast and effective approximate algorithms are needed to solve the large-scale problem in reasonable computing time. The known approximate algorithm can not give a good enough tour for the larger instance in reasonable time. So an algorithm called multilevel reduction algorithm is proposed, which is based on the analysis of the relation of local optimal tour and global optimal tour of the TSP. The partial tour of the global optimal tour is obtained by a very high probability through simply intersecting the local optimal tours. Using these partial tours it could contract the searching space of the original problem, at the same time it did not cut the searching capability down, this is the so-called reduction theory. And then the scale of the instance could be reduced small enough by multi-reduction. Finally it could solve the small-scaled instance using the known best algorithm and get a good enough tour by putting the partial tours together. The experimental results on TSPLIB (traveling salesman problem library) show that the algorithm could almost get optimal tour every time for instance in reasonable time and thus outperformed the known best ones in the quality of solutions and the running time.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利