2024 华为软件精英挑战赛初赛总结

今年三月，受一起实习的好哥们邀请，参加了今年的华为软件精英挑战赛。已经多年没有参加比赛的我又一次体会了大学时候大家一起在实验室中攻克难关，互相帮助和鼓励的时光。说实话虽然很过度消耗精力，很累人，但是非常开心。

赛题介绍

赛题详细资料可以移步官方论坛查看。

我简单概括一下：

首先会有一张地图，地图是在程序初始化阶段由标准输入给出的，为 200*200 的字符矩阵，利用不同的字符，定义好海洋、陆地、泊位、障碍以及机器人等地图元素。

判题器会与竞赛软件通过标准输入输出做交互。首先传输初始化数据给竞赛软件，待竞赛软件初始化完成，反馈“OK”之后，评分正式开始进行。评分分周期进行，最多 15000 个周期，每个周期有 5ms 用作判题器处理，剩下时间给竞赛软件处理。理论上处理多久都可以，但 5min 时判题会结束，此时没有跑到的周期全部作废（处理不及时发生丢帧）。如果处理得快，win 和 mac 版本的判题器会有不同表现，win 版本判题器会等待到 15ms，再发下一帧数据；mac 版本的判题器会直接进入下个周期。

每个周期内，判题器会告知竞赛软件当前帧机器人以及船只的信息、帧数与分数、新增的货物等。竞赛程序需要依据这些信息给出机器人与船只的控制指令，机器人可以移动、拾取、放置；船只可以移动、停靠。

正式比赛时会有多张地图，所有地图得分总和高者排名靠前，区域前 32 名进入决赛。

地图元素特性

货物：货物在生成时会有其价值，每个货物只会在地图上存在 1000 帧，竞赛软件需要记忆它并且通过帧数来判断其是否消失。
机器人：机器人每帧只能行动一格，但当前帧可以同时取/放物品+移动；只有四个方向，不能越过障碍。
船只：无需控制其具体路径，只需发送“去往 x 号泊位”指令，一段时间后自动到达。船有容积上限。
泊位：泊位有一个属性指明了船只从该泊位到市场，与从市场到该泊位需要的时间，船只从这个泊位前往市场卖货需要经过这一段时间。每个泊位还有装载速度属性，代表船每一帧可以从该泊位取走多少货物。

分析

经过小组成员的头脑风暴，我们得出了以下信息点：

物品能产生的价值跟“物品与泊位的距离”、“物品本身的售价”和“物品与机器人的距离”有关。
泊位无容量上限，但是如果机器人卸货速度大于船的装载速度，泊位中的货物会堆积。
船只可以在泊位间调度，但是需要时间；船只卖货需要时间，取决于从哪个泊位出发；船只从市场到泊位需要时间，也取决于去哪个泊位。
启动时有 5 秒钟用来初始化，可以在此期间进行多次 DFS，维护地图上每个坐标到每个泊位的最短距离信息。

利用以上信息，我们制定了如下的策略：

基本思想是，以泊位为中心，定义泊位优先级，船只和机器人优先满足优先级高的泊位。定义机器人和船只的运力，如果满足优先级高的泊位之后，机器人和船只运力有盈余，则将剩余运力分布至次优泊位。

泊位中心策略

泊位上接船只下接机器人，非常适合作为决策的中心点。

每个泊位维护一个优先队列，其中从大到小维护着“对本泊位最有价值的货物”。货物价值 $(v)$ 、货物到本泊位的距离 $(d)$ 以及货物本身的价值 $(m)$ 之间满足如下关系：

v = \eta m - \lambda d

其中 $\eta$ 和 $\lambda$ 是用来调整的参数；d 为理论上地图该点到泊位的最短距离，由程序初始化阶段进行 DFS 求出的表查得，复杂度为 $O(1)$ 。

泊位控制器 (berth controller) 维护一个优先队列，其中从大到小维护着“产生最大价值的泊位”。泊位价值 $(b)$ 、泊位物品价值总和 $\sum_{i=1}^nv_i$ 、泊位卖货时间 $t$ 以及泊位装载速度 $l$ 之间满足如下关系：

b = \alpha\sum_{i=1}^nv_i + \beta l - \gamma t

其中 $\alpha$ 、 $\beta$ 和 $\gamma$ 是用来调整的参数。

船只调度

初赛简化了船只控制，只需在合适的帧命令其前往哪个地方就行，等时间到船只就会自动出现在那个地方。

即使在这种情况下，船只要考虑的东西也很多：

船只从市场到泊位需要时间，需提前规划；
船只从一个泊位到另一个泊位需要时间，需决策直接去卖还是到价值高的泊位继续装货；
当时间到达接近末尾时（取决于船只所在泊位的卖出时间），所有船只都应去卖货，防止时间到达时货物未售出；

直接说结论吧，我们尝试了不少策略，最终发现最简单的就是最有效的：

船卖完东西的一瞬间，直接前往当前剩余物品最多且没有船只前往，也没有船只停泊的泊位；
当泊位中物品被装载完全，船会等待一个超时时间，超时时直接前往市场；
当剩余时间只够船只前往市场时，船无条件前往市场。

机器人调度

机器人模块是完全由我实现的模块，我的思想是将机器人看作一个整体，对外暴露两个接口：创建任务/取消任务，创建任务接口告诉机器人整体如下信息：

任务优先级
需要运送的目标点
需要运送的物品优先队列
需要的运力（每帧需运送到达的物品数）

之后，机器人控制器 (robot controller) 会找到未被满足的优先级最高的任务，并指派机器人去完成它。

为达到这个目的，我们需要创建如下的实体：

地图：用作 A* 算法的实时寻路，不使用 DFS 算出的最短路径表格是因为那样很难处理“独木桥”场景；
任务列表：任务列表依据任务优先级有序，每一任务会记录目前在运行的机器人运力，因此容易知道哪些任务已被满足；
机器人：机器人维护自身的状态机，状态机如下图所示：

注意事项

有关 A* 算法相关的内容，可以移步之前的文章：

A算法初探究及优化 - 自动解贪吃蛇
 A算法深入探究 - 使用Qt和C++实现带权重版本的A*
A算法扩展 - 三维A

机器人控制器
- 取消任务时，不能直接删除任务，因为可能有机器人正在执行此任务。可以将对应任务的优先级置为最低，等所有机器人交付时再删除之；
- 机器人会在同一帧行走，所以如果一个机器人寻到路径之后，应将其位置在地图上更新，防止两个机器人同时踏上独木桥，造成两个机器人反复在独木桥入口震荡。
机器人
- 泊位装载速度很高，所以容易有很多机器人汇聚在泊位周围的情况，此时如果不做处理可能会导致机器人拥堵，需要设置合适的排队机制；
- 如果丢帧过多，可能机器人在物品消失前已经无法到达物品处了，需要转而接取其他任务；
- 接取任务时，要确保如下条件满足：任务运力未被满足；机器人可达泊位（查表）；机器人可达物品。