TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji，i，j=1，2，3，n）；2）非对称旅行商问题（dijdji，i，j=1，2，3，n）。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V=v1，v2，v3，vn的一个访问顺序为T=t1，t2，t3，ti，tn，其中tiV（i=1，2，3，n），且记tn+1=t1，则旅行商问题的数学模型为：minL=。TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标
