103 lines
8.1 KiB
Markdown
103 lines
8.1 KiB
Markdown
# 第三、四问算法审核与优化
|
||
|
||
依据：原始 `issue/B题.pdf` 第1—3页，重点为附录2(3)(4)，并结合(1)(2)(5)(6)(8)与第三、四问要求。
|
||
审核起点为 `9cf9428` 的程序；最后一次官方第三问演练为 `3BW5-9R54-NZNA-MYB9`，
|
||
13/13源成功清除、虚拟总时间4058.709750秒。本轮改进验证使用本地模拟器，没有启动或消耗官方测试。
|
||
|
||
## 1. 题设约束及审查结论
|
||
|
||
附录2(3)中的交会是有宽度的角域交集。不能把两条示向线的交点当作精确真值，
|
||
也不能利用同地重测求平均缩小±1°误差。程序已保留完整角域及0.005°舍入裕量，
|
||
本轮继续使用该证据颁发清除证书。统计评分仅用于选点，不能替代保守几何证书。
|
||
|
||
附录2(4)要求逐频道检测，换频1秒；结合(5)，每次停靠检测5秒且不能在移动中检测。
|
||
已有HTTP客户端是串行的，没有把20频道视为一次免费测量。缺陷在于规划成本和站点利用：
|
||
|
||
| 审核发现 | 影响 | 当前改进 |
|
||
| --- | --- | --- |
|
||
| 已停靠点只测UNKNOWN频道，已发现频道容易错失交会机会 | 之后为第二条方位线另走一段路 | 对DETECTED频道预测收缩；当前位置到整个候选集均小于1000m、未在此处测过且预测半径减少35%时，逐频道补测；每次仍支付5秒和实际换频成本 |
|
||
| 定位选点只计到测点的移动 | 测完后到清除区域的路程没有进入选点目标 | 加入候选检测点→候选源中心的接近代价，保留后续根据真实响应重新规划 |
|
||
| 候选方向固定在全局角度网格 | 与当前交会几何不对齐，可能产生多余绕行 | 增加以当前位置到候选中心为轴的对称候选；均仍位于距离保证盘内 |
|
||
| 路线代价中的service_s按初始频道一次估计 | 2-opt比较不同顺序时没有正确传递频道状态 | 路径成本逐任务传递频道，站内当前频道优先，clear保持频道；两个任务也比较完整开放路径成本 |
|
||
| 清除默认走到候选集包围圆心 | 未利用20米光学定位/清除范围 | 在证书允许范围内向当前位置平移目标；平移距离+原包围半径不超过阈值，保留三角不等式证明 |
|
||
| 七站环半径可调但没有执行覆盖校验 | 不合法调参可能把“都没测到”误作不存在 | 构造时检查解析覆盖界；不满足条件直接拒绝运行 |
|
||
| 第四问盘外探点无信号也可能记为定向遮挡 | 把接收距离不足误诊为已确认定向 | 仅当实际探点位于距离保证盘内才据无信号确认定向；盘外无信号保留不确定性 |
|
||
| 第四问发现一个源就离站定位，后续频道再返回原站 | 同站频道间产生长距离往返 | 保留49站定向覆盖，先逐频道扫完本站，再按当前位置就近处理已发现源 |
|
||
| 后备清除按初始位置距离静态排序 | 狭长候选集可能反复折返，且循环内无虚拟预算检查 | 每一步从当前位置选最近未处理格，并逐次检查虚拟预算 |
|
||
|
||
第三问所有源均为全向，才能用no_signal排除1000米圆盘。第四问源类型与朝向未知，
|
||
no_signal还可能是半平面遮挡，不能用上述排除规则，也不能直接沿用七站缺席证明。
|
||
本轮没有把BayesLoop套到第四问；第四问继续采用49站覆盖和独立的定向定位/后备清除。
|
||
回归用例包含(1800,0)向外发射的源：七站全无信号，49站中有站可检出。
|
||
|
||
七站覆盖界为 `max(r/√3, sqrt(R²+r²−√3Rr))`，前提是`0<r≤√3R`。
|
||
当前R=1800m、r=1159.7m，通过小于1000m的校验。网格滤波额外带Voronoi裕量，
|
||
故无源时仍可能留下边界格；此时完整七站覆盖可以证明缺席，不要求PF一定为空。
|
||
|
||
## 2. 验收口径
|
||
|
||
4000秒目标按整场虚拟总时间（包含移动、换频、全部检测、清除和缺席确认）比较，
|
||
没有在4000秒强行停止，也没有以只清除部分源或最后一次成功清除的时刻代替总时间。
|
||
题面表格的平均定位清除时间仍等于总时间除以实际清除源数。
|
||
|
||
第三问优化开发集固定为种子0—5、10/16源，加两个最小接收半径的圆周边界场景（14场）。
|
||
选择实现后停止调整，再运行种子100—105、10/13/16源的独立验证集（18场）。
|
||
同场景前后使用相同位置、频道、有效半径和逐点固定误差种子。
|
||
真值只传给本地模拟器和执行后的校验，不提供给算法；全部请求和响应保存。
|
||
|
||
有效运行要求：全部真实源清除、没有误判真实频道缺席、正常exit、无算法异常、逐步耗时复算一致。
|
||
|
||
| 第三问指标 | 旧版 | 改进后 |
|
||
| --- | ---: | ---: |
|
||
| 开发集全清且有效 | 14/14 | 14/14 |
|
||
| 开发集平均总时间 | 3812.97s | 3390.88s |
|
||
| 开发集最大总时间 | 5535.13s | 4624.97s |
|
||
| 开发集中小于4000s | 10/14 | 12/14 |
|
||
| 独立验证集全清且有效 | 18/18 | 18/18 |
|
||
| 独立验证集平均总时间 | 3799.72s | **3315.89s（减少12.73%）** |
|
||
| 独立验证集最大总时间 | 4569.47s | **3981.74s** |
|
||
| 独立验证集中小于4000s | 12/18 | **18/18** |
|
||
|
||
两个人工圆周边界场景改进后仍为4145.19s、4624.97s左右。因此本轮实现达成的是
|
||
独立验证组每场小于4000秒，**不是对全部合法题目场景的最坏时间保证**。
|
||
旧官方案例已经结束，无法对新路线查询其未知响应；本地结果不冒充官方同案例重跑。
|
||
更新后的官方成绩仍需新演练验证，不能由前后不同案例的数字直接得出提升比例。
|
||
|
||
## 3. 第四问结果
|
||
|
||
固定四场：10源/3定向，种子0、1；16源/8定向，种子2、3。覆盖朝向未知场景，
|
||
每场源分布与误差种子前后相同。旧版、改进版均4/4全清、正常退出、零异常和零计时偏差。
|
||
|
||
| 场景 | 旧版总时间 | 改进后总时间 |
|
||
| --- | ---: | ---: |
|
||
| 10源，种子0 | 18599.317s | 13652.140s |
|
||
| 10源，种子1 | 16709.225s | 14918.134s |
|
||
| 16源，种子2 | 16388.604s | 11635.398s |
|
||
| 16源，种子3 | 16983.270s | 12453.274s |
|
||
| 平均 | 17170.104s | **13164.737s（减少23.33%）** |
|
||
|
||
第四问尚未降到4000秒。保留域外49站是为未知朝向源提供发现证据；本轮优化减少重复移动，
|
||
没有用第三问假设缩小第四问覆盖范围。其后备清除仍是有预算上限的算法，不能据四场结果声称所有混合场景必定在预算内完成。
|
||
|
||
## 4. 数据及复现
|
||
|
||
- 第三问数据根目录：`output/q3/optimization-20260911/`，含冻结旧版代码、配置、逐场景真值、动作日志、summary及汇总。
|
||
- 最终开发集：`development/improved/results.json`；独立验证：`validation/verified/results.json`；对应旧版在各自`baseline/results.json`。
|
||
- 第四问：`output/q4/optimization-20260911/{baseline,improved}-{10,16}.json`。
|
||
- 中间开发试验也保留：同点补测、移动前瞻、路线终点、来向候选、路径计费及自适应发现。最终未采用均值变差的路线终点估计和未知频道自适应补扫。
|
||
- 回归测试：`pytest -q`，**166项全部通过**。新增用例验证串行6秒补测、不重复同地读数、频道状态成本、清除圆平移证书、无信号诊断及七站/49站的适用边界。
|
||
|
||
在项目根目录运行（label使用未存在的名称以保护已有证据）：
|
||
|
||
```powershell
|
||
.venv/Scripts/python.exe scripts/benchmark_q3_revision.py --label rerun-development
|
||
.venv/Scripts/python.exe scripts/benchmark_q3_revision.py --label rerun-validation --suite validation
|
||
.venv/Scripts/python.exe scripts/benchmark_q3_revision.py --label rerun-baseline --suite validation --baseline
|
||
.venv/Scripts/python.exe scripts/benchmark_q4.py --seeds 0,1 --sources 10 --directional 3 --out output/q4/rerun-10.json
|
||
.venv/Scripts/python.exe scripts/benchmark_q4.py --seeds 2,3 --sources 16 --directional 8 --out output/q4/rerun-16.json
|
||
```
|
||
|
||
概率限制：网格幸存集是保守可行集，不是已知官方概率模型的精确贝叶斯后验。
|
||
均匀源分布、接收半径分布、代表读数和哈希误差均属测试或启发式假设。
|
||
完备覆盖与清除证书依赖题面给出的确定性边界，性能数字则依赖具体测试分布。
|