TSP问题算法小软件 5.0

TSP，即Traveling Salesman Problem，也就是旅行商问题，又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出。

TSP问题算法小软件数学模型简介

“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法，在大型计算机的帮助下才取得了一些进展[1] 。 TSP问题 TSP问题

TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。

TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为(n-1)。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。

旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。

旅行推销员的问题，我们称之为巡行(Tour)，此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。

TSP问题算法小软件更新日志

1.质点坐标是屏幕像素坐标，left,top,纵坐标向下不是向上，与数学上的纵坐标方向相反。

2.坐标为屏幕像素坐标，所以只能整数。

3.点坐标可以用鼠标拖动，拖动时可以超出屏幕范围自动产生滚动条，但点坐标不可以为负数。

本次升级5.0主要修改如下：

1。增加了concorde算法。附带有原作者的开源ansi-C源代码和文件。

2。将原来隐藏的穷举法分支限界法中的初始值可以手工输入框显示出来。

本次升级4.0主要修改如下：

1。增加了LKH算法。

2。附带有LHK原作者的开源C++源代码和4个PDF文件。

本次升级3.7主要修改如下：

1。增加了模拟退火算法。

2。分支限界改名为穷举算法。

本次升级3.6主要修改如下：

1。更正了计算路长时有别名的BUG。

2。更正了分支限界算法的一个BUG。

本次升级3.5主要修改如下：

1。优化了动态规划算法和分支限界算法。

2。质点可以右键中设置别名。

本次升级3.0主要修改如下：

1。当鼠标移到边线条时，高亮显示边与边长数字。

2。点坐标可以用鼠标拖动，拖动时可以超出屏幕范围自动产生滚动条，但点坐标不可以为负数。

3。增加了分支限界算法。

4。修正了点坐标的BUG，点坐标与屏幕坐标完全相同。