华为软挑代码开源及思路介绍
代码开源在这里。分 Python 和 C++ 版本,起先是用 Python 实现的系统逻辑,后来任务数据量上来 Python 运行太慢,就换成 C++ 了。
CodeCraft219-Cpp
2019 华为软挑 赛后源码整理
2019 华为软件精英挑战赛代码 Repo
- 江山赛区队伍:今天是 2019 年 3 月 29 日农历二月廿三多云
- 初赛赛区第三
- 复赛赛区十四
代码结构
- CodeCraft-2019
- CMakeLists.txt
- CodeCraft-2019.cpp:主程序 Main 函数入口
- trafficManager.cpp/trafficManager.h:模拟器(根据判题逻辑实时更新车辆 / 道路 / 路口状态)和调度器(车辆上路策略和更新路径策略)
- car.cpp/car.h:车辆类(记录车辆对象静态信息 + 更新车辆动态信息)
- road.cpp/road.h:道路类(记录道路对象静态信息 + 更新道路动态信息 + 道路内移动车辆)
- cross.cpp/cross.h:路口类(记录路口对象静态信息 + 跨路口调度车辆)
- dijsktra.cpp/dijsktra.h:图模型构建 + 最短路径搜索
- utils.cpp/utils.h:赛题文件读取
最短路径搜索
Dijkstra’s Shortest Path Algorithm
先使用邻接矩阵表征,时间复杂度 O (v^2);后来使用 邻接表 + 优先队列,时间复杂度 O (ElogV)。
Ps:第一次感受到降低时间复杂度的重要性
参考链接:
Dijkstra’s Shortest Path Algorithm using priority_queue of STL
Single-Source Shortest Path:Dijkstra’s Algorithm
发车策略 + 动态换路 + 路权函数
跟大神的差距就差在这了。一个人没下功夫琢磨(忙,忙,忙!)。
发车策略
很 low 的策略。
初赛(按车辆发车)
- 车辆按照起点分布分组,按照出发时间排序。每个地点依次抽一辆车放入出发序列。
- 设置场上运行车辆数目上限。
复赛(按道路发车)
- 初始化所有车辆的路径,将车辆分配给该车起始道路。
- 每条道路对管辖的车辆进行排序(分优先序列和非优先序列)。
- 设置场上运行车辆数目上限。
- 遍历道路,在上限内每条道路依次发车(1-2 辆)。
动态换路
很 low 的策略。
路口对象对时间片内调度次数进行统计,越多则表示该路口车辆情况越不乐观。
时间片内判断最大的路口调度次数,超过阈值,则场上车辆进行抽样,更新路径(当前位置至目的地)(更新一半或更少是防止出现扎堆现象)。
路权函数
很 low 的策略。
两个因素:
- 道路:统计道路内车辆数目,计算占比,得到权重。
- 路口:统计时间片内路口调度次数,作为权重,更新到连接该路口的道路。
以上两因素,更新整张地图的拓扑,从而更新抽象图(用于最短路径搜索)。