比赛基本信息:
这是 2024 华为软件精英挑战赛 “适可而止矣,涓埃之事,亦央原神” 队的决赛代码。
我们属于粤港澳赛区,三名队员(cq、yhf、xsf)都来自华南理工大学。在2024华为软件精英挑战赛中成绩如下:
- 初赛:粤港澳赛区冠军
- 复赛:粤港澳赛区冠军、全国第 2 名
- 决赛:全球总决赛第 4 名(季军/三等奖)
PS:
- 本仓库仅复制我们决赛所用仓库的 main 分支,也删除了
judge
目录中的判题器和回放器等。由于决赛期间涉及华为的大模型,本仓库中删除了相关的接口地址与密钥,这会导致代码无法正常运行。本仓库仅作算法实现上的参考。 - 深大王前明小哥哥,人帅气质佳性格好,单身。
成功之处:
- 我们的代码实现能力比较强,能够高效准确地将想法落地并测试效果。有很多想法预期效果很好但实际徒劳无功甚至负作用,而个别想法看似普通却会有很惊喜的效果。我认为将 idea 快速落地并测试是在华为软挑取得好成绩的关键。
- 有一点点算法基本功(三人都有 icpc/ccpc 银),但相比其他一些队伍并不亮眼。
- 虽然没有单元测试,但编写了很多集成测试,帮助我们迅速定位没有正常达到目标的模块。
- 临时抱佛脚学习了 git(之前只会用 zip 压缩+微信传代码)、cmake、clang-format 等工具,并写了一些 python 和 shell 脚本。利用工具提升效率。
不足之处:
- 三人都没有大厂实习经验,缺乏项目合作开发的流程。例如没有需求和交付的流程和文档,git 分支混乱,git 流程不规范,缺乏设计模式的使用等。
- 在决赛中,策略过于保守(意图避免出大错,也不算是一件坏事)。
项目结构:
docs
:决赛的官方文档judge
:决赛的判题器和回放器(本仓库已删除)scripts
:一些脚本src
:核心代码test
:决赛前期针对大模型的测试文件
这里不谈具体的细节,只一句话概括各个模块的大致算法:
-
路上调度:
- (初赛、复赛、决赛)计算机器人-货物匹配的收益矩阵(大体是价值/距离),并动态限制在每个泊位工作的机器人数量,转化为带分组约束的二分图最大权匹配问题。构造分层图,通过最大费用最大流算法求解,得到实时贪心意义下的理论最优解(见
src/land_scheduler
)。 - (初赛、复赛、决赛)若机器人上一帧与当前帧匹配目标不相同,只有价值增益比例超过一定阈值才改变目标。利用并查集将新老目标重叠的机器人分组,同一组的机器人同时改变目标或不改变(见
src/land_scheduler
)。
- (初赛、复赛、决赛)计算机器人-货物匹配的收益矩阵(大体是价值/距离),并动态限制在每个泊位工作的机器人数量,转化为带分组约束的二分图最大权匹配问题。构造分层图,通过最大费用最大流算法求解,得到实时贪心意义下的理论最优解(见
-
路上控制:
- (初赛、复赛、决赛)BFS 获得每个货物与泊位的距离矩阵(见
src/cargo
,src/berth
)。若不考虑碰撞,沿距离矩阵下降的方向运动即可到达目标货物或泊位(见src/land_controller
)。 - (初赛、复赛、决赛)为了解决碰撞问题,使用并查集将存在碰撞风险的机器人分组,组内 DFS 爆搜不碰撞条件下的最优解,通过剪枝提升搜索性能(见
src/land_controller
)。 - (决赛)为了避免其他队伍的机器人堵成墙,同时为了避免爆搜的潜在掉帧风险,我们在 BFS 预处理的基础上结合实时搜索小范围内的运动方向最优解(见
src/land_controller
)。
- (初赛、复赛、决赛)BFS 获得每个货物与泊位的距离矩阵(见
-
海上调度:
- (初赛)不需要特别的调度,哪里货物总价值多就去哪里。
- (复赛)转化为旅行商问题,DFS 爆搜船的取货顺序。引入了泊位失活机制,在程序后期逐个失活泊位(按收货量),使得剩在泊位的货物尽可能少。
- (决赛)用并查集将泊位分组,每组单独分配船并调度,船按权抢占空闲泊位。(见
src/ocean_scheduler
)
-
海上控制:
- (复赛、决赛)将船的位置+方向视为一个状态,使用 Dijkstra 算法计算每个泊位的距离矩阵(见
src/map
)。赛后与中山大学 “SYSU_oms维修队” 的同学讨论本题其实可以用双端队列优化 BFS 做到$O(N)$ 初始化,省下std::priority_queue
的$\log$ 复杂度(退役后啥都忘了……) - (复赛、决赛)轮船防碰撞使用爆搜解决(见
src/ocean_controller
)。
- (复赛、决赛)将船的位置+方向视为一个状态,使用 Dijkstra 算法计算每个泊位的距离矩阵(见
-
并发/并行(仅决赛):决赛提供了双核,数据规模陡增,同时引入了通过网络与大模型交互的环节,因此必须通过并发/并行充分利用双核的优势。
- 初始化:决赛有
48
个泊位,并且地图面积是初赛复赛的16
倍。我们使用双核并行初始化泊位,在两个cpu 上分别跑两个线程初始化泊位,解决了泊位初始化超时的问题(见src/map
)。 - 主线程:绑定到
cpu0
,专注与判题器的交互、各种调度和控制算法(见src/main
)。 - 大模型提问:实现了一个简易线程池。并发地向大模型提问。绑定到
cpu1
(见src/question
)。 - 货物搜索:实现了一个简易线程池。由于决赛中货物数量陡增,地图面积也是初赛复赛的
16
倍,每帧都搜索所有新增货物已经不现实。我们会在cpu0
上实时搜索高价值货物,在cpu1
上异步搜索性价比最高的低价值货物(见src/cargo
)。
- 初始化:决赛有
决赛策略:
- 相比于“海贼王”和“机甲王”等流派,我们是很传统的策略,自己的机器人将货物送给自己的船。
- 我们用并查集将泊位分组,按照一定顺序,根据机器人和船的数量启动这些泊位组。机器人和船只考虑已经启动的泊位组。
- 通过练习赛的回放记录学习了浙大 “Eagle414” 队伍的策略:没货物的机器人只拾取高级货,若附近没有高级货就前往一个地方随时捕捉可能出现的高级货(宁可原地耗着也不取低级货)。我们的创新之处在于将没有货物的点视作 “虚拟货物”,同样参与费用流的二分图匹配过程,并且实现了更优秀的虚拟货物设置策略。