一、前言

小伙伴们好，说起来已经好久好久好久没见了呢！之前一直忙着做其他事情去了（泛指学习一类），公众号已经落下好久好久了。今天来写点好玩的东西。

说起来，小编似乎就是做启发式算法起家的。当时记得老师是这么跟我说的，启发式算法这东西很简单，你不需要基础，有高中基础就够了（其实他想说的是初中……）。后来小编一直在学这个东西，做了三四年了，用启发式算法做过的大大小小的project已经不记得有多少了，所以还算得上有一点点经验。

因此今天就来写写，怎样实现一个比较高效的启发式算法吧~

二、何为高效？

说到这个词，相信大家一定不陌生。高效意思就是达到相同效果或者更好的效果时，使用的时间更短，所需要的资源更少。就拿小编来说，由于小编特别笨，学一样东西需要花一周的时间，而群里的小伙伴只需要一天的时间就能学会。那么这位小伙伴是要比我高效的。

同样的对于一个启发式算法而言，不同人实现出来，即使是使用同一编程平台达到同样的效果，运行时间也会千差万别，相差几倍甚至几十倍。这样说出来大家可能还没啥感觉，那么放一下我们之前做过的一些数值实验大家直观感受下吧~

这是某个Java实现的求解VRP类问题的算法代码，两个算法都达到了同样的效果，只不过绿色曲线对应的算法在计算过程中去除了相关冗余，可以看到运行时间直线下降。根据我们的统计，消除冗余计算后可使计算时间降低约83%，对于工业化生产而言，提升哪怕一个小数点都能带来巨大的收益，何止是83个百分点呢。怎么说呢，这简直是A small step forward，one step civiliazation。

三、放码过来？

不要一上来就是写代码，不加思考就上手写代码，你只会搓一坨屎山出来，自己坑害自己。开始写代码之前一定要构思好算法的整体架构，解的表示方式，如何快速得到邻居解等。建议是思考的时间一定要占总时间的一半以上。

其实思路清晰写代码是非常快的，比如每次在写代码的时候我都会先写好注释，比如：

//1. 先获取所有可行点的信息

//2. 对点按照成本进行排序

//3. 贪心将各个点插入到解中

然后写的时候我只需要按照这个思路往下走就可以了，这就跟你写小学生作文一样，起床刷牙到公园看鲸鱼，一定要思路清晰。

四、邻居解如何计算？

到了今天的核心问题，我们都知道，邻域搜索过程中，邻居解与当前解相比往往只有细微的变化，因此迭代过程中绝大部分变量不需要重新计算，消除了冗余计算，可大大提高邻域搜索效率，降低运行时间。听不懂吗？没关系，我举例子，慢慢给你讲解。

下面是一个VRP问题（没有TW哦）的一个初始解

为了方便表示我们用 image

可以看到该move就是将客户19从路径 image

中发生变动的边我已经用红色实线标出来了， 中发生变动的边我用红色虚线标出来，那么 和 是不是可以用之前计算好的 和 得出来呢？当然可以啦，我们只需减去原来的边，再加上新的边就可以了。

我们将这两条式子带入下面的式子：

即可得到：

这个时间复杂度为 ，OK。经过重重优化，将时间复杂度从原来的 成功降到了 。

可能大家对这个 降到 没什么感觉。我来给大家分析一下，在小规模问题，比如10个、20个节点这样可能还真没啥区别。但是别忘记了启发式算法是针对大规模的优化问题的，邻域搜索类算法的邻域规模往往是随着问题规模的增长而呈爆炸式增长的。比如说在一个100个节点的VRP算例中，对于exchange算子，交换任意两个客户，那么一个解所能形成的邻居解就有 ，大约为5000个邻居解。

• 如果每个邻居解你都使用Algorithm1重新算一遍，那么大概要算5000*100=50万次。
• 如果你用优化过的计算方法，只需要算5000*1=5000次。

这个差距有多大，大家动动屁股都知道了。当然了，这只是理论上的分析。实际上的差距和编程环境以及实现方式等都有很大关系，但是只要差距超过10倍以上，都是能很明显的感觉出来的。

五、小结

关于如果去除冗余，不是说一套方法通用的，需要根据算法工程师根据问题的特性，设计合适的解结构，再对邻域算子进行降冗余的思考与实现。降冗余的操作比较适合邻域搜索类的启发式算法，因为这类算法显著特点就是邻居解相比较当前解而言，变化非常细微。

当然了，这需要丰富的编程经验，所以大家有时间还是好好磨练下吧，相应的学习代码请点击头像获取哦。