专栏首页程序猿声自适应大邻域搜索代码系列之(1) - 使用ALNS代码框架求解TSP问题
原创

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

前言

上次出了邻域搜索的各种概念科普,尤其是LNS和ALNS的具体过程更是描述得一清二楚。不知道你萌都懂了吗?小编相信大家早就get到啦。不过有个别不愿意透露姓名的热心网友表示上次没有代码,遂不过瘾啊~哎,大家先别急,代码有得你们酸爽的……

不过由于ALNS的代码量实在太大,小编打算把这个做成一个系列来一一为大家讲解,好让小伙伴们彻底把这个算法框架的代码吃透。今天暂时还是先不对代码进行讲解,先来教大家怎么使用ALNS的框架求解一个TSP问题吧~

环境准备

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

2.1 安装MinGW

这玩意单独装比较麻烦,但是安装devC++会自带这玩意儿,特别方便。没有安装devC++的小伙伴戳下面链接(https://pan.baidu.com/s/1PJ5uxGKmkWzl_3s4GQM88g)去下一个安装上。然后在电脑上找到devC++的安装位置,把其目录下的MinGW64\bin文件添加环境变量。如下图所示:

打开cmd命令行,输入下面命令:

mingw32-make

出现下面提示就成功了。

下载源代码

把源代码下载下来,然后解压到某个位置(路径不要有中文)。

修改源码

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

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

编译

在命令行下进入\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问题的代码。最优解是7542,至于这里的解为什么比7542少,原因是代码算总距离的时候没有加上第一个和最后一个city的距离。

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 只有程序员才看得懂的段子!

    一程序员去面试,面试官问:“你毕业才两年,这三年工作经验是怎么来的?!”程序员答:“加班。”

    加米谷大数据
  • 字节跳动凉面(抖音C++)(问题+解答)

    本科大四。 在字节官网投了简历,过了一天突然收到hr电话,问我工作倾向于北京还是上海,我说上海,然后hr说把我简历转给抖音上海hr....又过了一天(清明节前一...

    牛客网
  • C++ 标准库之 iomanip 、操作符 ios::fixed 以及 setprecision 使用的惨痛教训经验总结

    本菜鸡自从退役之后就再也没怎么敲过 C++ 代码,在 C++ 语言下,求解关于浮点数类型的问题时,之前有碰到类似的情况,但是似乎都没有卡这块的数据,基本上用一个...

    Angel_Kitty
  • JavaScript和Java的区别?

    它是运行在浏览器中的一种脚本语言,在web页面中,Javascript可谓是无所不能:

    葆宁
  • Linux命令(65)——ld命令

    ld命令是二进制工具集GNU Binutils的一员,是GNU链接器,用于将目标文件与库链接为可执行程序或库文件。

    Dabelv
  • 百度面试两板斧:手写算法问基础

    17年7月份,我参加了百度的实习生面试,随后在百度开始了半年的实习生活,18年7月份,我参加了百度的校招提前批面试,由于可以同时参加百度多个部门的提前批面试,结...

    黄小斜
  • 五大人工智能流行编程语言对比,只要学会一种绝对不亏!

    就像大多数软件应用程序的开发一样,开发人员也在使用多种语言来编写人工智能项目,但是现在还没有任何一种完美的编程语言是可以完全速配人工智能项目的。

    一墨编程学习
  • Protocol Buffers(1):序列化、编译与使用

    Protocol Buffers docs:https://developers.google.com/protocol-buffers/docs/overvi...

    李拜六不开鑫
  • Linux 多进程通信开发(六): 共享内存

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/briblue/article/details/891...

    Frank909
  • Linux命令(63)——nm令

    nm命令是GNU Binutils二进制工具集的一员,用于显示目标文件中的符号。如果没有为nm命令指出目标文件,则nm假定目标文件是a.out。

    Dabelv

扫码关注云+社区

领取腾讯云代金券