249 lines
26 KiB
Markdown
249 lines
26 KiB
Markdown
# 问题二：具有接收保证的第二检测点选择
|
||
|
||
## 摘要
|
||
|
||
针对只获得一次全向干扰源示向度的情形，提出以接收保证为约束、以后验最小包围半径为主要指标的主动选点方法。首先将源位置圆域、首次角域与有效接收距离上界相交，构造包含真实源的位置候选集；随后把第二检测点的安全条件写成一族闭圆盘的交，并证明其非空性等价于候选集最小包围半径不超过最小有效接收半径。利用首次角域狭窄的题设特征，进一步推导截断角域的最小包围圆，得到半径约250米、能够直接计算的安全候选圆盘。为比较候选点的定位效果，建立兼顾 `direction` 和 `near` 的保守后验模型，推导交会角的局部几何意义，并给出采用外包多边形及观测区间划分的有限候选评估算法。严格接收保证与启发式性能优化分别陈述，不将有限采样结果解释为连续问题的全局最优解。
|
||
|
||
**关键词：** 主动测向；鲁棒选点；安全候选区域；最坏后验半径；保守几何近似。
|
||
|
||
## 1. 问题界定与思路来源
|
||
|
||
题目第二问给定某全向干扰源在一个检测点处的示向度，要求提出第二检测点的选择策略、说明其定位效果并给出候选区域。这里的源类型明确为全向，不能混入第四问的朝向可见性条件。[题面第1页问题2](C:/Users/HelixCopex/code/MATH/issue/B题.pdf)
|
||
|
||
本问有两个先后不同的问题：第二点是否仍能收到信号；在能收到信号的点中，如何使新测量更有价值。如果只追求较大交会角而不控制到真实源的距离，第二次测量可能返回 `no_signal`，预期几何收益无法实现。因此先构造保证接收的可行域，再优化测向后的不确定区域。
|
||
|
||
方法来源分为三部分。候选位置集合来自题设有界误差与接收距离，沿用问题一的角域约束；安全选点来自“对每个可能源位置都满足距离条件”的鲁棒可行性；定位收益来自主动测量设计，以最坏后验半径代替未经题面支持的平均误差。凸函数与鲁棒建模的一般背景参见 Boyd 与 Vandenberghe 的《Convex Optimization》第3章、第6.4节；本题的安全圆盘公式、扇形推导及区间评估方法在下文逐步建立。[文献3](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)
|
||
|
||
需要强调：本题没有给出源位置概率分布，也没有给出可直接使用的独立高斯测向噪声模型。因此不能把卡尔曼滤波、协方差或费舍尔信息计算直接作为严格保证。交会角仍有明确几何意义，但应作为局部解释和候选筛选依据。
|
||
|
||
## 2. 符号、题设事实与建模约定
|
||
|
||
| 符号 | 含义 |
|
||
| --- | --- |
|
||
| $s$、$\theta$ | 首次检测位置与示向度 |
|
||
| $\delta$ | 误差半角，默认 $1^\circ$ |
|
||
| $g$ | 未知的全向干扰源位置 |
|
||
| $\Omega=B(0,1800)$ | 干扰源位置圆域 |
|
||
| $R_g\in[R_-,R_+]$ | 未知有效接收半径，$R_-=1000$、$R_+=1500$ 米 |
|
||
| $K_1$ | 首次观测后的保守位置候选集 |
|
||
| $q$ | 第二检测点 |
|
||
| $\mathcal Q(K_1)$ | 对 $K_1$ 内所有位置均保证接收的第二点区域 |
|
||
| $\rho(K)$ | 非空有界集合 $K$ 的最小包围半径 |
|
||
| $J(q)$ | 第二点的最坏保守后验半径 |
|
||
|
||
采用以下题设事实：有效接收半径在1000至1500米之间；检测点到全向源距离不超过5米时无法得到示向度，可直接光学定位并清除；清除距离不超过20米；机器狗移动速度为5米/秒，检测需要5秒，同一频道连续测量不发生额外频道切换。[题面附录2第(2)、(4)至(9)项](C:/Users/HelixCopex/code/MATH/issue/B题.pdf)
|
||
|
||
1800米圆域限制的是源位置，不是机器狗的搜索位置。检测点可以位于该圆域外；接口坐标分量的绝对值上限属于数值防护限制，不能误解成要求 $q\in\Omega$。[题面第4页](C:/Users/HelixCopex/code/MATH/issue/B题.pdf)
|
||
|
||
如果把读数舍入额外计入误差预算，可显式采用 $\delta=1.005^\circ$。下文解析推导对 $0\le\delta\le45^\circ$ 成立，但这一扩展区间不是题目误差范围。
|
||
|
||
## 3. 首次观测对应的源位置集合
|
||
|
||
设 $u=u(\theta)=(\cos\theta,\sin\theta)$。由第一次有效示向度，真实位置属于前向角域 $W(s,\theta,\delta)$；由已经收到信号，必有 $\lVert g-s\rVert\le R_g\le R_+$；由源位置限制，又有 $g\in\Omega$。故定义 $K_1=\Omega\cap W(s,\theta,\delta)\cap B(s,R_+)$。
|
||
|
||
该集合为闭凸紧集。真实观测一致时 $g\in K_1$，所以它非空。首次返回 `direction` 还意味着 $\lVert g-s\rVert>5$，但若把这个开圆盘排除，会破坏凸性。本文暂不使用该排除信息，保留包含真源的凸外包集合；由此得到的保证可能更保守，不会误删真实位置。
|
||
|
||
这一区别决定了后续结论的口径：本文给出的保证对较大的 $K_1$ 中所有位置成立，因而对实际源成立；但在 $K_1$ 上定义的最坏后验指标可能比利用全部观测细节的精确模型更悲观。
|
||
|
||
若计算得到 $K_1=\varnothing$，说明输入、频道、误差界或数值处理与题设不一致。此时应返回不一致状态，不能继续给空集计算圆心。问题一的纯角域求解器也不能直接把上述圆弧边界当作直线边界处理。
|
||
|
||
## 4. 安全候选区域的精确定义及基本性质
|
||
|
||
### 4.1 接收距离条件
|
||
|
||
若第二检测点满足 $\lVert q-g\rVert\le R_-$，由于 $R_g\ge R_-$，即可保证全向源信号能够接收。因此定义 $F_K(q)=\max_{g\in K}\lVert q-g\rVert$，并令 $\mathcal Q(K)=\{q:F_K(q)\le R_-\}=\bigcap_{g\in K}B(g,R_-)$。
|
||
|
||
这里限制的是第二点到所有可能源位置的距离，而不是到第一次检测点的距离。保证接收也不等于保证返回示向度，因为距离不超过5米时可能返回 `near`；该分支的定位效果更好，不能视为策略失败。
|
||
|
||
### 4.2 凸性、稳定性和非空条件
|
||
|
||
**命题1：** 对任意非空紧集 $K$，函数 $F_K$ 为凸函数，且满足 $\lvert F_K(q_1)-F_K(q_2)\rvert\le\lVert q_1-q_2\rVert$。
|
||
|
||
**证明：** 对每个固定的 $g$，距离函数关于 $q$ 凸；逐点取最大值保持凸性。又由三角不等式，$\lVert q_1-g\rVert\le\lVert q_2-g\rVert+\lVert q_1-q_2\rVert$，对 $g$ 取最大值得到一个方向的不等式，再交换两点即得结论。证毕。
|
||
|
||
因此 $\mathcal Q(K)$ 是闭凸集。非空时，它包含在任一 $B(g_0,R_-)$ 内，所以也有界。
|
||
|
||
**定理1：** $\mathcal Q(K)\ne\varnothing$ 当且仅当 $\rho(K)\le R_-$。
|
||
|
||
**证明：** 最小包围半径的定义为 $\rho(K)=\min_q F_K(q)$。存在 $q$ 使 $F_K(q)\le R_-$，与其最小值不超过 $R_-$ 完全等价。最小值存在，因为 $F_K$ 连续且随 $\lVert q\rVert\to\infty$ 趋于无穷。证毕。
|
||
|
||
当 $\rho(K)=R_-$ 时，安全区域仅包含唯一最小包围圆中心；唯一性可由两个候选中心的中点距离恒等式证明，见[问题一第8节](C:/Users/HelixCopex/code/MATH/docs/algo-1.md)。因此应使用不严格不等式，不能把等号情形误判为空。
|
||
|
||
### 4.3 外包圆给出的充分区域
|
||
|
||
若已知 $K\subseteq B(c,r)$ 且 $r\le R_-$，则任意满足 $\lVert q-c\rVert\le R_--r$ 的点，都有 $\lVert q-g\rVert\le\lVert q-c\rVert+\lVert c-g\rVert\le R_-$。因此 $B(c,R_--r)\subseteq\mathcal Q(K)$。
|
||
|
||
这给出了容易计算的充分候选区域，但一般不等于整个安全区域。一个宽松外包圆若满足 $r>R_-$，只能说明该外包圆不能提供证书，不能证明真实的 $\mathcal Q(K)$ 为空。
|
||
|
||
## 5. 首次截断角域的解析最小包围圆
|
||
|
||
### 5.1 坐标变换
|
||
|
||
暂时去掉只会缩小集合的 $\Omega$ 约束，考虑完整截断角域 $S=W(s,\theta,\delta)\cap B(s,R_+)$。平移并旋转，使 $s$ 成为原点、$u$ 成为横轴。其点可写成 $g=s+t\,u(\theta+\varphi)$，其中 $0\le t\le R_+$、$-\delta\le\varphi\le\delta$。
|
||
|
||
令 $a=R_+/(2\cos\delta)$，并取 $c=s+au$。
|
||
|
||
### 5.2 包含性证明
|
||
|
||
**定理2：** 对 $0\le\delta\le45^\circ$，截断角域 $S$ 的最小包围圆为 $B(c,a)$。
|
||
|
||
**证明的第一部分：** 对任意 $g\in S$，有 $\lVert g-c\rVert^2=t^2+a^2-2at\cos\varphi$。固定 $\varphi$ 时，右侧关于 $t$ 为凸二次函数，区间最大值在端点取得。当 $t=0$ 时等于 $a^2$；当 $t=R_+$ 时，由 $\cos\varphi\ge\cos\delta$ 得其不超过 $R_+^2+a^2-2aR_+\cos\delta=a^2$。故整个 $S$ 被该圆覆盖。
|
||
|
||
### 5.3 最小性证明
|
||
|
||
取角域中的三个点 $p_0=s$、$p_+=s+R_+u(\theta+\delta)$、$p_-=s+R_+u(\theta-\delta)$。它们均在 $B(c,a)$ 的圆周上。
|
||
|
||
令 $\lambda_+=\lambda_-=1/(4\cos^2\delta)$，$\lambda_0=1-1/(2\cos^2\delta)$。由于 $\delta\le45^\circ$，三权重非负且和为1，直接代入可得 $c=\lambda_0p_0+\lambda_+p_++\lambda_-p_-$。
|
||
|
||
对任意中心 $z$，利用加权距离恒等式，有 $\sum_j\lambda_j\lVert p_j-z\rVert^2=a^2+\lVert c-z\rVert^2\ge a^2$。若半径为 $r$ 的圆覆盖这三个点，则左侧不超过 $r^2$，故 $r\ge a$。任何覆盖 $S$ 的圆都必须覆盖这三个点，结合第一部分的包含性，得到最小半径恰为 $a$。当 $\delta=0$ 时两个远端点重合，结论退化为长度 $R_+$ 的线段直径圆，仍成立。证毕。
|
||
|
||
该推导不依赖源位置先验，也不依赖位置概率分布。它给出的是完整截断角域的精确最小圆；与 $\Omega$ 相交后，真实 $K_1$ 的最小圆可能更小。
|
||
|
||
## 6. 本题可直接采用的第二点候选区域
|
||
|
||
由 $K_1\subseteq S\subseteq B(c,a)$ 和第4.3节，可取 $\mathcal Q_0=B(c,b)$，其中 $c=s+au$、$a=1500/(2\cos\delta)$、$b=1000-a$。
|
||
|
||
| 误差半角 | 轴向中心距离 $a$ / 米 | 安全候选半径 $b$ / 米 |
|
||
| --- | ---: | ---: |
|
||
| $1^\circ$ | 750.114246 | 249.885754 |
|
||
| $1.005^\circ$ | 750.115391 | 249.884609 |
|
||
|
||
两种口径下 $b>0$，故本题首次有效测向后的安全候选区域可以直接证明非空。无需将“若安全区域为空就去最小圆圆心”作为正常流程的保底步骤。
|
||
|
||
几何上，$\mathcal Q_0$ 位于首测示向方向前方约750米，以约250米为半径。位于圆盘轴向前后端的点、两侧横向点以及圆心都保证接收。横向点只是可供比较的候选点，并未被证明总是最优。
|
||
|
||
为抵消坐标计算和动作提交中的工程舍入，可取缩小区域 $\mathcal Q_\eta=B(c,b-\eta)$，其中 $0<\eta<b$。若圆心和提交位置合计偏差不超过 $\eta$，三角不等式保证仍有 $\lVert q-g\rVert\le1000$。例如先取 $\eta=0.01$ 米属于可调工程选择，不是题面要求，也不是未分析数值误差的自动上界。
|
||
|
||
若有更精细的 $K_1$ 外包圆，可得到更大的充分区域；若精确处理其圆弧边界，也可直接搜索 $\mathcal Q(K_1)$。这些扩展是性能优化，不影响 $\mathcal Q_0$ 的正确性。
|
||
|
||
## 7. “较好的定位效果”的数学定义
|
||
|
||
### 7.1 保守后验集合
|
||
|
||
对候选点 $q\in\mathcal Q_0$，若返回 `direction` 及示向度 $\beta$，定义保守后验 $K_d(q,\beta)=K_1\cap W(q,\beta,\delta)$。这里继续忽略距离大于5米所提供的非凸排除信息。真实源一定属于 $K_d$。
|
||
|
||
若返回 `near`，定义 $K_n(q)=K_1\cap B(q,5)$，故 $\rho(K_n(q))\le5$。在此分支直接以当前位置进行光学定位和清除，满足20米的清除条件，不必强行再取得一个角度。
|
||
|
||
设圆周角距离为 $d_{\mathbb S^1}(\alpha,\beta)=\min_{k\in\mathbb Z}\lvert\alpha-\beta+360^\circ k\rvert$。对 $\lVert g-q\rVert>5$ 的候选位置，令真实方位为 $h_q(g)=\operatorname{atan2}(g_y-q_y,g_x-q_x)$。可能出现的读数集合定义为 $\mathcal B(q)=\{\beta:\exists g\in K_1,\ \lVert g-q\rVert>5,\ d_{\mathbb S^1}(\beta,h_q(g))\le\delta\}$。
|
||
|
||
这里用所有允许误差描述可能读数，不是假设各地点的误差可以随机独立重抽样。同一个位置的重复检测不产生新的独立信息；所构造的 $\mathcal Q_0$ 与首测位置相距至少约500米，天然避免原地重复测量。
|
||
|
||
### 7.2 最坏后验半径指标
|
||
|
||
定义 $J(q)$ 为所有可能 `direction` 分支的 $\rho(K_d(q,\beta))$，以及非空 `near` 分支的 $\rho(K_n(q))$ 的上确界。等价地，它是未来所有允许观测下最坏的保守最小包围半径；不存在的观测分支不参与取最大值。
|
||
|
||
选点的主要目标为在安全候选区域中降低 $J(q)$。该指标直接服务于一次清除要求：若 $J(q)\le20$，则每个可能分支都有半径不超过20米的保守定位圆。它比仅比较面积更符合任务，因为面积较小的集合仍可能十分狭长。
|
||
|
||
对于任意有效分支，后验都是 $K_1$ 的子集。集合包含关系给出 $\rho(K_2)\le\rho(K_1)$，故 $J(q)\le\rho(K_1)$。但不一定严格小于，因此不能仅由“增加一次观测”推断定位精度必然严格改善，更不能保证只需两次测向便达到20米阈值。
|
||
|
||
### 7.3 移动成本的引入
|
||
|
||
连续测量同一频道时，本次动作的虚拟时间增量为 $C(q)=\lVert q-s\rVert/5+5$ 秒。推荐先按后验半径择优，再在几何效果接近的候选点中比较移动成本，以避免任意混合米和秒。
|
||
|
||
用 $\widehat J(q)$ 表示实际计算的评估量，在第10节的保守方案中取为上界 $\overline J(q)$。设有限候选点中的最小评估值为 $J_{\min}$。可先保留满足 $\widehat J(q)\le J_{\min}+\tau$ 的点，再选择其中 $C(q)$ 最小者，其中 $\tau\ge0$ 是显式给定的定位容忍量，单位为米；$\tau=0$ 对应严格的字典序选择。本文不预设一个未经实验支持的最优 $\tau$。
|
||
|
||
## 8. 交会角的局部几何解释
|
||
|
||
在某个假定真实位置 $g$ 附近，令两站距离为 $r_1,r_2$，真实视线单位向量为 $u_1,u_2$，对应法向量为 $n_1,n_2$。当角误差很小且位置扰动相对站距较小时，方位函数的一阶展开给出 $n_i\cdot\Delta g\approx r_i e_i$，其中 $e_i$ 用弧度表示，满足 $\lvert e_i\rvert\le\delta_{\rm rad}$。
|
||
|
||
于是局部不确定区域近似由两条带状约束限定：$\lvert n_1\cdot\Delta g\rvert\le r_1\delta_{\rm rad}$、$\lvert n_2\cdot\Delta g\rvert\le r_2\delta_{\rm rad}$。若视线交会角为 $\phi$，法向量矩阵的行列式绝对值为 $\lvert\sin\phi\rvert$。对法向坐标中的矩形作线性逆变换，得到近似面积 $A_{\rm loc}\approx4r_1r_2\delta_{\rm rad}^2/\lvert\sin\phi\rvert$。
|
||
|
||
这解释了两点：近于平行或反向的视线使误差显著放大；在距离不变的局部比较下，接近直角的交会较有利。然而真实源位置未知，$r_2$ 和 $\phi$ 随 $g$ 改变，且有限角域并非无限带状区域。因此不能由该近似推出“总应横移固定距离”或“在某个假定源位置形成90度就是全局最优”。本文只将其用于优先考虑轴线两侧候选点，最终仍以后验集合指标评价。
|
||
|
||
## 9. 圆弧先验的保守离散
|
||
|
||
### 9.1 外包切线多边形
|
||
|
||
直接将圆周采样点连接得到的是内接多边形，会错误排除圆盘边缘的真实位置。为了复用第一问的半平面工具，选择 $M\ge3$ 个均匀法向量 $v_j=u(2\pi j/M)$，定义 $P_M(o,R)=\{x:v_j\cdot(x-o)\le R,\ j=0,\ldots,M-1\}$。
|
||
|
||
由柯西不等式，任意 $x\in B(o,R)$ 都满足所有约束，因此 $B(o,R)\subseteq P_M(o,R)$。相邻切线交点到圆心的距离为 $R\sec(\pi/M)$，故单个圆盘外包的最大径向超出不超过 $R[\sec(\pi/M)-1]$。
|
||
|
||
令 $\widetilde K_1=P_M(0,1800)\cap W(s,\theta,\delta)\cap P_M(s,1500)$，便有 $K_1\subseteq\widetilde K_1$。对任何第二读数再求半平面交，仍然保留真实源。上述单圆径向误差不能未经论证直接当成最终定位半径的误差界；靠近切触或退化时尤其需要加密检查。
|
||
|
||
安全选点仍使用第6节的解析 $\mathcal Q_\eta$。即使粗糙外包多边形的最小圆偏大，也不能据此推翻解析安全区域的非空结论。
|
||
|
||
### 9.2 多边形安全区域的可选扩展
|
||
|
||
若采用任意有界凸外包多边形 $\widetilde K=\operatorname{conv}\{v_j\}$，则 $\max_{g\in\widetilde K}\lVert q-g\rVert=\max_j\lVert q-v_j\rVert$，证明与第一问的凸组合论证相同。因此其保证接收区域由有限个约束 $\lVert q-v_j\rVert\le1000$ 给出，是圆盘交。
|
||
|
||
也可先解最小包围圆问题，再构造充分安全圆盘。由于 $\widetilde K$ 是外包集合，得到的区域可能更小，但其中每个点仍安全。若该离散区域为空，优先加密或回到解析候选盘，不把离散失败误报为真实问题无解。
|
||
|
||
## 10. 未来读数的保守区间评估
|
||
|
||
直接枚举少量假定源位置和误差端点，只得到被枚举情形的最大值，可能漏掉真正最坏读数。为了使评估输出具有上界意义，可以划分全部可能方位角，而非仅点采样。
|
||
|
||
将整周按圆周意义划分为若干区间 $I_j$，中心为 $\beta_j$，宽度为 $h_j$，要求 $\delta+h_j/2<90^\circ$。跨越 $0^\circ$ 的区间按圆周距离处理。
|
||
|
||
**命题2：** 对任意 $\beta\in I_j$，有 $W(q,\beta,\delta)\subseteq W(q,\beta_j,\delta+h_j/2)$。
|
||
|
||
**证明：** 对左侧任意非顶点位置，其方向到 $\beta$ 的圆周距离不超过 $\delta$；而 $\beta$ 到区间中心的距离不超过 $h_j/2$。由圆周距离的三角不等式，其方向到中心的距离不超过两者之和。顶点在两个闭角域中均被保留。证毕。
|
||
|
||
因此定义 $U_j(q)=\widetilde K_1\cap W(q,\beta_j,\delta+h_j/2)$，则任何落在该区间的真实读数所对应的保守后验，都包含于 $U_j(q)$，从而 $\rho(K_d(q,\beta))\le\rho(U_j(q))$。
|
||
|
||
对于 `near` 分支，可以取统一上界 $\min\{5,\rho(\widetilde K_1)\}$。该上界不需要精确计算圆弧交集；即使某点实际不会触发 `near`，纳入此上界只增加保守性。
|
||
|
||
令 $\overline J(q)$ 等于所有非空 $U_j(q)$ 的最小包围半径，以及上述 `near` 上界的最大值，即得到 $J(q)\le\overline J(q)$。该结论在精确几何计算下成立。浮点实现还需给出包含性和数值误差处理，不能把无误差预算的计算值称为机器可验证的严格上界。
|
||
|
||
通过将某个角区间二分，子区间扩张后的角域包含于父区间的扩张角域，所以相应方向上界不会增大。通过保留旧切线并增加新切线，也可使外包多边形嵌套缩小。这给出稳定的自适应加密方向，但没有在本文中证明连续选点的统一收敛速率。
|
||
|
||
该评估可能较慢，实际可先用少量读数采样粗筛，再对入围点使用完整角区间上界。前一阶段仅决定计算资源分配；最后报告的保守上界必须来自完整覆盖的区间，不能来自粗筛样本最大值。
|
||
|
||
## 11. 可执行的第二点选择算法
|
||
|
||
**算法2：安全区域内的有限候选主动测向。**
|
||
|
||
1. 输入 $s,\theta,\delta$，核验首次观测为同一全向源的有效示向度，构造 $K_1$ 或其保守表示。
|
||
2. 计算 $a=1500/(2\cos\delta)$、$c=s+au(\theta)$、$b=1000-a$，选择满足误差预算的缩小半径 $b-\eta$。
|
||
3. 构造有限候选集：包含圆心 $c$，并取 $q_{\ell j}=c+r_\ell[\cos\psi_j\,u+\sin\psi_j\,u_\perp]$，其中 $0<r_\ell\le b-\eta$、$\psi_j=2\pi j/N_\psi$、$u_\perp=(-\sin\theta,\cos\theta)$。所有候选点自动满足接收距离保证。
|
||
4. 对每个候选点构造第9节的外包后验，按第10节评估 $\overline J(q)$，保存最坏角区间及对应包围圆作为评估依据。
|
||
5. 优先选择 $\overline J$ 较小的点；按预先声明的 $\tau$ 筛选近优点，再按移动检测代价选择，必要时用固定顺序消除完全同分。
|
||
6. 在现实计算预算内，对入围候选附近加密位置、细分最坏角区间并增加外包切线。保留当前已验证安全的可用点，预算耗尽时返回当前结果。
|
||
7. 在所选位置测量同一频道。若为 `near`，在当前位置清除；若为 `direction`，用实际读数更新候选集合并复算最小包围圆；若其半径仍大于20米，继续后续测向，不能宣称两次定位已经完成。
|
||
8. 若在距离保证条件下意外得到 `no_signal`，核查动作是否被接受、频道是否正确、源是否仍存在及坐标和模型是否一致。未知原因解决前不按正常 `direction` 分支更新位置候选。
|
||
|
||
例如可从3层半径、每层16个方向及1个圆心开始，共49个候选点；这是位置搜索的数值分辨率示例，与第三问49点全域覆盖网格无关，也不是已优化参数。外包切线数、角区间宽度、加密次数及 $\tau$ 均应在论文实验部分显式记录。
|
||
|
||
设候选数为 $N_q$、角区间数为 $N_\beta$、每个后验的半平面数为 $k$。复用第一问的边界枚举时，主计算量约为 $O(N_qN_\beta k^3)$，另加顶点直径或最小圆计算。该方法提供清楚的正确性结构，但需通过缓存首次约束、局部加密和计算预算控制实现成本。不能用“只需一次新的测量”忽略选点器自身的运行时间。
|
||
|
||
算法输出保证的是：所选点位于已证明安全的区域，并在给定有限候选及评估精度下按既定规则择优。本文未证明 $q\mapsto J(q)$ 是凸函数，也未证明有限候选的最优点就是整个 $\mathcal Q(K_1)$ 中的全局最优点。
|
||
|
||
## 12. 边界情形与适用范围
|
||
|
||
| 情形 | 正确处理 |
|
||
| --- | --- |
|
||
| $K_1$ 为空 | 报告模型或数据不一致，不构造虚假圆心 |
|
||
| 首次结果已经为 `near` | 直接清除，不再套用“已知示向度”的第二问流程 |
|
||
| 一般集合满足 $\rho(K)=1000$ | 安全区域为最小包围圆中心这个单点 |
|
||
| 一般集合满足 $\rho(K)>1000$ | 不存在对该集合全部位置保证接收的点；圆心仅是最小化最坏距离的探索选择 |
|
||
| 外包圆半径大于1000 | 只能判定该证书不足，不能直接判真实安全区域为空 |
|
||
| 测量轴接近 $0^\circ/360^\circ$ | 使用向量约束和圆周区间，避免角度断点错误 |
|
||
| 两次测向交会较差 | 保留完整后验并继续测量，不将小面积当成小直径 |
|
||
| 源类型为定向 | 距离证书仍成立，但接收还受朝向限制，不能直接沿用本问的接收保证 |
|
||
|
||
对于一般集合无安全点的情形，最小包围圆中心确实解 $\min_q\max_{g\in K}\lVert q-g\rVert$，但其最坏距离仍可能大于1000米。改善交会角若要求偏离该中心，还会牺牲最坏距离最优性，必须明确是另一个多目标探索策略，不能把两项互相冲突的要求同时称为已保证。
|
||
|
||
## 13. 验证设计及当前实现边界
|
||
|
||
本问的验证分为数学证书与策略性能两层。数学层检查：截断角域被解析圆覆盖；安全候选到所有允许位置的距离不超过1000米；外包离散不删除真实点；角区间扩张包含所有区间内读数。数值抽样只能辅助检查这些证明，不能取代它们。
|
||
|
||
性能层应在相同自建源位置与确定的空间误差场上，比较轴向点、两个横向点、有限候选最坏后验策略。误差场在同一位置保持固定；不得让每次调用重新独立生成误差。记录第二次测量类型、后验直径和包围半径、额外移动、计算耗时及是否达到20米清除阈值。至少包含误差边界、源域边界、接收半径1000米、近距离和近共线案例。没有这些实验前，不报告未经验证的性能提升比例。
|
||
|
||
目前 [planning.py](C:/Users/HelixCopex/code/MATH/geometry/planning.py) 中的 `first_bearing_candidate_disk` 已实现第5至6节的解析证书；问题一内核可用于纯半平面区域的顶点和最小圆计算。**本仓库第二问交付的定位是"安全选点的启发式基线"**：解析安全候选盘证书已实现并证明（选中点必能收到信号），而选点评分采用边界采样点 × 读数区间端点的有限枚举近似（含 near 分支）。第9至11节描述的完整选点器数学方案，特别是第10节覆盖全部未来读数的保守区间上界，尚未在现有仓库中实现；采样最大值只用于候选点之间的相对比较与粗筛，不得当作严格最坏情形上界报告，也没有相应正式成绩。该实现边界不影响解析候选区域的证明。
|
||
|
||
对后续实现而言，应新增接收任意半平面约束的交集入口，或使用独立的多边形裁剪函数，再复用第一问的最小包围圆。不能把圆盘先验伪装成额外测向观测传入现有 `solve(measurements)` 接口。
|
||
|
||
## 14. 结论
|
||
|
||
第二问的候选区域可以明确取为前方约750米处、半径约250米的圆盘，其解析式为 $\mathcal Q_0=B(s+au(\theta),1000-a)$，其中 $a=1500/(2\cos\delta)$。这一候选区域对题设全向源提供接收保证，且在首次有效测向条件下严格非空。
|
||
|
||
在该区域内，以最坏保守后验最小包围半径为主指标、移动代价为次指标，采用有限候选和逐步加密进行选择。交会角解释局部几何优劣，外包多边形和读数区间扩张保证不低估相关后验集合；全局最优和“两次即可清除”均不作为未经证明的结论。
|
||
|
||
## 参考文献
|
||
|
||
1. 全国大学生数学建模竞赛组委会. 2026年高教社杯全国大学生数学建模竞赛B题：无线电干扰源的快速自动定位与清除[Z]. 2026. [本地题面](C:/Users/HelixCopex/code/MATH/issue/B题.pdf)，问题2、附录2及第4页坐标约束。
|
||
2. 模拟器配套材料. 附件2：模拟器通信接口说明及编程指南[Z]. 2026. [本地附件](C:/Users/HelixCopex/code/MATH/issue/附件/附件2.docx)。用于 `direction`、`near`、`no_signal` 等程序观测字段与动作接口的对应。
|
||
3. BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2004. [作者公开版本](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)，第3章、第6.4节。用于凸性及鲁棒建模的一般背景，不作为本题候选圆盘公式的出处。
|
||
4. 本项目. 问题一：有界测向误差下定位区域的直径与圆覆盖[Z]. 2026. [algo-1.md](C:/Users/HelixCopex/code/MATH/docs/algo-1.md)。用于角域半平面表示、顶点判定和最小包围圆的衔接。
|
||
|
||
**来源说明：** 第5节的截断角域最小圆及第6节的安全圆盘，是结合题设参数在本文中推导的结果；第8节的交会角关系由方位函数一阶展开推得；第9至11节是据集合包含关系构造的保守计算方案。以上陈述说明本项目的推导路径，不宣称这些一般几何思想在既有文献中首次出现。
|