概述
TSP => Traveling Salesman Problem 旅行商问题
1、旅行商问题
旅行商每个城市都经过一次，又回到出发地；搜索出旅行商所经过的最短路径；
6个城市将会有5!/2=60条路，因为经过城市1后有5个选择，若选择城市2，那么经过城市2后有四个选择，依次类推，经过第5个城市的时候只有一种选择，那就是最后一个城市，所以是5*4*3=60条路；
即n个城市有(n-1)!/2条路
TSP问题的原型即为哈密尔顿回路问题；
2、钻孔规划问题
决定在电路板上钻孔(为焊入部件)順序问题；钻孔机总移动距离最小化单位时间内生产量最大化；
3、不对称旅行商问题
每个城市都经过一次，又回到出发点，搜索出经过的最短路径；但是，城市间的行走时间各不相同（行走世间的非对称性）；
4、旅行商问题的变化
城市间距离：
非对称TSP：城市间距离与方向有关
对称TSP：城市间距离与方向无关
平面TSP：城市是平面上的点，城市间距离是2点间的直线距离
其他情况：
m人TSP： m人从出发点出发遍历所有城市
刚好通过各城市1次 -> 通过1次以上
通过各边1次以上 = 中国邮递员问题(Chinese Postman Problem)
最后
以上就是清秀棉花糖为你收集整理的TSP旅行商问题1的全部内容，希望文章能够帮你解决TSP旅行商问题1所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复