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-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
  • 微信扫一扫
  • 支付宝扫一扫