Fat Computational Complexity and Heuristic Design for the TSP
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The traveling salesman problem (TSP) is one of the classic NP-Hard combinatorial optimization problems. Efficient heuristics for the TSP have been the focus in research of computer science at all times. As a new tool to describe the structure of the TSP, the fat is essential for heuristic algorithm design. Since research on the fat is still at the beginning stage, It still lacks theoretical results and related heuristic algorithms. In this paper Firstly, the fat computational complexity for the TSP is investigated. It’s proved that it is NP-Hard to obtain the fat of the TSP through construction of biased instances, i.e., there is no algorithm to get the full fat of the TSP in polynomial time on the assumption P?NP. Furthermore, a meta-heuristic——dynamic candidate set search (DCSS) was proposed by analysis of the relationship between local optimal solutions and the fat. And the DCSS was applied to the LKH, one of the best existing algorithms for the TSP to improve it. Extensively wide experimental results on typical instances from the benchmark—TSPLIB indicate that the improved algorithm has a better performance than the LKH in terms of solution quality. This new fat-based heuristic shows a new way for other NP-hard problems.

    Reference
    Related
    Cited by
Get Citation

江贺,胡燕,李强,于红. TSP问题的脂肪计算复杂性与启发式算法设计.软件学报,2009,20(9):2344-2351

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 08,2008
  • Revised:July 02,2008
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063