代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题

前言

上次出了邻域搜索的各种概念科普,尤其是LNSALNS的具体过程更是描述得一清二楚。不知道你萌都懂了吗?

小编相信大家早就get到啦。不过有个别不愿意透露姓名的热心网友表示上次没有代码,遂不过瘾啊~哎,大家先别急,代码有得你们酸爽的……

不过由于ALNS的代码量实在太大,小编打算把这个做成一个系列来一一为大家讲解,好让小伙伴们彻底把这个算法框架的代码吃透。

今天暂时还是先不对代码进行讲解,先来教大家怎么使用ALNS的框架求解一个TSP问题吧~

01 环境准备

小编的演示是基于Windows 10 x64位环境的(Linux党就更简单了),其他Windows 环境也类似。在此之前我们需要配置几个东西。

1.1 安装MinGW

这玩意单独装比较麻烦,但是安装devC++会自带这玩意儿,特别方便。没有安装devC++的小伙伴请移步留言区获取安装包下载链接。

去下一个安装上。然后在电脑上找到devC++的安装位置,把其目录下的MinGW64\bin文件添加环境变量。如下图所示:

打开cmd命令行,输入下面命令:mingw32-make 出现下面提示就成功了。

2.1 下载源代码

请大家 移步留言区 把源代码下载下来,然后解压到某个位置(路径不要有中文)。

2.2 修改源代码

找到\trunk\src\alns下的OperatorManager.cpp:

打开,在头文件位置加入下面这句话,把调试模式给禁用掉:

2.3 编译

在命令行下进入\trunk\Release目录,首先输入mingw32-make clean,清理以前编译的中间文件。

然后输入:mingw32-make。进行编译。

得到我们的目标文件:libALNS-framework.so。这是ALNS框架的动态链接库,稍后我们要使用到的。

可以在该目录下看到:

在命令下进入\trunk\examples\tsp,把main.cpp替换为小编修改好的main.cpp

(请移步留言区获取下载链接)

然后照例:首先输入mingw32-make clean,清理以前编译的中间文件。

然后输入:mingw32-make。进行编译。

最终得到我们的程序TSP.exe。这里还有一步,把刚刚编译好的libALNS-framework.so文件复制到当前目录,TSP程序运行需要用到它。

最后可以在命令行下输入TSP,运行我们的程序:

至此,已经完成了。最后说一下,修改的代码为求解Berlin52问题的代码。如果需要求其他TSP问题,在小编修改好的main.cpp文件里,把城市坐标CITY_SIZE改过来,重新编译tsp文件夹里面的内容就行。

最优解是7542,至于这里的解为什么比7542少,原因是代码算总距离的时候没有加上第一个和最后一个city的距离。

03 小结

最后再多说两句,上述求解的代码是根据ALNS框架定制而来的。其实,大家想用ALNS算法求解任何问题,只需要把框架内容做相应的定制就可以啦。在下面的几篇推文里,小编将详细解析ALNS代码框架的内容,然后把上面求解TSP例子的代码定制内容也给大家讲解一下。期待我们后面的文章吧~

原文发布于微信公众号 - 程序猿声(ProgramDream)

原文发表时间:2019-01-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券