前天华为2017精英软件挑战赛初赛结束了，但是并没有进入64强，扎心，趁着还热乎，来写下参赛感受，不喜勿喷哈。
比赛介绍
这个比赛是华为公司面向全球大学生举办的大型软件竞赛，在之前就听说过华为精英软件挑战赛，认识的一个学长还拿了这个比赛第一届的冠军，所以今年在这个比赛开始前我就开始关注这方面的信息，这个比赛一般在每年的3月初开始，初赛进行一个月左右，决出64强，然后前32强直接进入复赛，第33-64名队伍进入复活赛，每赛区复活赛的前4名队伍晋级复赛，在复赛阶段，决出各赛区前4强获得决胜奖，并前往深圳参加决赛。在决赛上，决出大赛八强和最优美代码奖。
当然比赛的奖品还是蛮丰厚的，一等奖奖金20W，详细的可以上大赛介绍查看。
题目介绍
本次赛题“大视频时代.布局”，在给定结构的G省电信网络中，为了视频内容快速低成本的传送到每个住户小区，需要在这个给定网络结构中选择一些网络节点附近放置视频内容存储服务器。需要解决的问题是：在满足所有的住户小区视频播放需求的基本前提下，如何选择视频内容存储服务器放置位置，使得成本最小。其实也就是一个CDN(Content Delivery Networ)节点服务器部署问题。当然还有很多具体说明，详细内容可以到赛题介绍查看，在这儿就不多说了。
我们队伍的解决方案
这次是和研二的两个学长组队的，是我室友实验室的，据说平时就是研究网络的。题目放出来的时候我还在实习，所以自己也没咋看，然后两个队友说他们有一个思路，大概就是用遗传算法选取服务器位置，当服务器位置确定后，用dijkstra算法来算最小花费。算最小花费的算法如下（假设服务器M个，消费节点N个）:
- 先使用dijkstra算法计算MxN条最短路径（路径上的权重就是带宽单位花费）
- 对MxN条最短路径进行排序（排序标准：路径上单位花费和）
- 从路径上单位花费和最小的开始使用，如果这条链路上的带宽大于消费节点带宽，则此消费节点全部满足，若小于消费节点带宽，则使用链路的最大带宽
- 然后对应更新MxN这个路径集合
- 直到满足所有消费节点为止，或者路径都不满足，返回部署方案不可行
后面在跑的过程中，发现按这种算法出现了很多部署方案不可行，而且这种算法计算很慢，因为每次都要去求最短路径，其实是很慢的操作。所以导致遗传算法跑不了多少代，更别说跑出结果来了。
后面针对出现很多部署方案不可行的情况，提出了K条dijkstra最短路径，即KxMxN最短路径，来计算当服务器确定时的最短花费。不过速度还是很慢（还是经过一定的优化后的结果），不过算法结果还是正确，根据参赛群里给出的最佳部署方案的服务器位置，我们的算法算出来的最小花费和最优解是一样的，就是太慢了。此时我们的遗传算法也还有问题，关于初始种群的生成和在进化中的交叉变异等。
此时我已经实习结束回来一周了，把两位队友的想法基本写出来（我主要是负责搬砖的），事实证明这种方式不可行。
通过一段时间参赛，我也了解相关的一些算法，也在知乎上和参赛群里知道了些思路。大家用的最多的就是最小费用最大流算法。由于我之前没有接触过算法，尤其是图相关的，所以一开始对最小费用流，最大流算法什么的是一脸懵逼的，听着感觉高大上，很复杂的样子，所以最开始也没有去仔细研究，但是现在我们自己想的算法不可行。只能硬着头皮去看看了。在网上找了下最小费用最大流的相关资料看了下，发现这个算法就是我们所需要的，完全可以解决这个题目的问题（当服务器位置确定后）。
在github上找到份最小费用最大流算法做参考。在这儿推荐这个网站给大家，里面有好多关于算法的代码，都是用Java写的，因为我主要是用Java的。里面关于最小费用最大流算法用了三种方法实现。在这儿我就不多说了。不过最小费用最大流都是针对一个源点到一个汇点的算法。而我们题目中需要的是多个源点到多个汇点的。开始并不知道怎么做，还持有怀疑的态度。直到看到官微推送的这篇博客，博主就是用的多源多汇最小费用最大流算法。这个时候看到针对多个源点多个汇点的最小费用最大流的解决方案，其实和单源点单汇点的是一样的，就是在多源点前加一个超级源点，这个超级源点和各个源点之间的带宽无限大，费用为0。在多个汇点后加一个超级汇点，每个汇点与超级汇点的带宽为各消费节点的带宽，单位花费也为0。这样就可以把多个源点多个汇点的最小费用最大流问题转化为单源点单汇点的问题，直接就可以用这个算法。最开始没有想到，被自己蠢哭。
然后开始写代码，只需要写添加超级源点超级汇点的代码，然后直接套用最小费用最大流算法，很快就写出来了，跑了下果然很快。按开始给的case最佳部署方案的服务器位置跑了下，算出来的花费也是最优的。不过这会儿已经快到放清明节了。距离初赛结束没有几天了。这块搞定后我又开始去研究遗传算法，遗传算法主要是初始种群生成的可行解太少了。导致在迭代过程中问题很多。也可能是我对遗传算法了解的不够深（毕竟才接触遗传算法，之前没有接触过）。开始我的思路是针对每个网络节点的出度进行一个排序，然后赋予不同的概率，这样在生成时候，出度大的节点部署服务器的概率大，生成的可行解比较多。还有就是通过看论文，对不可行解进行修正，成为可行解。具体在代码编写过程中，都很复杂，也没有能弄出来。于是考虑其他的启发式智能算法。听说有的队伍使用模拟退火做的，于是我开始去看模拟退火算法，主要参考了这篇博客，讲的是用模拟退火算法解决TSP问题。模仿博客中的代码写了确定服务器位置的代码。写完后最开始没有跑出结果来，后来发现了一个bug，改正后基本都能跑出结果来了，效果看起来也挺不错的。
准备上传代码，看看能跑多少分。上传跑的结果如下：
判题系统说超过链路流量限制。第一感觉是不太可能啊，怎么可能流量超过呢。后面也是通过看官微推送的那个大佬的博客，才找到了问题，由于在计算最小费用最大流的时候，保存的路径是增广路径，然后增广路径存在着回流的情况，这种保存增广路径的方式会把回流的方式也保存为路径，所以有机会超过链路上的最大流量了。大佬的博客上是有解决方法的，利用DFS和回溯来输出正确了路径，尝试编写了一天多的代码，没有成功。后来利用SPFA来输出正确路径。此时代码基本已经基本正确。上传试了下，得了70多分，感到很高兴。然后就准备优化了。
由于现在距离初赛结束也就只剩一天半的时间了，所以主要把优化点放在了模拟退火上，由于我的模拟退火是仿照博客里面写的，所以应该还有很大的优化空间。下午自己详细看了下模拟退火算法并和两位队友进行讨论，确定了几个改进点。
- 初始解的生成，可以改为不全部在与消费节点的网络节点上部署服务器。按一定的比例随机部署。
- 新解产生，产生新解原来的方式是随机改变三个基因位，这根据网络规模进行调整。
- 初始温度，原来的温度都为250度。
- L的大小，即每个温度下循环的次数。
- 降温策略
晚上针对上面的优化点分别进行了优化，然后在晚上提交了一次结果，上升了1分多，效果还是比较明显的。只不过这会儿其他队伍也在优化自己的代码。在优化代码的过程中，也发现了一个问题，就是针对高级用例的优化很有限，主要是在90s内高级用例大概只能跑900多次最小费用最大流。次数太少。需要提高最小费用最大流算法的速度。
最后天上午和队友说了下遇到的问题，然后便去上课了。后面队友和我说看看zkw算法。下午到实验室看了下zkw算法，发现这种算法每次并不需要重新求最短路径，而是更新局部，速度更快，代码量还少，实现也比较简单。于是花了2个小时实现了下，跑了下，速度提高了快两倍多。高级用例可以跑2500次左右。此时就可以着手对高级用例进行优化了，毕竟高级用例有50分，而我们现在高级用例只得了30多分。
晚上去两位队友的实验室，进行最后的优化，晚上12点就截止，我们三个人针对高级用例进行了参数测试，然后确实减少了不少最小花费。这会儿官网的判卷时间变得很慢，应该是提交代码的人太多了。在10点多的时候我们提交了一份代码，结果如下，这也是我们最好的结果了，(⊙﹏⊙)
后面改变了下降温策略，也提交了次，不过跑出来的结果并不好。
至此，比赛就结束了。
代码
代码整理整理后我已上传到github,地址，仅供参考。
参赛感受
参加这次华为比赛，虽然后面没有进入64强，还是收获很多的。这个结果我也是满意的，尽了自己的最大努力。谁让我之前没有怎么玩过算法呢。通过这次比赛，也让我了解到我的编程能力还有很大提高，在参赛过程中，编写的代码bug比较多，耗费了较多的时间去调试。还有一个就是算法的重要性，原来就听说过算法是程序员的内功，一个好的算法，可以将程序执行效率提高很大。所以后面需要好好学习算法。
