【优化算法】变邻域搜索算法(VNS)求解TSP（附C++详细代码及注释）
原创【优化算法】变邻域搜索算法(VNS)求解TSP（附C++详细代码及注释）
原创
短短的路走走停停
修改于 2019-05-14 10:03:17
修改于 2019-05-14 10:03:17
00 前言
上次变邻域搜索的推文发出来以后，看过的小伙伴纷纷叫好。小编大受鼓舞，连夜赶工，总算是完成了手头上的一份关于变邻域搜索算法解TSP问题的代码。今天，就在此给大家双手奉上啦，希望大家能ENJOY哦！
01 代码说明
本次代码还是基于求解TSP旅行商问题的。至于什么是TSP问题，小编这实在是不想科普啦……
代码是基于迭代搜索那个代码魔改过来的。其实看了这么多启发式算法解TSP问题的代码。想必各位都有了一个比较清晰的认识，其实呀。之前介绍的模拟退火、遗传算法、迭代搜索和现在的变邻域等等，是十分相似滴。最大的不同在于算法框架的不同而已，像什么扰动啦，邻域动作啦。代码基本是不变的。所以大家可以多联想，多思考，学习就是一个探求事物本质的过程嘛！
至于算法框架什么的概念，大家看上一篇关于VNS的推文啦。
这里就不做过多介绍了。再次贴一下伪代码。代码是基于伪代码写的。不过本文的代码只做了一个shaking的邻域，vnd的邻域做了两个。这里给大家说明一下。
image
简要说说算法vnd里面两个邻域使用的算子：
two_opt_swap
没啥好说的，区间反转。直接上图：
two_h_opt_swap
还是要说一点，随机产生两点，塞进新排列头部。其余的按顺序往后逐个塞进去。嗯，来看图片~
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录