队名:西北小靓仔
初赛成绩:西北21名
复赛成绩:西北24名
文件介绍:
code1:初赛代码
map1:初赛地图
code2:复赛代码
map2:复赛地图
思路简单介绍:
1.根据地图信息创建双向图。
2.对车进行预处理(排序),确定发车顺序。
3.根据双向图利用Dijstra或者Floyd确定车的路径。
4.每一辆车经过一条道路则为此道路增加权重。
5.权重挥发。即除了道路本身所具有的的权重,后来增加的权重都具有挥发性,让其以一定速率进行挥发
(求小星星)
初赛思路分析:
1.根据地图信息创建双向图。
道路权重 = 道路长度 / 道路车道数。 再将道路权重进行归一化,让基础权重在0和10之间。
2.对车进行预处理(排序),确定发车顺序。
现将所有车按照发车时间排序,再按照速度从大到小的顺序排序。先发快速车,再发慢速车,减小慢车对快车的影响。
3.根据双向图利用Dijstra或者Floyd确定车的路径。
初赛采用的Floyd算法求最短路径,时间复杂度较高O(n3), 正式赛中数据集增加了很多,导致我们的运行时间增加了上百倍,模型是基于调参的,七分钟左右的运行时间让我们顶不住,参数没有调到最优。复赛中换成了Dijstra算法,运行时间大大减小。
4.每一辆车经过一条道路则为此道路增加权重。
在代码中有一个道路容量的概念,道路容量 = 道路长度*车道数。当有一辆车经过一条路时,为此条路所增加的权重为:拥挤度权重 = Q / 道路容量。其中Q为我们定义的一个常量,需要根据地图信息进行调整。我们初赛和复赛都是用的Q = 200。
关于道路权重:
道路权重可以分为两个部分,其中一部分是我们在1中初始化的一部分权重称为基础权重,也就是和道路本身属性相关的,这部分权重与车经数量无关。另外一部分权重是车经过道路带给道路的影响,可以称之为拥挤度权重,其定义如上所示。最终权重为这两部分权重之和,根据总权重确定最短路径。
5.权重挥发。
即除了道路本身所具有的的权重,后来增加的权重都具有挥发性,让其以一定速率进行挥发。
第二部分权重 拥挤度权重 所带给道路的影响是有时间的,当车驶出这条道路时,这部分权重就需要减去,但是我们没有判题器,无法判断车什么时间走完这条路,所以定义了一个权重挥发的概念。在代码中我将其定义为常量Dec = 0.85;
时间片每增加一个,让这部分权重挥发一次:挥发后的总权重 = 基础权重 +(挥发前总权重 - 基础权重 )* Dec;
其中Dec需要根据不同的地图进行调整,也可以定义为变量,根据车经过路的时间长短改变Dec。
6.发车策略。
将车按照时间、速度排序之后,简单的按照时间片分批发车,每发出一辆车更新一次权重,每增加一个时间片挥发一次权重。
复赛思路分析:
复赛由于事情较多,耽误了一些时间,也没有想到好的解决方案,只能继续采用初赛的模型。
在初赛的基础上做了一些较小的改变,就去参加比赛了,惨败而归。。。
1.车先根据时间排序,在根据速度排序,最后根据优先级排序。保证先发优先级较高的车。
2.关于预置车,到预置车时间点就让它发车,之后再继续发非预置车。
具体分析请看我的博客:https://www.cnblogs.com/qiang-wei/p/10705503.html