论文部分内容阅读
0引言旅行商问题(Traveling Salesman Problem:TSP)是十分重要的组合优化问题,它在计算机科学、运筹学及工程等领域都有着广泛的应用.巡回旅行商问题即给定一组N个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短.用图语言描述即是:给一个图G=(~ E),每边e∈E上有非负权值ω(e),寻找G的Hamilton圈C,使得C的总权W(C)=(?)ω(e)最小.TSP问题是一个典型
0 Introduction Traveling Salesman Problem (TSP) is a very important combinatorial optimization problem, and it has a wide range of applications in computer science, operations research and engineering, etc. The traveling salesman problem is to give a set of N cities and The direct distance between them, looking for a closed journey, so that each city just happened once and the total travel distance of the shortest.Described in graph language is: to a graph G = (~ E), each edge e ∈ There is a nonnegative weight ω (e) on E and a Hamilton cycle C of G such that the total weight W (C) = (ω) ω (e) of C. The TSP problem is a typical