Skip to content
2019华为软件精英挑战赛 初赛(江山排名3/64)和复赛(江山排名14/32) c++源码 实时调度
Branch: splitRun
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
CodeCraft-2019
3223F32C.png
README.md
build.sh
build_and_run.sh

README.md

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

发车策略+动态换路+路权函数

跟大神的差距就差在这了。一个人没下功夫琢磨(忙,忙,忙img)。

发车策略

很low的策略。

  • 初赛(按车辆发车)

    • 车辆按照起点分布分组,按照出发时间排序。每个地点依次抽一辆车放入出发序列。
    • 设置场上运行车辆数目上限。
  • 复赛(按道路发车)

    • 初始化所有车辆的路径,将车辆分配给该车起始道路。
    • 每条道路对管辖的车辆进行排序(分优先序列和非优先序列)。
    • 设置场上运行车辆数目上限。
    • 遍历道路,在上限内每条道路依次发车(1-2辆)。

动态换路

很low的策略。

路口对象对时间片内调度次数进行统计,越多则表示该路口车辆情况越不乐观。

时间片内判断最大的路口调度次数,超过阈值,则场上车辆进行抽样,更新路径(当前位置至目的地)(更新一半或更少是防止出现扎堆现象)。

路权函数

很low的策略。

两个因素:

  • 道路:统计道路内车辆数目,计算占比,得到权重。
  • 路口:统计时间片内路口调度次数,作为权重,更新到连接该路口的道路。

以上两因素,更新整张地图的拓扑,从而更新抽象图(用于最短路径搜索)。

You can’t perform that action at this time.