TSP问题算法小软件最新版是一款专业且实用的TSP问题算法工具。TSP问题算法小软件最新版界面简洁，操作简便，能对分支界限的算法路径进行显示，是黄色的颜色，不仅如此，TSP问题算法小软件官方版功能全面还支持显示动态规划算法的路径，是绿色的颜色。

基本简介

      TSP问题算法小软件最新版，即Traveling Salesman Problem，也就是旅行商问题，又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题。

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

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

      旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。

      TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。

      TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。

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

软件功能

      只对分支界限的算法路径进行显示，是黄色的颜色

      显示动态规划算法的路径，是绿色的颜色

      这次对益群里面的蚁数进行输入

      信息素重要程度、启发式因子重要程度

      信息素的挥发、信息素的初始值

      每次金华的代数设置、交叉算子的信息

      TSP问题算法小软件软件特色

      分支限界的算法信息查看

      1.在顶点数为 12 时，测得分支限界算法约半分钟。

      2.在顶点数为 13 时，测得分支限界算法约一分钟。

      3.在顶点数为 14 时，测得分支限界算法约两分半钟。

      4.顶点数大于 14 时，没有测试过。

      动态规划算法

      此动态规划算法，

      当顶点数为 20 时，运行约十秒，

      当顶点数为 21 时，运行约半分钟，

      当顶点数为 22 时，运行约一分钟，

      顶点数为 23 时，测试时提示 out of memory ，内存大的电脑

      或可一试。

解决方法

      1、途程建构法(Tour Construction Procedures)

      从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：

      2)节省法(Clark and Wright Saving)：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。

      3)插入法(Insertion procedures)：如插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。

      2、途程改善法(Tour Improvement Procedure)

      先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：

      1)K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代路径中K条节线，并计算其成本(或距离)，如果成本降低(距离减少)，则取代之，直到无法改善为止，K通常为2或3.

      2)Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性。

      蜜蜂实验

      蜜蜂实验

      3、合成启发法(Composite Procedure)

      1)起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。     2)起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

      TSP问题算法小软件注意事项

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

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

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

使用方法

      1、下载完成之后解压成功，点击TSP.exe运行软件;

      2、进入软件的主界面，支持对坐标界面的信息进行查看;

      3、点击说明，进入文本说明的界面，支持对相关的信息阅读;

      4、进入软件的关于界面，对各种相关的作者信息查看;

      5、感觉软件好的话们可以进行借款的操作;

      6、支持对顶点的数量进行输入，在点击创建随机顶点就能得到你需要使用的顶点;

      7、并且支持对顶点的坐标进行导入;

      8、对路径进行输入，点击计算路长;

      9、遗传算法支持对种群进行快速的创建;

      10、支持对蚂蚁进行创建，对相关的信息进行显示;

      11、动态规划的界面，点击运行，就能得到相关的算法路径;

      12、支持对分支界限及很想运行，而且可以对运行的数据查看;