ROOT
ROOT
文章目录
  1. 体验
    1. 2017-04-25 20:18
    2. 2017-04-09 22:40
    3. 2017-04-04 10:27
    4. 2017-04-03 12:19
    5. 2017-04-02 20:02
    6. 2017-04-01 21:13
    7. 2017-03-30 23:21
    8. 2017-03-29 21:34
    9. 2017-03-29 20:49
    10. 2017-03-28 16:23
    11. 2017-03-25 15:20
    12. 2017-03-25 10:58
    13. 2017-03-25 09:55
    14. 2017-03-25 00:24
    15. 2017-03-24 22:00
    16. 2017-03-22
  2. 程序输出
    1. caseDemo.txt
    2. case0.txt
    3. case1.txt
    4. case2.txt
    5. case3.txt
    6. case4.txt
  3. 思路
    1. 2017-04-25 20:25

2017 华为软件精英挑战赛参赛心得

2017.03.23 Netcan 随笔  热度 ℃

体验

2017-04-25 20:18

比赛终于要结束了，最终复赛没能进前四，止于中游。自从上周三把数据规模调大后，名次一直哗哗掉，无法挽救，试过好几种方案，没能搞定换挡问题，也就是说给你最优位置，你都找不到最优解，真是可怕。

复赛题目加了个档次条件，相当于 2 个 NP 问题了，一个是选址问题，一个就是换挡问题了。

目前复赛代码已开源：https://github.com/netcan/2017-HUAWEI-Codecraft/releases/tag/2.0

初赛的思路已经更新，可以翻到 最后。

2017-04-09 22:40

今天复赛题目放出来了，增加的条件如下：

  • cdn 有好几个档次了，每个档次都有输出流量限制
  • 每个网络节点增加部署费用
  • 节点数量上万

考虑复赛后一周有 6 门左右的考试，所以要早点写了，不然爆零那多尴尬。。。

2017-04-04 10:27

之前因为交的程序可能概率性段错误，所以必须修复 bug 重新提交，防止最后重跑的话出事就 gg 了。然而修复了 bug，却很难最优，这两天提交无数次，中级才出现过 2 次最优，弃坑了。复赛再搞起。

说一下关于定时器的问题吧，我用的是 alarm 定时器，非常精确，用它定时，时间一到会给进程发送 SIGALRM 信号，只需要捕捉这个信号，然后进行退出处理就行了。

2017-04-03 12:19

现在来说一下如何统计输出文件的 cdn 数量吧，懒得在代码中添加统计最终可行解的 cdn 数量了。

根据官方输出格式可知，第一行表示链路数量，第二行空行，那么从第三行开始就是起始链路了。链路的第一个数就是 cdn 的节点编号，从而可以统计出最终 cdn 数量。

$ time ./bin/cdn case_example/The\ second\ batch\ of\ test\ cases/2\ Advanced/case0.txt o
$ awk  'NR > 2 {printf $1; printf("\n") ;}' o | sort -g | uniq | wc -l
 109

首先用 awk 从第三行开始，提取第一列，也就是 cdn 编号，由于有重复编号，需要排序去重，最后统计出行数就是 cdn 数了。

如果要输出 cdn 的编号，可以这么做：

$ awk 'NR > 2 {printf $1; printf("\n") ;}' o | sort -g | uniq | tr '\n' ' ' && echo

2017-04-02 20:02

今天遇到一个非常致命的 bug，我在本地测试的时候，有时候会出现 段错误，而且几率非常小，那是多么的恐怖，连复现定位都异常困难。

不过这个问题难不倒我，既然是有几率复现的，那么我只要记下程序开始运行的时间戳（因为我的随机种子是设置为时间戳），然后复现的时候，设置这个时间戳，重新跑，就能定位出错误了。

不断重复跑了将近一小时，才出现 段错误，最后定位到的问题是对象没有初始化。。。

2017-04-01 21:13

今天愚人节。。昨晚看到 ftp 下载失败，得了 0 分，吓的一大早起来交，却不能交，感觉前十大换血一样 = = 莫名慌张。

不过看到校友 silverfly 在 20 多名，心里还是稳了，因为我们交流过，都是启发式。

现在贴一下战绩吧，三个样例没跑好，等排名掉了在重新交一下吧。（PS: 大规模样例曾跑出 199055 的满分成绩，三组数据成绩都需要看脸）。

Screenshot_from_2017-04-01_21-11-37.png

Screenshot_from_2017-04-01_21-11-55.png

这里我补充我最近遇到一个特别脑残（也很有意思吧）的 bug，肯定是没睡醒导致的。

我昨天跑启发式算法的时候，发现 88 秒能迭代 5000 多次呢（能达到跳出条件），瞬间觉得不可思议，我把迭代系数调大，目的让它能慢一些，结果还是能在 88 秒内达到跳出条件，不过这个时候，迭代 58 万次 = =，费用流能跑这么多次？？也正是这个 bug，导致我一天白调参了。

为了更具体的说明，我举个例子，仅供参考。

int iterationCnt = 0;
while(T > 0.1) {
	for(int i = 0; runing && i < N; ++i) {
		...
	}
	...
	T *= delta;
	++iterationCnt;
}

这里的 runing 标记位，等到达足够的时间，会变为 false，考虑到内循环花的时间比外循环长，我很天真的把runing 标记位放到内循环中，以便 runing 变为 false 的时候能够及早跳出，不会超时。也正是这个原因，我为我 88 秒内能跑 5000 多次费用流（迭代次数）而自豪。

前面我说了，把迭代系数调大，能跑 58 万次呢。我隐隐约约觉得这是个bug，但是又感觉不到哪里有问题。

然后我打算给外循环也加上 runing 位，即

while(runing && T > 0.1)

跑了一下，发现 88 秒居然只迭代了 200 多次！我只是在外循环加个 runing 位而已，性能损失 20 倍？！

不管了，和队友打红色警戒三了。

现在切入正题，为何我把 runing 加在外循环会导致性能“损失”。其实放到外循环才是真实的迭代次数，因为只放到内循环，那么当 runing 变为 false 的时候，导致内循环不干活，外循环拼命跑，直到达到跳出条件…

2017-03-30 23:21

经过一天的优化、调参，基本稳定了。坚持到最后吧。

Screenshot_from_2017-03-30_23-09-56.png

2017-03-29 21:34

做了点微小的贡献，希望能攒点人品。

Screenshot_from_2017-03-30_07-38-12.png

2017-03-29 20:49

最近很多同学问我，怎么输出路径，老是超流。前面说过了不能保存增广路径，却没说怎么找路径，那我在这里细说一下吧。

跑费用流的时候，算法基本上都是找增广路径，比如某条边上流过的流量为 3/5（斜杠后面的表示满流为 5），那么它的反向边变为 -3/0（同理，因为流量为负，满流为 0），这个表示我以后可能会流过 -1, -2, -3 的流量，亦即 回流 （细说一下，比如流过 -1，表示我从 3 变为 2，实际上流过的流量为 2），所以光保存增广路径是不行的，因为算法后面有可能 回流 ，一回流，那么实际流量可能会减少，而你之前保存了，那么当然会 超流。

现在来说说跑完费用流后怎么保存实际路径。跑完费用流后，边上流过的流量是知道的。所以可以从源点出发，进行深度优先搜索（同时记录这条路径上的最小流量），直到找到汇点，那么保存这条路径。而从汇点回溯的时候，就扣除这部分的流量，如果这个点的流量 还有，那么就访问这个点的下一个点，直到找到汇点，然后保存路径，再回溯，以此类推。

这里我举一个例子吧，正在作图，稍后继续。 dfs.png

加入源点是 0，汇点是 5，跑完费用流后，得到如上所示的流量分布。

  1. 从源点 0 开始出发，进行深度优先搜索，比如走到 1，记录此时的最小流量 3，然后从 1 开始出发，走到 3，记录此时的最小流量 1，接着从 3 出发，走到汇点 5，那么保存这条路径（0->1->3->5，流量为 1）。
  2. 从汇点 5 回溯，回溯到 3，减去该点流量：1-1=0，没有流量了，继续回溯，回溯到点 1，减去该点流量：3-1=2，还剩有流量，那么不回溯了，接着从 1 走到它的下一点 4，记录最小流量 2，从 4 走到汇点 5，保存这条路径（0->1->4->5，流量为 2）
  3. 从汇点 5 回溯，回溯到 4，减去该点流量：2-2=0，没有流量了，继续回溯，回溯到点 1，减去该点流量：2-2=0，没有流量了，继续回溯，回溯到源点 0，这时候源点流量为 3 这条边流量用完了，那么选择下一个邻接点 2，记录最小流量 2，从 2 走到下一个汇点 5，记录这条路径（0->2->5，流量为 2）

经过以上几个步骤，所有路径都找出来了。

2017-03-28 16:23

现在掉到 20 来名了，经过这两天的尝试 / 优化，终于把小规模数据的时间 / 效率提上去了，费用能跑到21920，可是中规模和大规模跑的不是很好分数比较低，达到瓶颈了，比大佬差那么个几千吧。

Screenshot_from_2017-03-28_16-50-27.png

2017-03-25 15:20

刚刚群里有位同学和我一样，只保存了增广路径作为结果，最后我们都是因为这个导致流量超了。

昨晚我能想到的原因是有可能输出的路径带有负流量，比如要求 5，你输出了 3 条路径 3、3、-1，虽然符合要求，但是 3+3=6 就有可能超。

然后跑了一晚上样例，没发现有负流量，觉得可能官方数据有可能会触发负流量，然后通过时间来判断是不是因为官方数据触发了负流量，结果也没有。

真是个坑。。

2017-03-25 10:58

寻路部分已解决，目前提交几次都有分了。大概是这样的： Screenshot_from_2017-03-25_06-54-56.png

2017-03-25 09:55

官方判题服务器没有问题，我的费用流保存的是增广路径，所以流量超了，已经重写了寻路那部分。

2017-03-25 00:24

可能官方判题器出现 bug 了，现在又在修复，应该是判断链路流量是否超过总带宽的那部分错了，有人把容量调为一半，就有分了。

睡觉睡觉，等待修复，希望明天一大早就给我惊喜吧。

2017-03-24 22:00

昨天官方数据有重边 bug，后 2 组没分，没什么意义，就不管代码了。

今天官方修复了 bug，一大早就起来提交，结果比较奇葩了，前 2 组没分，第 3 组倒有。有时候就只有第 2 组没分，反正就是第 2 组没分。

判题大哥说我 流量超了 ，仔细检查了好久，直到刚刚（21 点），才感觉到哪里不对劲了，改了改，应该有分了， 功夫不负有心人。这个漏洞比较有意思，非常难发现，本地测试的时候还没触发过，等赛后再更新吧。

由于官方评测系统的数据和练习用的数据规模差不多，~~ 这里直接上结果好了。~~ 比直连大法好就行了，毕竟我前几天还是用直连大法呢。

2017-03-22

华为挑战赛去年就了解到了，一直没参加，记得去年是道经过指定结点的最短路，今年一看题，想了好久没头绪（YY 一个方案，写的时候发现不可行，浅尝辄止），居然有点后悔去年没参赛。

一开始就先写了一个将 cdn 全部放消费结点的方案，那时候名次还很好，20 左右。直到昨天跌出 40，形势刻不容缓。

3 月 21 开始查看相关资料（建议看算法导论最大流那章，理解了残余网络，增广路径就好办了），写了最小费用流，3 月 22 一早上加一下午写了输出费用流路径，然后开始考虑选址问题，开始用随机算法，每次随机选几个服务器，跑来跑去的解都比全放消费结点的成本高。

接着写了一晚上的启发式搜索，因为初始参数的原因，导致自己一直怀疑算法有问题，却又坚定不移，期间也由于 STL 使用不当 (erase/insert) 导致非常难调的 bug。

之所以一直没放弃，是因为我跑样例的时候，偶而出现那么几次可行解，虽然只比全部放消费结点便宜了那么几块钱，但仍让我觉得可行。

就在 12 点熄灯的那一刻，我几乎快要绝望了，就在最后，我调下参数，观察了一下输出，想看看最后的结果，结果让我大吃一惊，居然是最优解（群里有人发过）！然后我忍不住又试了两组数据，也是最优解，最后样例一次性全部跑出！！瞬间心态爆炸。。

PS: minCost(2042/2340)表示跑出来的可行解为 2042，2340 表示 cdn 全部放消费节点直连的服务器上所需要的费用。 Screenshot_from_2017-03-23_00-27-55.png

然后就想试试大规模数据，从群里下了个 1500 结点的数据跑了下，得了如下可行解，可能不是最优解，但总比全部放消费结点好吧。 Screenshot_from_2017-03-23_00-34-19.png

心情已经非常激动了，这个比赛让我非常有成就感，比我大学做过的事情有意义多了，从来没有这么开心过，非常感谢华为。

正好赶上官方更新初中高级数据，还没来得及跑分就关闭系统更新了。。太耐人寻味了。

程序输出

这是针对官方练习样例跑出来的结果：

caseDemo.txt

这组样例是官方 题目介绍 的图：

$ time ./bin/cdn case_example/caseDemo.txt o
line num is :62
Deploy CDN(3):
3 22 0
=====Solution======
3->3 flow: 45
22->2 flow: 28
22->24->11 flow: 11
3->19->5 flow: 24
3->24->11 flow: 12
0->16->6 flow: 8
0->8->0 flow: 36
0->7->10 flow: 10
3->1->19->5 flow: 2
3->1->16->6 flow: 7
3->2->25->9 flow: 7
0->9->11->1 flow: 13
0->6->5->8 flow: 13
0->2->25->9 flow: 8
3->1->18->17->4 flow: 2
0->1->18->17->4 flow: 9
0->1->15->13->7 flow: 11
0->2->4->5->8 flow: 5
0->2->1->15->13->7 flow: 2
22->21->8->0 flow: 4
Flow :257/257 Cost: 783/1200

case0.txt

为了说明路径 /CDN 位置的随机性，这里随意给出了 2 组最优费用，但是路径 /CDN 位置不一样：（其实是一样的，真尴尬）

$ time ./bin/cdn case_example/case0.txt o
line num is :110
Deploy CDN(7):
7 37 15 13 22 43 38
=====Solution======
7->3 flow: 22
37->4 flow: 46
15->6 flow: 49
13->5 flow: 40
22->2 flow: 36
43->0 flow: 24
38->7 flow: 63
13->3->32->34->8 flow: 8
43->44->1 flow: 15
Flow :303/303 Cost: 2042/2340
./bin/cdn case_example/case0.txt o  22.40s user 17.75s system 99% cpu 40.167 total

case1.txt

$ time ./bin/cdn case_example/case1.txt o
line num is :111
Deploy CDN(7):
17 6 7 41 48 13 35
=====Solution======
35->0 flow: 57
13->5 flow: 99
48->6 flow: 82
17->7 flow: 27
6->2 flow: 32
7->3 flow: 28
41->4 flow: 25
6->5->1 flow: 10
7->9->0->22->23->8 flow: 21
Flow :381/381 Cost: 2136/2520
./bin/cdn case_example/case1.txt o  23.02s user 17.42s system 99% cpu 40.441 total

case2.txt

$ time ./bin/cdn case_example/case2.txt o
line num is :127
Deploy CDN(6):
48 18 29 38 12 23
=====Solution======
23->2 flow: 47
12->6 flow: 41
38->0 flow: 58
31->7 flow: 34
48->8 flow: 47
18->3 flow: 80
29->4 flow: 70
23->21->5 flow: 13
18->22->21->5 flow: 37
12->10->13->0->6->5->1 flow: 4
Flow :431/431 Cost: 1692/1890
./bin/cdn case_example/case2.txt o  19.03s user 14.30s system 99% cpu 33.344 total

case3.txt

$ time ./bin/cdn case_example/case3.txt o
line num is :111
Deploy CDN(5):
10 35 26 29 22
=====Solution======
26->5 flow: 55
35->8 flow: 50
10->7 flow: 32
29->4 flow: 22
22->2 flow: 64
22->21->3 flow: 22
35->33->6 flow: 6
10->0->4->47->0 flow: 5
22->20->21->3 flow: 7
22->24->21->3 flow: 18
10->0->2->3->31->1 flow: 1
29->27->3->31->1 flow: 13
35->32->4->47->0 flow: 23
35->32->33->6 flow: 10
35->34->33->6 flow: 12
Flow :340/340 Cost: 2111/2700
./bin/cdn case_example/case3.txt o  16.56s user 12.22s system 99% cpu 28.788 total

case4.txt

$ time ./bin/cdn case_example/case4.txt o
line num is :113
Deploy CDN(7):
20 12 22 37 15 48 26
=====Solution======
20->0 flow: 22
12->6 flow: 52
22->3 flow: 31
26->1 flow: 16
48->4 flow: 20
15->5 flow: 70
37->8 flow: 31
37->38->2 flow: 13
37->3->28->7 flow: 17
12->2->4->3->28->7 flow: 3
37->36->38->2 flow: 1
37->40->38->2 flow: 5
12->16->41->38->2 flow: 3
Flow :284/284 Cost: 1967/2160

思路

我用多源多汇最小费用最大流 + 启发式算法来解决这个 NP hard 问题。

2017-04-25 20:25

现在来更新思路可能有点晚了，由于复赛成绩不理想，我就说说我初赛是怎么做的吧。

初赛代码：https://github.com/netcan/2017-HUAWEI-Codecraft/releases/tag/1.0

启发式我试过模拟退火、遗传算法、粒子群算法、禁忌搜索，最终选择了 遗传模拟退火 算法相结合来实现。

先说说初始状态，最后我们选择对 直连 状态进行 删点 作为初始状态，删点按照消费节点流量需求从小到大删，如果删了费用变小就删，否则不删，直到处理完所有消费节点，得到初始状态。

接下来的是 遗传模拟退火 算法，可以参考《现代优化计算方法（第二版）》第 4.5 节。

遗传用 bitset 进行 01 编码，长度为网络节点数量，0 表示不放，1 表示放。

  1. 首先初始化种群数、温度，迭代次数，我只有一条个体是初始状态，其他都是随机。
  2. 进行模拟退火阶段，遍历种群中的个体，计算费用，生成新的状态（寻找邻域内的状态），计算新状态的费用，接受概率为 若接受则作为新种群个体，否则丢弃，用回，同时更新最小费用。这个阶段遍历完后，新种群数应为。
  3. 在新种群中，遍历各个个体，计算其适应度：
  1. 然后按照轮盘赌进行选择、交叉、变异操作，最终得到一个种群，将这个种群作为步骤 2 的种群，更新温度，更新，执行步骤二。

当温度达到最低温度，或者时间到了，输出整个过程中的最优可行解。

关于退火中选择的邻域状态，我是从当前状态，随机选一个点 ，然后在随机选这个点的邻接点，将当前状态的 点改成 点，作为新的状态。形象点来说就是选一个点移动到它下一个点。

支持一下
扫一扫，支持Netcan
  • 微信扫一扫
  • 支付宝扫一扫