代码链接https://github.com/happyte/2017CodeCraft
距离大赛结束已经过去1个月了，从3月份开始比赛到最终5月中旬的总决赛，历时72天。最后的结果挺好的，进了全国8强，取得了第6的成绩。了却本科做比赛期间一直未能进入全国决赛的遗憾。
-
2.首先介绍下今天大赛的题型，是基于华为现实SDN抽象出来的一个模型，在一个城市内分布一些服务器，通过网络链路服务消费者，成本耗费在服务器的购买，服务器档位费用，链路费用。最终要使得总成本最小。详细题目介绍在 http://codecraft.huawei.com 官网上。
-
3.初赛代码我们是基于启发式算法+最小费用流算法，启发式搜索用的是爬山法+邻域搜索，最小费用流算法是目前速度最快的网络单纯型。在比赛过程中很多人使用的费用流算法是zkw，zkw改为在原图上跑的话速度也是很快的，当时我们的底层算法就选用了效率最高的网络单纯型。
-
4.复赛:在初赛的基础上，复赛增加了档位约束条件，新增加降压策略和压档策略，最小费用流通过修改顶点势的方法改为在原图上跑，是初赛速度的5倍。在1200个点的图上90s时间内纯跑费用流的话大概能跑14、15w次。
-
5.决赛:题目改为双方博弈类型，第一轮产生的初始解很重要，需要优先评估服务器，删除一些不必要的服务器，而且需要对服务器的选择档位作出评估。博弈策略是预测自己的下一轮收益和对手的下一轮收益，需要抢夺的消费结点分类讨论，1-已经占领的，2-对手占领的，3-双方都没有占领的，模拟退火算法以双方的收益差作为目标函数，使得双方的收益差尽可能大。
-
6.华为的软挑确实是个好比赛，不过也出现了很多的意外情况，复赛现场的时候出现了网站被攻击的情况，决赛前几天官方的判题还一直有bug存在。不过最终都得到妥善解决了，希望以后的大赛能尽量避免这些意外情况。
-
7.在比赛过程中很考验一个团队的想法和快速编码能力，对于我们队来说，基本上每天都有一种要推倒重来的感觉，尝试各种不同的策略。因此就很考验写代码的速度了，如果方法不行的话赶紧尝试下一种方法。还有，给大家一个建议，如果确定了底层算法用哪种的话，尽量去找资料看效率最高的算法，对后期的成绩起到了重要作用。
最后附上一张团队照片，哈哈
IMG_1185.JPG
网友评论