2017华为软件精英挑战赛–总结

2017华为软件精英挑战赛–总结

比赛已经落下帷幕。尽管最后没能进到64强，但从最开始的啥也不懂，到最后西北赛区91名，我尽力了，尽管还是有很多的不甘心。把这近一个月的辛酸历程做一个总结吧，也算是对自己有一个交代了。

3.4日，官方正式公布赛题。之前对华为软赛只是有所未闻，并为真正去了解过，所以一开始也并没有准备参赛，只是草草的看了一下赛题（并没有读懂赛题），加上手头上也还有事没做完，想着把事情一件一件做好。真正开始做软赛是在3.8日，抱着锻炼自己的算法能力的初衷开始做比赛了，此前对算法基本上是一张白纸，我已经能够预见接下来的这段时间势必会遇到很多困难，但是只要我一旦决定要去完成一件事后，我就会尽百分之百的努力去做好。

花了一个上午把赛题（大视频时代-布局）仔仔细细读了一遍，知道题目是要在 络拓扑中设计寻找最优的服务器部署方案：在满足所有消费节点带宽消耗需求的前提下，使得耗费总成本（服务器部署成本+带宽租用成本）最低。尽管读懂题目后，还是一头雾水，根本不知道从哪儿开始下手。我去请教了实验室一个研三的师兄，师兄说：1、先去 上找相关的资源，所有的程序从头到尾全是自己写的话在一个月这么短的时间根本来不及；2、先编程序，边想边写，不要等到把所有的算法都想出来了才开始写，不然等你想出来了，已经没有时间写代码了；3、 络图一般都是图论中的知识点，把图论的书看一遍也来不及了，你需要用得到什么就去里面看什么，一般最短路径问题常用的方法有广度优先搜索、dijkstra算法。

有一点方向，总比茫然好，尽管我不知道dijkstra算法对这个题目有没有用。然后我就去图书馆借了两本图论的书，找到里面的dijkstra最短路算法，用了差不多两天的时间去读懂和实现这个算法。在实现过程也遇到了困难：通过遍历得到最小值后怎么确定前驱节点；输出经遍后是从终点到起点的，刚开始是用数组存放然后输出的，后面知道了用堆栈存放刚好符合这个特点。理解dijkstra算法后，发现和题目并没有什么联系，我又在 上搜看有没有大佬分享一些经验，在知乎上找到了一个帖子说这是一个NP-Hard问题，是facility location问题，然后还是一脸蒙圈，不知所云，到后来才知道说的全是对的。然后我在软赛交流群里看到有人说可能是背包问题，我又去了解了背包问题，发现也不能解决题目的问题。在走投无路的情况下，我试着在软赛交流群里去私信一些看起来像大佬的人，问问他们的思路，本来不抱有任何希望，但真有人回复了我，说是 络流的问题。尽管只是一句简单的提示，我向他表示了万分感谢。我去了解了 络流中的最大流问题和最小费用最大流后，发现正是题目所对应的问题。经过了差不多一周的折腾，才找准了方向。一个人去面对问题，才知道困难远比想象的多。

接下来就是去解决 络流中的最大流问题和最小费用最大流问题了。由于之前的数据结构和算法的功底太差，看了好久才把算法思路看懂。在最小费用最大流问题中，每条边有两个参数（费用，容量），分别建两个图，第一个图的边用费用表示–用来求可增广路径，第二个图的边用流量和容量（流量的上限为容量）表示–用来求最大流，当然这两个图是相互影响的。在第一个图中求增广路径是可以用dijkstra算法来求的（之前的努力还是没白费的），但是由于dijkstra算法存在一个局限：不能处理有负权边的图，所以最后选择用SPFA算法来处理。SPFA算法是建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（本身为0，其他为无穷大）。然后进行松弛操作（求最小），用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列用则加入。重复直至队列为空。现在把底层的最小费用最大流的问题已经解决了，但是赛题是一个多源点多汇点的问题。怎样把单源单汇问题转换为多源多汇呢实很简单，把所有源点连到一个超级源点，所有汇点连接到一个超级汇点，再把超级源点连到所有源点的边的费用和容量分别设为0和无穷大，超级汇点连到所有汇点的边的费用和容量分别设为0和消费节点带宽所需的消耗。但是赛题要求满足所有消费节点带宽消耗需求，这又该怎么处理呢时我在博客中看到了一个思路，刚好和这个情况类似。博客在这：http://blog.csdn.net/fobdddf/article/details/19615651。此时我在超级源点前再加上一个超级超级源点，是其边的费用和带宽为0和所有消费节点带宽所需消耗的总和。这样就能够很好的解决上面的问题了。其实这些方法都是自己在反反复复的探索过程中发现的，说着容易，但却经历非常多的艰难困苦。

等把上面的问题都解决了之后，我才发现赛题考察的核心根本都不是 络流的问题， 络流只是底层部分，核心的部分是设施选址问题，此时我才意识到之前在知乎上看到的都表述得非常准确，我又仔细读了一遍。然后立马去图书馆借了四本关于NP问题和设施选址问题的书。但赛题不单单是设施选址，因为首先服务器（也就是设施）的个数不知道，其次是服务器的位置也不知道。往往设施选址只能确定服务器的位置应该部署在哪，但是并不能确定服务器的个数，这是接下来必须要解决的非常棘手的问题。

在书中了解到选址的常用算法有：数学规划算法（分支定界法、割平面法、拉格朗日松弛算法）、领域搜索算法（贪婪算法、禁忌搜索算法）、智能优化算法（遗传算法、模拟退火算法、人工神经 络算法、蚁群算法、粒子群优化算法、多目标进化算法）。书中只是介绍了一些概念性的东西，看了也不会用。然后我就开始疯狂的找相关的论文、看论文，论文中都把选址问题转换成数学模型，列出了目标函数和一系列约束条件，处理过程我基本上都没看懂。看了几天的论文，我发现赛题是一个0-1的整数规划模型，但是就算我把目标函数和约束条件都列出来了，我也没办法把它转换成c++代码，所以整数规划的方法我是没办法了。而启发式算法中我又只对遗传算法有所了解，所以我决定用遗传算法试试。

用遗传算法有几个需要明确的关键点：种群是什么群的初始化群的编码价函数是什么
显然，评价函数应该是总成本（服务器成本+线路费用）。种群是服务器的位置，而种群初始化为把服务器放在消费节点的位置（可以保证得到一个总成本），种群的编码用二进制编码。明确了这些之后，我就开始写代码去实现了。

由于官方要求是在Linux ubuntu中运行，所以我现在的首要任务是把在Windows下面写的程序移植到ubuntu中。我现在是Windows系统，我又不想重装系统，所以索性装一个虚拟机，在虚拟机里跑ubuntu，还好实验室给我配了一台新台式机，不然我的笔记本根本刚不住。我对自己说今天无论多晚都要把程序移植完成。我下载好虚拟机之后便开始安装ubuntu，安装完成之后ubuntu中有个工具升级一直有问题，这时实验室的小伙伴晓雷说他刚好也安了ubuntu，里面的编译环境都已经配置好了，要不直接拷给我。我立马就答应了，非常感谢晓雷同学的ubuntu，还演示了一下在eclipse gcc中编译运行和打包上传文件的整个过程，为我省去了不少时间。这样我便开始了移植工作。在移植到eclipse gcc中变化最大就是文件的读取和输出，之前在Windows下是直接重定义标准输入输出就ok了，但是在官方给的demo中是以文本中字符的格式输入输出的，于是乎我开始重新写读取和输出的部分，用sscanf()、sprintf()这两个函数完成了这部分工作。直到凌晨4点钟我才弄完，想着在终端编译一下.sh文件，生成一个压缩包上传到官 之后才回去睡觉。谁知道，在终端编译一直显示权限不够，我在 上又搜了半天还是没解决，我知道这应该是一个小问题，只是知道与不知道。无奈，我便回去睡觉了。又体验了一下学校凌晨四点过的夜景！！也没睡好，可能是一直都想着这个问题，第二天9点过就起了，到实验室问问老高（老高已经提交代码了，成绩还不错），老高三五两下就帮我解决了。老高在比赛过程中也帮了我不少的忙，我真的是非常的感谢他。还好实验室还有两个小伙伴可以一起交流讨论，不然一个人做比赛太难熬了。终于提交了自己的第一份代码，看着有一个成绩和排名，心里的喜悦溢于言表。这也给了我一个继续做下去的信念。

后来我就开始写遗传算法的部分了，23 官方更新了用例，高级用例部分得分为零，当时我还在上课，立马就坐立不安了，下课了赶紧跑到实验室检查是啥问题，因为我是直接把服务器放在消费节点的，不应该出现零分的情况啊。后来经检查发现是数组越界了，我修改后又提交了，居然直接到了51名，着实吓了我一跳，又偷偷的窃喜。

比赛已经告一段落了，再用一年的时间去好好沉淀自己！！来年我也想做一回大佬！！

PS：要特别感谢一直陪着我的傻妞，每次心烦意乱的时候，给你聊聊天，总能给我一些灵感、给我一些动力，要是没有你的陪伴、你的支持，可能我都坚持不到最后，不管最后结果怎样，我从未放弃过。小傻猪，谢谢你！！

这段时间看过的书：