Huawei CodeCraft 2016 复赛解析

复赛问题

给定一个带权重的有向图G=(V,E),V为顶点集,E为有向边集,每一条有向边均有一个权重。对于给定的顶点s、t,以及V的子集V’和V’’,寻找从s到t的两条不成环的有向路径P’和P’’,使得P’经过V’中所有的顶点,而P’’经过V’’中所有的顶点(对P’经过V’中顶点的顺序以及P’’经过V’’中顶点的顺序不做要求)。

若不同时存在这样的两条有向路径,则输出无解,程序运行时间越短,则视为结果越优; 若同时存在这样的两条有向路径,则输出得到的两条路径,按下列优先级从高到低评价结果优劣:
1、 路径P’和P’’重合的有向边个数越少,则视为结果越优;
2、 在两条路径重合的有向边个数一样的情况下,两条路径权重总和越少,则视为结果越优;
3、 在上述两个指标一样的情况下,程序运行时间越短,则视为结果越优。

说明:
1)图中所有权重均为[1,100]内的整数;
2)任一有向边的起点不等于终点;
3)连接顶点A至顶点B的有向边可能超过一条,其权重可能一样,也可能不一样;
4)该有向图的顶点不会超过2000个,每个顶点出度(以该点为起点的有向边的数量)不超过20;
5)V’和V’’中元素个数均不超过100,交集为空,且不包含起始顶点s和终止顶点t;
6)从s到t的不成环有向路径P是指,P为由一系列有向边组成的从s至t的有向连通路径,且不允许重复经过任一顶点;
7)路径的权重是指所有组成该路径的所有有向边的权重之和(重复边的权重应分别在两条路径中各计算一次)。

输入与输出

输入文件格式

以两个.csv文件(csv是以逗号为分隔符的文本文件)给出输入数据,一个为图的数据(G),一个为需要计算的路径信息(s,t,V’,V’’)。文件每行以换行符(ASCII’\n’即0x0a)为结尾。

1)图的数据中,每一行包含如下的信息:
LinkID,SourceID,DestinationID,Cost
其中,LinkID为该有向边的索引,SourceID为该有向边的起始顶点的索引,DestinationID为该有向边的终止顶点的索引,Cost为该有向边的权重。顶点与有向边的索引均从0开始编号(不一定连续,但用例保证索引不重复),顶点索引范围在[0,2000),有向边索引范围在[0,40000)。

2)路径信息中,只有一行如下数据:
DemandID,SourceID,DestinationID,IncludingSet
其中,DemandID里面第一行为1,第二行为2,表示路径索引,1表示P’,2表示P’’,SourceID为起始顶点s的索引,DestinationID为终止顶点t的索引,IncludingSet表示必须经过的顶点集合V’或V’’,其中不同的顶点索引之间用“ | ”分割,如果该路径没有必经顶点要求,则此处输入NA。

输出文件格式

输出文件同样为一个.csv 文件。
1)如果该测试用例存在满足要求的有向路径P’和P’’,则输出两行信息,第一行按P’经过的有向边顺序,依次输出有向边的索引,索引之间用“ | ”分割;第二行按P’’经过的有向边顺序依次输出有向边的索引,索引之间用“ | ”分割;
2)如果该测试用例不同时存在两条满足要求的有向路径P’和P’’,则只输出一行信息:NA;
3)每一行只允许输出最多一条有向路径,以换行符0x0a结尾。

求解算法

这是初赛问题的升级版,最简单直接的想法就是使用初赛的算法求两次路径,然后不断迭代,优化到重合边更少的可行解。但是,我们测试的时候发现,初赛模拟退火算法的收敛速度远远比不上复赛扩大的拓扑规模。面对这样的现实,我们只能改进初赛中路径的退火策略。

我们将初赛中的3-opt的退火方式改进为N-opt的退火方式,同时也对每一子迭代的过程中的寻路算法由Dijkstra改进为BFS,由此我们得到了非常快速的收敛速度。
由于我们时间非常紧张,实验室还有一堆活儿=.=,虽然通宵调试,但是整体实现仍然非常粗糙,还有多处来不及优化,导致比赛止步16强。这里是我们的算法实现。

0%