HuaweiCodeCraft2024-Final

KO | EN

gitlite — search

#javascript #typescript #llm #go #golang #android #machine-learning #docker #nodejs #awesome #cli #pytorch #mcp #open-source

HuaweiCodeCraft2024-Final

(★ 42)

2024 华为软件精英挑战赛决赛代码（初赛粤港澳赛区冠军，复赛粤港澳赛区冠军，全球总决赛第 4 名）

HuaweiCodeCraft2024-Final 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 2024 华为软件精英挑战赛

比赛基本信息：

- [2024华为软挑比赛官网](https://developer.huaweicloud.com/codecraft2024)
- [2024华为软挑宣传推文](https://mp.weixin.qq.com/s/9DLysYicqrx1mgqiDfQ2Lw)
- [2024华为软挑人民日报宣传片](https://wap.peopleapp.com/video/rmh40901762/rmh40901762)
- [总决赛赛题](https://bbs.huaweicloud.com/forum/thread-02107148304313640001-1-1.html)（docs目录中也有）
- [总决赛获奖名单](https://competition.huaweicloud.com/advance/1000042021/html13)
- [总决赛结果推文](https://mp.weixin.qq.com/s?__biz=MzIyMjAwNTU2Mg==&mid=2651077568&idx=2&sn=c7c8af782f809f2f89ee25b5e2aaed81&chksm=f3c48b95c4b302834c3c61c31cb186cf02ea9b1a466a97027121aaaaf5f8b90b96c27b09a168&mpshare=1&scene=2&srcid=0429mxdk36FwhpDmRiD7EQzJ&sharer_shareinfo=9a749603b1f7caea014b25fb36ba9d42&sharer_shareinfo_first=9a749603b1f7caea014b25fb36ba9d42#rd)

------

这是 2024 华为软件精英挑战赛 **“适可而止矣，涓埃之事，亦央原神”** 队的决赛代码。

我们属于**粤港澳赛区**，三名队员（[cq](https://github.com/OrangeQi-CQ)、[yhf](https://github.com/yhf4aspe)、[xsf](https://github.com/zzwtx)）都是来自**华南理工大学**的本科生。在2024华为软件精英挑战赛中成绩如下：

- 初赛：**粤港澳赛区冠军**
- 复赛：**粤港澳赛区冠军、全国第 2 名**
- 决赛：**全球总决赛第 4 名（季军/三等奖）**

PS：
1. 本仓库仅复制我们决赛所用仓库的 main 分支，也删除了 `judge` 目录中的判题器和回放器等。**由于决赛期间涉及华为的大模型，本仓库中删除了相关的接口地址与密钥，这会导致代码无法正常运行。本仓库仅作算法实现上的参考。**
2. 深大王前明小哥哥，人帅气质佳性格好，单身。

------

成功之处：

- 我们的代码实现能力比较强，能够高效准确地将想法落地并测试效果。有很多想法预期效果很好但实际徒劳无功甚至负作用，而个别想法看似普通却会有很惊喜的效果。我认为将 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`）。
- 海上调度：
    - （初赛）不需要特别的调度，哪里货物总价值多就去哪里。
    - （复赛）转化为旅行商问题，DFS 爆搜船的取货顺序。引入了泊位失活机制，在程序后期逐个失活泊位（按收货量），使得剩在泊位的货物尽可能少。
    - （决赛）用并查集将泊位分组，每组单独分配船并调度，船按权抢占空闲泊位。（见 `src/ocean_scheduler`）
- 海上控制：
    - （复赛、决赛）将船的位置+方向视为一个状态，使用 Dijkstra 算法计算每个泊位的距离矩阵（见 `src/map`）。赛后与中山大学 “SYSU_oms维修队” 的同学讨论本题其实可以用双端队列优化 BFS 做到 $O(N)$ 初始化，省下 `std::priority_queue` 的 $\log$ 复杂度（退役后啥都忘了……）
    - （复赛）如果检测到下一步会碰撞，则返回随机一个运动指令。（效果意外的出奇的好，平均几帧时间可以解决碰撞问题）
    - （决赛）轮船防碰撞使用启发式搜索（魔改的 Astar 算法）解决，可以实现多船完美防碰撞（见 `src/ocean_controller`）。

- 并发/并行（仅决赛）：决赛提供了双核，数据规模陡增，同时引入了通过网络与大模型交互的环节，因此必须通过并发/并行充分利用双核的优势。
    - 初始化：决赛有 `48`  个泊位，并且地图面积是初赛复赛的 `16` 倍。我们使用双核并行初始化泊位，在两个cpu 上分别跑两个线程初始化泊位，解决了泊位初始化超时的问题（见 `src/map`）。
    - 主线程：绑定到 `cpu0`，专注与判题器的交互、各种调度和控制算法（见 `src/main`）。
    - 大模型提问：实现了一个简易线程池。并发地向大模型提问。绑定到 `cpu1`（见 `src/question`）。
    - 货物搜索：实现了一个简易线程池。由于决赛中货物数量陡增，地图面积也是初赛复赛的 `16` 倍，每帧都搜索所有新增货物已经不现实。我们会在 `cpu0` 上实时搜索高价值货物，在 `cpu1` 上异步搜索性价比最高的低价值货物（见 `src/cargo`）。

------

决赛策略：

- 相比于“海贼王”和“机甲王”等流派，我们是很传统的策略，自己的机器人将货物送给自己的船。
- 我们用并查集将泊位分组，按照一定顺序，根据机器人和船的数量启动这些泊位组。机器人和船只考虑已经启动的泊位组。
- 通过练习赛的回放记录学习了浙大 “Eagle414” 队伍的策略：没货物的机器人只拾取高级货，若附近没有高级货就前往一个地方随时捕捉可能出现的高级货（宁可原地耗着也不取低级货）。我们的创新之处在于将没有货物的点视作 “虚拟货物”，同样参与费用流的二分图匹配过程，并且实现了更优秀的虚拟货物设置策略。

HuaweiCodeCraft2024-Final

HuaweiCodeCraft2024-Final 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

HuaweiCodeCraft2024-Final

HuaweiCodeCraft2024-Final 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README