cdn 2017华为软件精英挑战赛初赛、复赛、决赛代码

概览

赛题《大视频时代•布局》背景如下，摘自2017年比赛官网：

在给定结构的G省电信网络中，为了视频内容快速低成本的传送到每个住户小区，需要在这个给定网络结构中选择一些网络节点附近放置视频内容存储服务器。需要解决的问题是：在满足所有的住户小区视频播放需求的基本前提下，如何选择视频内容存储服务器放置位置，使得成本最小。

该比赛要求参赛者在指定时间内给出一种视频服务器的部署方案，满足消费者的需求并使得成本最小。因为指定时间内无法算出结果，所以比拼的是：初始解、搜索策略、算法优化。比赛过程如下表所示。

阶段	项目	比赛经过	赛题变化	解题思路
初赛	cdn1	赛区第32，前36进入复赛	赛题如表前所述	先用dijkstra算法求粗糙解，再用最小费用最大流求精确解
复赛	cdn2	赛区第3，前4进入总决赛	1)服务器具有10个等级的输出能力 2)节点有部署费用	1) 先用dijkstra算法求粗糙解，再用zkw算法求精确解 2) 采用神经网络来确定网络节点的属性评分参数，按评分选取初始解
决赛	cdn3	全国第14，共36支队伍	两支队伍对战来争夺消费者，算法类->策略类	1) 使用复赛的选点策略进行选点 2) 为了开局很好的抢到优势开始提供的较大的流量 3) 如果发现点没抢过对手，那么如果将增加提供的流量和对手竞争

com.cacheserverdeploy.deploy 包中是比赛具体的一些实现代码。
com.filetool.util 包中是官方的一些工具类：读写文件和日志。
com.util包中是测试和运行相关的类。Checker 类用于校验输出答案是否正确。FilePath 类用于指定输入输出路径。Main 类测试com.cacheserverdeploy.deploy 包中的函数功能。

配置 com.util 包中 FilePath 类中的路径，然后启动 com.util 包中的 Main 类既可以运行。运行时间限制在一分半内。

本次比赛，我们优化的点是一些算法和数据结构。因为我们使用的是Java语言，所以速度相对比较慢，比较幸运的是，我们利用神经网络训练网络节点的评分参数的方法效果很好，可以基于评分选取一个较好的初始解，从而在有限的时间内给出一个较好的解。该方法的过程如下（实现是NodesSelector类）：

值得注意的是，之所以效果比较好，可能是因为比赛中网络拓扑结构还是比较相似的。此外，在赛后交流中，发现其他队伍的优化包括：使用单纯型算法、缩小网络大小（去掉网络最边缘的点）、使用阈值函数（决赛中的策略）等等。