华为软挑小结
背景
2017 年春，和一位朋友参加华为软件精英挑战赛，负责所有编码工作，最终时运不济（启发式算法，确实有一定运气成分）、能力不足，最后成绩只有前 64，有点遗憾，不过过程中也接触到了很多平时不常见的算法，有些收获。
问题大意
问题需要给一个网络拓扑安排视频服务器节点，这些服务器需要给视频消费客户端节点传输视频，网络路径是有带宽限制的、客户端是有最小流量需求的、网络路径是有单位费用和最大流量的，因此如何安排这些服务器节点就决定了供应商是赚还是赔。这道题是实际问题的一个简化抽象，下面给出更严谨一点的描述。
给出一个无向网络，网络中每条路径有一个带宽容量限制和单位带宽的花费，网络中还接入了一些消费节点，每个消费节点有一个容量需求（这些消费节点和网络节点之间的路径是没有花费和限制的），现在让你在网络中布置一些服务器给消费节点提供带宽，每个服务器有固定的费用，让你设计一种服务器的布置方案使得费用尽量少并输出服务器给消费节点提供带宽的路径。
原题下载
思路
- 刚开始根据提示列出了个看起来有模有样的模型，似乎是可以解的（这当然是不可能的，该题是一个 NP-Hard 问题，在规定时间内得到最优解不大现实），于是企图使用解方程的方法来硬解，到图书馆借了本运筹学的书（《运筹学导论》），看了些解方程的算法就开始撸代码了，最后得到一个似是而非的答，所以第一次尝试失败了。
- 又重新列了几次模型，参考了群中大佬发的模型，确认模型是没有问题的了，那么应该就是解法的问题了，实际上是因为模型中的变量达到了二阶，拿单纯形法来解根本不合适（到现在我也忘了我是怎么把单纯形法套到这题上的了…）。
接下来我开始研究数学规划的内容，一些算法看起来似乎有能力解决这个问题，但是图书馆找不到靠谱的参考书，于是从网上找到了两本相关的书（《数值最优化算法与理论》、《数学规划》），但是用这么短的时间研究透彻并整出能用的代码还是太困难了，当还留下大概 2 周时间时，我们已经抱着一种参与第一的心态了（这里发现有些人实现了这种思路，但是具体实现方法我就不明白了）。
当时列出的整数规划模型大概如下图所示（临时网上找的，可能有 Bug）。
其中，b 为每一条边的带宽限制，c 为每一条边的成本，u 为每一条边的带宽使用情况，uxy 和 uyx 不一样，区分先后顺序，d 为每一个网络节点的带宽需求，s 为是否在某点建立服务器，为 01 变量。 - 最后，死马当活马医，借鉴了其他人的思路，觉得采用启发式+最小费用最大流算法会有效果，于是花了一、两天时间写了个遗传算法+SPFA 最小流的第一版解法，就兴致勃勃地提交了，得到的结果让我欲哭无泪，离前 32 有一定差距，于是我们就开始研究优化的方法。
- 对算法的优化主要针对题目、启发式算法和最小流两部分，对前者，主要是充分利用了题目给出的一些条件来使算法更快地收敛，比如用消费节点作为初始位置；对第二者，我尝试多种算法，并修改算法的初始化参数来得到更优的结果，比如用退火算法在一定概率内留下更好的一代，其实都挺玄学的，期间主要参考《现代优化计算方法》这本资料；对后者，我了解到一种 ZKW 算法是更高效的算最小流的算法（其实得视图的特点而定，但对本题来说是更优的），于是用 ZKW 算法替换了原来的算法。
经过优化的代码不负希望地进了 32，接下来就是看名词不断下跌了，压力蛮大，但是稳住似乎还是没问题的，但也就是在最后关头跌到 28 左右时，因为朋友比较担心被别人挤下去，于是提议重新提交一波，可能会拿到更稳的一个名次，最后关头我的心态也崩了，就同意了，结果再次提交的结果一不小心掉出了 32，结果当天在直到 Deadline 之前都在不断尝试提交…最后一次提交的结果是 40 来名，和期望有点差距，有些遗憾地结束了这一个多月的旅程。
总结
- 平时多积累代码，不是所有人都能靠临时冲刺搞定很多高难度的算法代码的；
- 越到关键时刻越要稳，不能将希望寄托到随机的东西上（很多启发式算法都是用随机数碰运气）。