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

1.题目

本次竞赛题目涉及视频服务器在CDN网络中的规划问题
赛题包_百度网盘


2.解题思路分析

2.1 思路一 整数规划

核心任务在于构建相应的模型结构


涵盖了
0-1变量->是否部署服务器
边变量-> 表示该边所承载的流量

尝试使用glpk进行求解，但由于变量数量过于庞大，导致内存无法承载，求解效果也不理想，仅能处理极小规模的问题，甚至28个节点的案例都无法完成；有清华的专家亲自编写了一款高效的整数规划求解器，求解表现非常出色，令人钦佩。

建模思路可借鉴清华博士专家的建模方法：
复赛整数规划模型.docx

2.2 思路二 启发式算法 + 最小费用流

2.2.1 启发式算法

可采用遗传算法、模拟退火等方法进行求解。若选择遗传算法，染色体的编码方式可以采用二进制形式，其中设置服务器节点的位置用1表示，未设置服务器节点的位置则用0表示；

2.2.1.1 基于遗传算法的改进

修改策略
加速收敛过程
1）完成一轮搜索后，首先进行排序操作，从中挑选出表现最佳的20