2017 华为软件精英挑战赛

### **03.13 - 03.19**

这段时间在整理毕设的东西之余，了解了关于整数规划的东西，包括分支定界、单纯形、拉格朗日松弛等等，并建立了一个整数规划模型，尝试去解，发现暂时还没有这样的水平来用这种方式来解决这个规划。

### **03.20 - 03.26**

于是，开始思考其他方式。一开始，我们发现去除带宽限制之后，这是个经典的无容量限制的设施选址问题(UPFL)，然后再通过多源多汇费用流的方法去解决，就好做了。随后，在淘了很多论文之后，找了一种贪婪算法去解决UPFL的问题，发现得到的结果和已知的最优解的服务器相近，这给了我们希望，后来通过贪婪算法 + 费用流 在小案例上得到了最优解。但是在大用例出来之后，发现这种办法会跑出来一些错点(非最优情况下的选址点)，因为毕竟没有考虑到带宽受限的情况，所以单单用费用流去判断哪些消费节点不满足，然后再在这些基础上进行优化，完全不会达到最优。

### **03.27 - 03.31**

写的第一版贪婪算法效率很高，但是由于打印的信息太多，导致我误以为效率很低（体现在高级跑了6分钟），采取另一种实现方式去实现贪婪算法，然后浪费了很多时间在上面，最后才发现写的第一版贪婪算法，在去除打印的信息之后，跑高级用例简直秒出。但是同时，由于没有考虑带宽限制，跑出的服务器点和已知最优解还是有些出入（虽然还上了一次64强榜单）。于是准备开始考虑采用其他启发式算法。

### **04.01 - 04.05**

在正式用例出来后，服务器成本提高，于是我们排名开始狂降。于是我先后尝试了遗传，由于是第一次实现，导致结果很不理想，却又无从下手，在4日晚上得知遗传退火可能会得到一些效果，所以又开始第一次实现遗传退火，在5日早上实现完成，中午测试了一下，初级用例有时可以跑到最优，中级可以提高一点点，但是高级就又完全跑不动了。

到5日晚上，我们几乎已经绝望，因为算来算去，我们最好的情况是得75分，而目测64强最后一名估计需要79分，最后两个小时的时候，终究还是技不如人，弃了。

### **心得**

* 代码
    1. 代码体现一个人的思维，代码混乱，即体现思维混乱
    2. 团队的代码功底不足，在解决问题的时候，往往代码写的非常难以维护，并且耦合情况十分严重。
    3. 以后在写代码的时候，要更加注重逻辑的设计，以及考虑时空间的开销。(还是算法功底以及数据结构的知识不足)
    4. 虽说这个比赛，更加考验的是算法，但是过烂的代码，会导致时间的拖沓，以及工作推进的效率
    5. 做好代码测试
 
* 算法
    * 三人算法功底都不足，导致在写完启发式，无从优化
    * 在学习算法的时候，往往只学习了其形，而没有学到其神，所谓学而不思则罔，思而不学则殆。在学习东西的时候，不仅仅要看到起表面的效果，而要思考其背后的逻辑。
    
* 时间与效率以及方法
    * 一个月的时间写比赛，给我们时间很宽松的错觉。而事实上，时间很紧张，多些时间，就多一些思路，就可能多一些尝试。
    * 这次比赛阶段不同，难度也节节升高，因此需要做好算法和代码的鲁棒性
    
* 团队
    * 团队散漫，不如单干。
    * 闭门造车，思路无法得到发散

逆风起笔