2019华为软件精英挑战赛(00)开篇题型分析

0,问题汇总:

  ①自己的评价系统(用于随时随地检验效果);

  ②多因素参与决策的全局最优解计算(路线选择、车次先后、单双向道路、道路最高速与车速等);

  ③使用方法问题(遍历,Dijstra最短路径,floyd算法等等);

  ④优化迭代方向(人工逻辑推理优化、机器最优解寻找)。

1,背景信息:

  城市交通路线的统一调度用以实现最快速度的通行。(关键词:最短路径搜索、全局最优、动态规划)

2,题目定义:

  ①规划每辆车的行驶路线;②所有车辆按照规划的路线到达目的地。

3,系统假设:

  ①路口完全立交互联(没有转弯耗时计入);②无限神奇车库(类似《英雄联盟》中幻影之舞的被动效果-无视体积碰撞,单位无限叠加,)。

4,约束条件:

  ①不允许超车变道(一条道走到黑,中途不超车匀速);②排队先到先行(小号优先于大号,直行优先于转弯,左转优先于右转);③车道固定进入(优先进入小号车道)

5, 题目输入

  ①道路  道路数据文件“road.txt”文件

  每一行数据为一条道路 (道路id,道路长度,最高限速,车道数目,起始点id,终点id,是否双向)格式的向量。

  例如  (502, 10, 6, 5, 2, 3, 1)的向量表示编号为502的道路,连接路口2和路口3的长度为10,限速6的双向5车道路段, 是否双向:1:双向;0:单向

  ②车辆  车辆数据文件“car.txt”

  每辆车数据表示为:(车辆id,始发地、目的地、最高速度、出发时间)格式的向量。

  例如  (1001,1,16,6,1)的向量表示一辆编号是1001最高速度为6的车辆要在时间点1从路口1到达路口16;

  ③路口  路口数据文件“cross.txt”

  每个路口数据表示为:(路口id,道路id,道路id,道路id,道路id)格式的向量。注意:有的路口不满4支道路出口(1,2,3都有可能赋值为-1)

  例如(6, 504, 514, 505, 518)表示504,514,505,518这四条路段交汇的编号为6的路口。

6,答案提交

  选手应针对题目输入中的所输入的信息为基础,编写完整程序,输出“answer.txt”文件

  每一辆车的行驶路线规划,具体格式为(车辆id,实际出发时间,行驶路线序列)格式的向量。

  例如(1001, 1, 501, 502, 503, 516, 506, 505, 518, 508, 509, 524)即为上述1001号车辆自时间点1开始出发,从道路501、502、503…行驶至道路524的行驶路线。

7,评分规则

  ①系统调度时间短者胜出。系统调度时间指,从系统调度开始时间(非第一辆车实际开始运行的时间),至所有车辆全部到达目的地的时间,两者之差作为系统调度时间。

  ②若系统调度时间相同,则所有车辆的行驶用时总时间最少者胜出。一辆车在系统计算中达到目的地的时间点减去其最初计划出发的时间点,称为这辆车的行驶用时。

  ③若两队参赛选手的规划路线所有车辆的行驶用时总时间相同,则参赛选手程序计算出所有车辆行驶路线所运行时间最少者胜出。(该时间与前述时间不同,为程序运行时间,单位为ms)

  ④若参赛选手程序计算运行时间也相同,则先提交代码的队伍胜出。

参考网站:https://codecraft.huawei.com/Generaldetail

原文地址:https://www.cnblogs.com/Mufasa/p/10567758.html