基于GA求解旅行商(TSP)问题小析

首先,需要搞清楚旅行商(TSP)问题是什么东东呢? ————————————————


TSP问题属于NPC(NP Complete)问题,即NP完全问题,是指该类问题没有确定的算法可以在多项式时间内得到问题的解。此外,关于P问题、NP问题、NPC问题和NP Hard问题在下面博客地址中解释地很明白,可以看看,有助于更好地理解NPC问题。
https://blog.csdn.net/John159151/article/details/49053963 ———————————————— 在MATLAB中带有TSP问题的示例,命令行中键入“travel”即可,关于本示例的介绍如下:
travel —— travel Traveling salesman problem demonstration.This demo animates the solution of the so-called "Traveling Salesman" problem.The problem is to form a closed circuit of a number of cities while traveling the shortest total distance along the way.Use the "Cities" popup menu to determine the number of cities to be visited. The "Start" and "Stop" buttons control the animation.Cities are chosen completely at random.
这个示例采用美国地图为模版,提供了不同数量的城市供我们进行选择,如图1所示。

图1 选择不同数量的城市,该示例会为我们演示所有城市最短路径的动态选择过程,请观看下方视频:

下面利用《MATLAB优化算法案例分析与应用》中给出的程序来作为示范,在100*100的地图中随机产生30个城市的坐标位置如图2所示,然后由GA求解这30个城市之间的最短距离,得到的结果如下图3和图4所示。

图2

图3

图4

参考书籍:MATLAB优化算法案例分析与应用,余胜威著

程序请回复“GATSP”或“GT”获取

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容