阅读指南 · 19 章 / 约 2.7 万汉字 ① 从零入门 参赛感受 · 规则与反馈 · 完整计费 ② 理解几何 误差锥与半平面 · 直径的反例 · 四圆盘选点 · 精度与路程 ③ 读懂算法 全向发现 · 联合调度 · 定向覆盖 · 成对阴性 · 最终决策 · 有限终止 ④ 查看证据 实验分层 · 六次正式测试 · 用量统计 ⑤ 回到个人 最后优化为什么难 · 提交与经验 · 概念地图与资料 正文含原生数学公式、几何配图和真实动作 GIF;文末附可离线打开的交互阅读版。

<p><strong>交互演练 · 把最终算法放进浏览器</strong></p><p><a href="https://fxy-b-signal-lab.me-5a3c.chatgpt.site">打开 B 题信号搜索实验室 ↗</a></p><p>随机生成 10—16 个干扰源,在你的电脑上实际运行最终 Q3 / Q4 算法。可以选择边界密集或聚集分布、调节定向源比例与误差场,暂停、单步、拖动时间轴,观察测向锥、可行域、轨迹和逐项代价。点击已知信道,再用地图 ◎ 按钮放大几何细节。</p><p>这是自建合成演练,不是正式测试成绩。首次运行需加载 Python / NumPy 环境;计算在读者浏览器内完成,观察者真值不会参与策略决策。网站与运行必需的最终算法源码已获授权公开。</p>交互演练 · 把最终算法放进浏览器 打开 B 题信号搜索实验室 ↗ 随机生成 10—16 个干扰源,在你的电脑上实际运行最终 Q3 / Q4 算法。可以选择边界密集或聚集分布、调节定向源比例与误差场,暂停、单步、拖动时间轴,观察测向锥、可行域、轨迹和逐项代价。点击已知信道,再用地图 ◎ 按钮放大几何细节。 这是自建合成演练,不是正式测试成绩。首次运行需加载 Python / NumPy 环境;计算在读者浏览器内完成,观察者真值不会参与策略决策。网站与运行必需的最终算法源码已获授权公开。

01 写在前面:我为什么觉得这道 B 题特别难

“今年的 B 题,和 A、C 题以及往年的题,根本不是一个难度。”

这是我做完这次比赛后最直接的感受。这里的“难度”是我的参赛体感,不是对所有历史题目做过统一评测后得到的排名。但我希望把这句话展开:究竟是什么让这道题如此难?难在公式长,代码多,还是运行时间紧?

我的答案是,它把几个通常可以分开处理的问题绑在了一起。你既要研究测向数据所允许的全部几何位置,又要决定下一步去哪儿;既要把发现、定位和清除放进同一个流程,又要给出“没有遗漏”的依据;既要优化平均速度,又不能让某个不走运的输入把程序拖进无穷循环。到最后,局部的一点进步,很容易碰坏另一个环节的前提。

我后来还有一句更直接的感受:“特别是最后的算法设计,我觉得根本就是没有最优解,光靠人脑也想不出优化方案。”数学上,我们没有证明最优解不存在。更准确地说,我们没有求得、也没有证明全局最优;当各种决策相互影响时,单靠直觉,已经很难找到一个稳定更好的组合。后文会专门解释这种感觉从哪里来,以及 AI 在其中到底帮了什么忙。

这篇文章比正式论文更慢地展开。论文需要在有限篇幅内陈述模型、证明和结果;这里给那些第一次接触题目的人补上被压缩的中间台阶:为什么想到这个量,为什么这个推理成立,为什么一个很自然的判断反而不成立。如果你只看最终的两行成绩,会错过这道题真正有意思、也最磨人的部分。

全文以我提供的最终提交材料为准:《论文源码最终版.pdf》共 32 页,支撑材料为 139.rar。采用方案是问题三的稀疏环联合调度、问题四的 21 站覆盖与锚定定位。过程中出现过的其他研究版本,不因为目录更新或数字更漂亮就自动成为本文主角。我们讨论最终留下来的系统,同时保留它尚未解决的问题。

先把结果放在这里,后面再解释它们意味着什么。问题三三次正式测试累计清除 36 个源,逐局每源虚拟耗时均值为 280.120 秒;问题四累计清除 42 个源,对应均值为 403.339 秒。正式测试没有公开真实源总数,所以这两行不是“官方全清率”的另一种写法。六份日志的上传状态有归档证据,但上传成功也不是获奖或评分结果。

下面的回放来自 Q4 第三次正式测试。青线连接机器狗实际发出的动作位置,橙点标记成功清除动作发生的位置。它们不是隐藏的干扰源坐标;一次清除允许有 20 米距离,因此把清除位置直接当成真实源,会给动画加上日志中并不存在的信息。回放按动作序列等间隔播放,虚拟时间取日志读数,不能用动画的快慢推断现实运行速度。

阅读时可以记住贯穿全文的四个问题:目前知道什么?还可能是什么?下一步做什么?凭什么现在能结束? 第一问主要回答第二个,第二问着重回答第三个,后两问把四个问题接成了一套真正行动的系统。

fxy-blog-01-formal-replay.gif

02 第一层:先把题目翻译成一个可以运行的世界

想象一个圆形区域,半径为 1800 米,里面藏着若干静止的无线电干扰源。机器狗可以移动、选择频道检测、尝试光学定位并清除目标。题目给出的不只是几个坐标计算任务,而是一个带反馈的行动环境:你发出动作,环境返回有限的信息,然后你根据这些信息决定下一步。

第三、四问中,真实源数在 10 到 16 之间。频道从 1 到 20 中选取,而且一个频道至多对应一个源。这使“频道”成为追踪目标的标识:今天在这里收到频道 7,下一步在另一处又收到频道 7,在题设静态模型中,两次观测约束的是同一个源。反过来说,没有出现的频道既可能没有源,也可能只是还没被发现。

每个源的有效接收半径在 1000 到 1500 米之间。1000 米是保证接收距离的下界;1500 米是一次有效观测能够给出的最大距离信息。这两个数不能混用。拿 1500 米去设计“保证能发现”的站点覆盖,会把接收半径实际只有 1000 米的合法源漏掉;把一次已接收源的距离上界写成 1000 米,又会误删仍然可能的远处位置。

在问题三中,源是全向辐射,只要距离进入真实接收半径,就有接收条件。问题四允许定向源:除了距离足够近,测站还必须位于源的某个闭 180 度发射半平面。这里“闭”意味着边界也包含在接收侧。这个小词会进入后面的凸包证明,并不是可以随意省略的修饰。

三种检测反馈到底告诉我们什么

正常示向反馈给出一个方向角,同时说明机器狗在该源接收范围内,且距离大于 5 米。方向有误差,因此它并不告诉你一条精确射线上的点,而是告诉你“真实方向位于报告方向左右一定角度之内”。这是一条几何约束,不是一个坐标答案。