2016华为软件精英挑战赛：赛题及其答疑汇总

注：本文文字均摘自官方指定网站和论坛，权威且可信，答疑见中间部分，非常全，众玩家可放心阅读。

同时文末给出了包括自己在内的诸多玩家的解法。

前言

赛题源自“未来网络”业务发放中的路由计算问题。算路问题属于基础算法问题，在图论、网络、交通等各个方面均有着广泛的研究与运用，里面不乏一些经典的算法，例如最短路中的广度优先搜索，Dijkstra算法等。网络算路问题的更优算法实现对于网络资源高效配置具有重要价值。 1 问题定义 给定一个带权重的有向图G=(V,E)，V为顶点集，E为有向边集，每一条有向边均有一个权重。对于给定的顶点s、t，以及V的子集V’，寻找从s到t的不成环有向路径P，使得P经过V’中所有的顶点(对经过V’中节点的顺序不做要求)。
若不存在这样的有向路径P，则输出无解，程序运行时间越短，则视为结果越优；若存在这样的有向路径P，则输出所得到的路径，路径的权重越小，则视为结果越优，在输出路径权重一样的前提下，程序运行时间越短，则视为结果越优。
说明： 1）图中所有权重均为[1，20]内的整数； 个人吐槽：没有复权值，经典Dijkstra算法可能适用
2）任一有向边的起点不等于终点； 个人吐槽：极端情况被踢出，减小难度 3）连接顶点A至顶点B的有向边可能超过一条，其权重可能一样，也可能不一样； 个人吐槽：不一样就取较小者
4）该有向图的顶点不会超过600个，每个顶点出度(以该点为起点的有向边的数量)不超过8；
5）V’中元素个数不超过50； 个人吐槽：指定点集越多，耗时越夸张，难点之一，优化点之一。
6）从s到t的不成环有向路径P是指，P为由一系列有向边组成的从s至t的有向连通路径，且不允许重复经过任一节点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和。
2 输入与输出 输入文件格式 以两个.csv 文件(csv 是以逗号为分隔符的文本文件)给出输入数据，一个为图的数据(G)，一个为需要计算的路径信息(s,t,V’)。文件每行以换行符(ASCII’n’即0x0a)为结尾。

1）图的数据中，每一行包含如下的信息：
LinkID,SourceID,DestinationID,Cost
其中，LinkID 为该有向边的索引，SourceID 为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost 为该有向边的权重。顶点与有向边的索引均从0 开始 编号(不一定连续，但用例保证索引不重复)。
2）路径信息中，只有一行如下数据：
SourceID,DestinationID,IncludingSet
其中，SourceID 为该路径的起点，DestinationID 为该路径的终点，IncludingSet 表示必须经过的顶点集合V’，其中不同的顶点索引之间用’|’分割。
输出文件格式 输出文件同样为一个.csv 文件。
1）如果该测试用例存在满足要求的有向路径P，则按P 经过的有向边顺序，依次输出有向边的索引，索引之间用’|’分割；
2）如果该测试用例不存在满足要求的有向路径P，则输出两个字符NA；
3）只允许输出最多一条有向路径。


3 单个用例的评分机制 有解用例的排名机制 按下面流程对参赛者结果进行排名： Step1： 对于提交的结果，进行合法性检验(详见题目描述)； Step2： 程序运行时间不得超过10s； 若不满足上述的结果则本用例得分为0；

Step3： 计算提交的路径的权重，权重越小，排名越优； Step4： 在权重相同的结果里，用程序运行时间进行排名，时间越短，排名越优。 无解用例的排名机制 按下列流程对参赛者结果进行排名： Step1： 对于提交的结果，验证是否识别出该用例无解，若无法识别或者算法运行时间超10s，则本用例得分为0； Step2： 用程序的运行时间进行排名，时间越短，排名越优。 单个用例的评分标准如下： 根据上面排名流程得到的排名，使用标准分计分(排名第一的提交者为100分)。
若所有人均未得到正确结果，则所有人均得分为0。
4 最终得分机制 平台会使用N个测试用例判题，该N个测试用例分为初级、中级、高级三个等级，参赛者对于每个测试用例都会得到一个百分制分数，使用加权平均分(初级权重为0.2，中级权重为0.3，高级权重为0.5)作为该参赛者的最终得分。
特别说明：在比赛初期，平台只放出初级、中级的测试用例，故此时满分为50分，在比赛后期，才会放出高级测试用例（具体发放时间会在网站公告通知），此时满分才为100分，请各位参赛者注意。
5 简单用例说明


在如上图所示的有向图中，我们会得到下面的有向图信息： 0,0,1,1
1,0,2,2
2,0,3,1
3,2,1,3
4,3,1,1
5,2,3,1
6,3,2,1
如果此时需要寻找从0到1的路径，且必须经过顶点2和3，我们会得到如下的路径信息： 0,1,2|3 对于该用例，可以找到如下两条可行路径:
1|5|4
2|6|3
由于第一条路径的权重为4，第二条路径的权重为5，所以此时最优解应该1|5|4。


运行环境 CPU：Intel Xeon CPU E5-2690 V2 @ 3.00GHz
内存：2G
内核：单核
编译器：gcc 4.8.4；java 1.7.0_95；
操作系统：linux Ubuntu 14.04.3 LTS，内核版本 Linux version 3.13.0-24-gineric
SDK：为方便选手做题，分别提供c++(兼容c）和Java SDK包供参考（见赛题下载包），详细描述信息请见SDK目录下的readme.txt。


讨论交流 武长赛区QQ群 117280759
杭厦赛区QQ群 131946455
上合赛区QQ群 221036348
粤港澳赛区QQ群 493667385
西北赛区QQ群 389603273
南京苏州赛区QQ群 545377507
京津东北赛区QQ群 271699173
成渝赛区QQ群 537141027 ————————————————————————————————————————————————- 赛题答疑： 1、节点出度不超过8，是一个需要利用的条件吗br> 当然是了，这会影响到你的数据结构的设计。通过节点数加上出度可以计算出来这是一个稀疏图
2、这个问题的复杂度可以有足够时间算出最优解吗br> 不求最优，只要胜过别人即可
3、图的顶点数不超过600个，但输入的顶点号最大值会不会大于600br> 不会超过600
4、10s包括读写文件的时间吗还是search_route运行时间
你认为IO需要多久一下就会带给你惊喜
5、那个 我问一下哦 是不是经过V’中的节点不是一定要连着的 就是说 可以经 过一个V’中的 经过一个V’外的 而不是一口气全部要经过V’中的
当然了
6、请问s,t在v’中吗br> 不在。其实在与不在没有质的改变，在里面只会增加费时的操作，要考察的是算法，不是这些无关的东西
7、高级数据以后也是要十秒计算时间吗
是的，10s对于求近似解已经足够长了
8、如果自己写io，最后都要提交什么参考readme介绍
9、顶点1指向2会有不同权值的多条边br> 会的，这个是与教科书上的图有不同的
10、请问题中所有节点都不允许重复经过吗的
11、连接顶点A至顶点B的有向边可能超过一条，其权重可能一样，也可能不一样；—-是不是使用权重最小的那个就可以了，其他的也没什么用。
初赛阶段你可以这么做，我只能说这么多
12、节点的索引连续吗
一般来说是连续的，但是制作用例很麻烦，极个别情况可能不连续
13、N个测试用例分为初级、中级、高级三个等级，请问每个等级的节点数目范围大概是多少br> 节点数不是唯一衡量问题复杂度的维度，还要考虑图的样子等等方面
14、什么时候出高级样例br> 大家PK的时候会有高级用例。作为调测用例，越复杂越不便于调试
15、请问中级的测试用例试顶点数目不变,只是边变化吗br> 顶点数目不是衡量复杂度的唯一维度
16、吴老师您好，请问初等中等高等难度分别怎样的占总分的比重和比赛时总的测试是多少个br> 难度的设定比较复杂，不一定是顶点数多就复杂。具体的占比初步计划是5:5:5，但是有可能会有调整
17、后面大家还要考虑路径拥塞问题
18、代码是以最后一次提交为准吗，出高级样例之后还能改代码吗
初赛结束前都可以改，而且还有复活赛，没有晋级的同学这个时候也可以修改代码调优
19、对于这个问题，你们专家组，有没有好的想法么比赛只是 找出比别人的好就行，
只要找出比别人好的就可以，所以就是跟自己的历史程序比，只要进步了就有机会
20、那你们的测试用例，对于有无解 ，总有答案吧。
是的
21、请问后面复赛和决赛的网络规模会变大么果变大，可能的规模是多少（这个涉及算法设计的）
顶点不会超过600
22、能保证测试数据格式正确么不会突然冒出来一个特殊字符
我们会尽全力保证不出这样的问题，即使出了也会最快的速度更正的
23、np-hard问题据资料说倾向于不存在证明意义上的最优解，不知道专家们是不是有方法能找出最优解，还是和很多同侪们一样只是在概率意义上逼近寻找所谓最优解的
我们不需要知道最优解，因为是各组选手之间PK
24、最后是在Linux环境下编译运行吗平时 调试时能否在windows下进行
你在win下调试了，我们也不知道呀
25、大家注意一下，初级用例不一定就简单，每个人的算法侧重都不一样，完全可能高级用例做得出来，但是初级的做不出来的情况
26、官方的测试用例，应该会给出 有解和无解的情况吧， 有解 就看谁的最优， 可以这样理解么
正确
27、请问一般情况下这个程序的平均执行时间是多少毫秒 br> 时间不是关键问题，你要PK赢了cost，哪怕是用满了10s也比别人1s的厉害
28、平台验证程序大概是怎么个流程啊br> 这个说来话长了。简单说，每个程序判题之前我们会重启虚拟机，所以不用担心前人把内存泄露光了的问题
29、题目中说顶点与有向边的索引均从 0 开始编号(不一定连续，但用例保证索引不重复)，这里的不连续怎么理解果只有三个顶点可以用0 、1、5这样表示br> 基本不会出现这样的问题
30、是否还要考虑算法稳定性，每个测试样例验证几次br> 一锤子买卖，如果你人品爆发，那就恭喜你了
31、大家注意一下，初级用例不一定就简单，每个人的算法侧重都不一样，完全可能高级用例做得出来，但是初级的做不出来的情况。
官方的用例应该包括各种情况，来应对不同的算法（每个算法的侧重不同），我想问的是，你们测试我们的程序时，会把所有的官方用例都测完吗后 统一 一下每组的排名么，还是对于每组的测试用例 随机选择。
所有测试例全跑
32、专家是否推荐几篇论文
引用论文的算法，这个需要分析好，避免承担版权责任啊
比如说我用数组存储索引号，那在定义索引号的值时我的容量到底应该定义超过多少呢10个br> 600足矣
33、出这个题目的背景br> 开幕式会讲
33、类似tsp吧
有相似性，但要想清楚哪里不一样，这个就自己想一想，不能再多说了
34、启发式算法是要拼人品的
也不一定
35、吴老师，顶点的入度呢，你们对入度有限制嘛br> 这个就随意了，没有限制
36、如果用暴力搜索，会不会特别费时间br> 有的时候不用犹豫，直接肯定自己就好了
37、设计多少顶点合适
题目中都有介绍，600个
38、最多会有多少条边
出度是8，最多600点，肯定最多4800边啊
39、给程序运行的内存有多大br> 虚拟机2G内存
40、会不会有空点存在br> 没有意义的事情，不会浪费大家时间的，不会有空点
41、吴老师 你们有没有官方自己的程序果有，拿官方程序能跑测试用例能跑多少分，时间是什么水平br> 裁判员当运动员不好吧，没有
42、吴老师，从s到t的不成环有向路径P中，是严格不允许重复经过任一节点吗是可以通过该节点的不同入边进入br> 严格不允许，否则就出环了
43、吴老师，一开始说所谓稀疏图的判断，是不是对这个问题有优化br> 稠密图和稀疏图设计数据结构的方法可能不同的
44、请问入度有可能为0呢br> 当然可能，对入度不做任何限制
45、毕竟裁判员算是标准答案
这是一场对抗性比赛，所以没有标准答案
46、这些必经点分布上是均匀的吧，，，
最好不要这么想，否则会吃亏的
47、我想问一下，能保证路径文件不包含多余空格么空格正则匹配会比较复杂，(会不会多花时间啊)，还要trim
如果有空格，那就一个文件变成两个文件了，没有空格
48、吴老师这个问题是不是应该用多种判断方法，从特殊到一般会不会比较省时间
可以这样判断，当然也可以用通杀的算法，这完全取决于你的算法设计
49、现所给的样例和最终的测评样例难度一样吗br> 用例难度只是一种人为的评判，不具有精确的量化数据
50、最终知识产权归本队所有吧br> 在大赛官网有介绍
51、权值的意义是代表接入网络设备的个数吗br> 你可以认为是时延
52、吴老师，有向边会不会有起点和终点一样，权重不一样的
有可能会有
53、初级，中级，高级测试用例，有没有严格的界限，比如边的条数等
负责任的设计用例就没有，如果不负责任的设计用例那就简单了。所以说没有界限，问题的难度不止取决于顶点和边的数量，还有很多复杂的东西要考虑
54、感觉比赛有一定的人品在里面
有可能
55、一个程序一次在一个机子上跑完所以的测试吗
是
56、@老师，这个问题复杂之处在哪里br> 我们对这个问题难度定义为NP-Complete的级别
57、再统一说明一下，这个问题的复杂之处不仅仅在于顶点个数和边的个数。还要考虑如何不成环
58、最后会对代码有具体的评估吗是只看运行结果br> 需要评估，至少不能抄袭，否则影响比赛的公平，对吧
59、请问，必经结点的实际意义体现在什么地方谢
这个在开幕式上会有介绍。简单说一下吧，比如需要到某个站点做数据处理。例如在线看一段视频，格式源和最终播放的格式不一样，需要到指定站点做转码。
60、怎么来确定边的权重，是自己输入的吗
赛题介绍中有说明，可以看一下输入那一段
61、降低计算不就是看运气了
不完全是，如果算法稳定，运气的成分就不重要了
62、@老师，这道题目和华为主题未来网络有何关系，或者说题目背景
保留一点神秘感，待到开幕式上揭晓吧。如果到时候很多人还是不明白，我承诺专门写一篇文字介绍清楚，可好br> 63、不会多花时间啊)，还要trim，如果有空格，那就一个文件变成两个文件了
我指的是1,2,3,4这样的路径会不会出现空格
不会，本题的考察点重点在于算法，不会在这里难为大家的
64、感觉就是一个异化的哈密顿通路问题，加上了权重，然而并没有最优解
汉密尔顿问题也没有要求最优解
65、如果是双连通分量，是不是可以判定无解br> 你说的双连通分量指的是什么br> 双连通是指一个点需要经过两次
是的，成环的路径是不符合要求的。那就是无解
66、吴老师 所有难度的题目中必经节点占总结点的比例br> 没有这个比例的限制
67、吴老师,17号提交的时候排名就是固定的用例吗后的初赛阶段用例是变化的还是固定的2个（初级&中级）
19号开通提交通道。如果用例没有错误，是不会更换用例的。初赛过程中先放出初级和中级的用例，第二次会增加高级用例。
感觉得拉一个学数学的来
可以呀，就是一种数学建模
68、吴老师 所有题目中无解样例多么，能说个大概比例么不br> 这个不太好说
69、官方可以多提供一些测试案例不软件精英挑战赛命题组专家–吴迪
这个对每一组都是公平的
70、吴老师，每个小组是不是在最后都有复活赛的机会br> 只要你的改进足够大，就可以复活
71、那您意思就是初赛只有初、中级用例二次是什么意思。。。
复活赛之前，会分两次把所有用例放上去
72、吴老师，据说华为内部算法对600个点可以在10ms内给出一个解，是真的吗
这样的算法有，但不是可以解决所有用例，是有针对性的算法。这次比赛也是希望发现在这方面有特长的同学
73、吴老师，在计时系统中，使用Java是否有时间上的补偿ava运行的太慢了。@软件精英挑战赛命题组专家–吴迪
没有补偿。时间不是关键，关键是cost足够小
74、关于奖励，是每人一份还是全队一份（既然没人问……）
全队一份
75、，，，弄的我想转成c++代码了
对于这个赛题算法为王
76、Cost指权重之和吗br> 如果你问的是P的cost，那么是，P是指最后输出的路径
77、这样的算法有，但不是可以解决所有用例，是有针对性的算法，也就是说您在设计图的时候是否尽量避免了某些特殊情况br> 不排除这种可能性
78、普通算法不容易通过所有测试用例。
是的
79、这种图如何分类，比如华为跑10ms的算法针对哪种图br> 没有明确的分类方法
80、10秒是怎么运行呐，不用定时退出吧，只要十秒内有保存
10s内有输出即可
81、一个用例只能跑一次吗用机器学习做下，能不能给第二次机会软件精英挑战赛命题组专家–吴迪
你可以把10s分成10个1s
82、有解和无解分开排名 但测试的时候有解和无解是打乱放的吗算成绩的时候再把他们区出来br> 是的
83、有解和无解分开排名 但测试的时候有解和无解是打乱放的吗算成绩的时候再把他们区出来br> 是的
84、我想问每个节点是按顺序给出吗的标号也是按顺序给出吗
基本上是
85、请问给出的测试用例case1中的这条路径是不适最优路径是只是一条最优路径br> 就算你求出了最优解，也没有办法验证就是最优
86、给个建议，有必要出解一个存一下吗
用SDK无法支持你的方法，需要你自己实现IO了
87、是否存在多条满足题意的路径使得cost最小，如果权值一样，就拼时间咯
什么叫拼时间，是指输出任意path就行么
权值一样时，看谁的运行时间短
———————————————————————————————————————————-
大赛邮箱：codecraft@huawei.com
大赛网址：http://codecraft.huawei.com ———————————————————————————————————————————-
这里链接一个很早就写出程序的玩家：
http://blog.csdn.net/lwtdzh999/article/details/50804713
———————————————————————————————————————————-
同时给出自己的低级案例（50个顶点以内）最优解的解决方案—深度优先暴力破解。 这种解法将能够使前五个案例得满分。 2016华为软件精英挑战赛：低级案例—暴力出奇迹（一）
高级案例的算法设计，该算法无法完全解出最后面10个中高级案例，只能解决前8个，最后两个无法解出！ 2016华为软件精英挑战赛：高级案例—贪心策略（二）
———————————————————————————————————————————- 参考资源：
【1】http://bbs.csdn.net/topics/391911624age=1
【2】大赛网址：http://codecraft.huawei.com
【3】CSDN论坛，http://bbs.csdn.net/forums/hwcodecraft
文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33946 人正在系统学习中

来源：EbowTang