40岁数学难题被他用"词对分解"一招终结，Ross猜想的最后一块拼图

龙哥导读

如果有一个目标在碰运气式的“两房间”里来回躲藏，搜索者每次只能查一个房间，而且即使查对了房间也可能看走眼——这种情况下，搜索策略的最终形态到底是怎样的？这个问题听起来像抓猫，其实是运筹学与随机控制领域里一个流传了四十多年的经典难题：Ross猜想。本文用一个极其漂亮的“词对分解+射影几何”组合，把最后一块未证的拼图补上了。

引言：Ross猜想与两站点移动目标搜索问题

先来给没接触过这个问题的读者建立一个直观画面。假设有一个目标（海盗、潜艇、逃犯，随你代入）在两个站点之间随机游走，每时每刻只能待在一个站。搜索者每个时刻选择一个站点进行搜索，付出的代价是固定的搜索成本；如果目标确实在搜索的站点，也有可能因为隐蔽得好而“漏检”。目标一旦未被发现，就按一个已知的马尔可夫链继续转移。整个过程反复进行，直到检测到目标为止。

这类问题在随机搜索理论（search theory）里有着悠久的历史。目标移动中的搜索问题最早可以追溯到20世纪中后期，相关综述可见经典文献[2,5,15]。而在1977年前后，Sheldon M. Ross在其著作中提出了一个看起来非常“单纯”的猜想：

只要每个站点的“漏检概率”都严格小于1，那么最优策略一定是关于后验概率的阈值策略：当目标在站点1的后验概率较低时搜索站点2，较高时搜索站点1，中间存在唯一的阈值。

听起来像是随机控制里一句话就能证明的结论？实际上深不见底。原因在于，这个问题的状态虽然是一维后验概率，但后验更新由两个线性分式映射复合而成，而无限时域的值函数是无穷多个仿射函数取下确界的结果，本质上是一个可能含有无穷多个线性片段的凹函数。想直接验证两个Bellman分支函数的单调性，却会绕回对未知值函数的依赖。这就是Ross猜想长期以来难以攻克的根本原因。

在本文之前，学界对Ross猜想已有一些重要进展。White [20]最早给出了部分证明以及结构化的分析框架；MacPhee和Jordan [13]则建立了当时最全面的离散时间双站点模型分析，在0 0时覆盖了一部分转移律。但正行列式区域仍有大片“无人区”。之后Jordan的博士论文[9]继续了同一套分类分析。Flesch等人在其著作[7]中也明确写到该离散时间猜想在当时仍未被完全证明。

现在，Yunpeng Li这篇论文给出了Ross猜想在det M > 0区域的完整证明。结合MacPhee–Jordan的结果，Ross猜想对所有两站点转移矩阵在α_i < 1时都成立，并且本文还处理了α_i = 1的端点情形。这是一项彻底解决经典猜想的工作。

核心创新：词对分解与公共射影分隔子定理

这篇论文在证明思路上做了一个非常大胆的转向：不去和值函数的线性片段“死磕”，而是把目光转回到有限搜索词上。所谓搜索词，就是把每一步搜索的站点按顺序记录下来形成的字符串。比如“1212”表示依次搜索站点1、2、1、2。在检测成功之前，失败是唯一的非终止观测，因此任何确定性策略在幸存历史（surviving history）上诱导出的搜索词是唯一的。反过来，任何有限词都对应一个开环搜索策略。

关键一步在于“未归一化幸存者坐标”（unnormalised survivor coordinates）。正常情况下，每次搜索失败后都要更新后验概率，这个更新是非线性的。但如果把“仍然未被发现的概率质量”作为向量来传播，就能把转移和漏检整合成一个线性矩阵乘积。对任意搜索词w，在给定初始后验p时，其期望成本J_w(p)可以表示为一个仿射函数（Lemma 3.1）。这个技巧的好处是：比较两个词的成本差，只需比较两个仿射函数，而不需要处理值函数的复杂几何。

图1：词成本公式。这里 ρ(p)=(p,1-p) 是初始分布作为行向量，R_w 是与搜索词 w 对应的累积成本算子，c 是搜索成本向量。

接下来的创新点是定义一个结构十分有趣的词对类别：高度为一词对。对于两个等长词 H、L，逐位比较前缀中“1”的个数之差。如果这个差值始终只落在0或1上，就称它们构成高度为一词对（height-one pair）。等价地，把累计差值画成一条高度路径，它就被限制在一个“两层阶梯”上。

这种词对有什么好处？Lemma 4.4的全新结论是：任意高度为一词对都可以通过一串“相邻冒泡移动”互相转换，即把相邻的“21”替换成“12”；如果总前缀差累计为1，则最后还需要一次将“2”替换成“1”的操作。更重要的是，这些操作的位置具有嵌套结构——所有操作的左前缀构成一条前缀链（prefix chain）。也就是说，操作一个套一个，而不是杂乱分布。

为什么要费这么大力气做词分解？因为要从“局部”推出“全局”的符号性质。每次冒泡移动对应的成本差都是某个具体的矩阵K和某个由前缀决定的矩阵的乘积。如果前缀矩阵A_u的射影区间（projective interval）里能找到一个分隔子（separator），也就是一个行向量ξ_t=(1,-t)，使得乘上成本差矩阵后各分量非正，那就等于证明了这一局部移动不会产生反向穿越。

图2：冒泡移动的成本差分解公式。左侧是交换相邻搜索次序（先搜索1再搜索2 vs. 先搜索2再搜索1）的成本差；右侧表明它可以分解为前缀矩阵 A_u、固定符号矩阵 K 与剩余部分 (I+ΓR_v) 的乘积。

关键的“公共射影分隔子”定理（Theorem 4.x）说的是：由于所有局部操作的左前缀是嵌套的，射影区间也随之嵌套收缩（Lemma 4.6：前缀越长，对应的射影区间越小）。所以只要取最深前缀对应的那个射影区间中的任意一点作为斜率t，就能同时成为所有局部操作的合法分隔子。这一个公共分隔子，足以排除两个仿射成本函数在任意初始信念下出现“向上交叉”的可能。

关键证明：高度为一词对与对数几率压缩

有了词对分解和公共分隔子这两个代数工具，还差一个关键环节：为什么动态规划里自然出现的词对恰好就是高度为一词对？答案藏在“对数几率压缩”中。

在经典的Ross模型中，目标在每次搜索失败后按转移矩阵M(=[[a,1-a],[1-b,b]])运动，其中a和b分别是目标留在站点1和站点2的概率。用Δ=det M=a+b-1来刻画两站之间的相关性。当Δ>0时，目标倾向于留在原站（正相关/持久性regime），这是MacPhee–Jordan当年没有完全解决的区域。

图3：两站点转移矩阵。a 为目标留在站点1的概率，b 为目标留在站点2的概率；对角线元素越大，目标越倾向于“恋旧”。

图4：转移矩阵行列式的定义。Δ>0 对应正相关情形，这正是本文主攻的“难点区域”。

现在来看对数几率视角。记η=log(p/(1-p))为当前后验信念的对数几率。搜索站点1失败后（漏检概率α₁），对数几率的变化为η→η-ℓ₁，其中ℓ₁=-log α₁ > 0；搜索站点2失败后，则是η→η+ℓ₂，其中ℓ₂=-log α₂ > 0。而目标移动造成的对数几率更新为一个压缩映射Φ(η)，其导数满足0<Φ'(η)<1。这一压缩性质正是“正行列式区域”下的关键动力学行为。

图5：目标移动在对数几率坐标下的更新公式。在 Δ>0 时该映射是严格递增的压缩（导数严格介于0与1之间），压缩性在后续证明中起到决定性作用。

图6：压缩性条件。Φ'(η) 恒大于0且恒小于1，这保证对数几率差在经过运动更新后会被压缩而不是放大。

压缩性意味着，两个从同一初始信念出发但先采取不同第一动作的轨迹，只要之后使用相同的单调续行策略，它们的“动作计数差异”在整个幸存历史上会被钳制在0和1之间。也就是说，动态规划归纳中出现的Bellman分支词对必然是高度为一词对。这一步就把动态规划与词序理论完美地衔接起来。

至此，证明的骨架已经清晰：有限时域值函数的两个Bellman分支各自对应一个有限词；两个分支对应的词对是高度为一的；通过链式分解与公共射影分隔子，这两个词的仿射成本函数满足单侧穿越性质；进而可以推出阈值最优选择。再通过一个一致截断不等式（uniform O(1/n) truncation bound）将有限时域结论传递到无限时域。

具体来说，就是构造一个参考策略，它的期望成本被某个常数V_ref一致上界，使得无限时域值函数和有限时域值函数的差能被O(1/n)控制。这个截断界是均匀成立的，而且与转移概率的具体取值无关，体现了方法的稳健性。

图7：有限时域与无限时域值函数的均匀截断误差界。这说明用足够长的有限时域近似无限时域时，误差随 n 以 1/n 的速度一致收敛到零。

边界情况处理与完整证明

前文已经说明，严格内部情形（00）的阈值最优性已经证明。剩下的是各种边界情况：a或b等于0或1，α_i等于0或1，以及行列式Δ=0或Δ<0的退化情形。

当α_i=1时，搜索该站点可能永远无法发现目标，此时期望总成本可能对某些初始信念取到无穷大。为此，论文采用了扩展实值期望成本准则（extended-real expected-cost criterion），并在Section 7中对所有参数做了完整分类，厘清了哪些参数向量对所有信念都有有限值、哪些则否。在Δ≤0的区域，MacPhee–Jordan的结论已经覆盖；在严格内部区域与边界区域之间，用连续性进行衔接。这样，三块拼图拼在一起，Ross猜想对全部2×2随机转移矩阵、所有α∈[0,1]、所有正搜索成本都得到了完整证明。

值得注意的是，论文的值函数是用最小化期望总成本直到检测为止来定义的，使用的准则本质上是无折扣的（undiscounted）。对于α_i<1的经典情形，搜索总会以概率1结束，因此值是有限的；对α_i=1的情形，若目标处于某个站点并且该站点永远不会被发现，则检测时间可能是无穷大，此时扩展实值准则自然给出+∞。

方法推广与未来研究方向

这篇论文的方法论价值很值得玩味。它没有采用现代强化学习中常见的策略梯度或Q学习等数值方法，而是用经典的动态规划结构加上组合数学与射影几何，把最优策略的结构性质完整刻画了出来。这在当下“数据驱动”盛行的环境中显得格外清爽。

在实际应用层面，两站点移动目标搜索模型可以映射到很多现实场景。例如，在计算机网络安全中，当一个攻击者以某种模式在多个服务器之间跳跃时，防御者需要在有限资源下决定检查哪个服务器；又如在海上搜救中，一个漂流目标的位置转移可以用两区域马尔可夫链近似。只要状态空间足够小而参数又基本稳定，这篇论文的阈值结构就能帮助决策者设计出可解释性极强的搜索策略。

然而也要承认，本文是纯理论证明论文，没有数值实验，也不涉及算法实现。对于工程师而言，最关心的“阈值是多少”并没有给出闭式表达式。从参数到最优阈值的映射，需要通过求解Bellman方程或近似动态规划来获得。本文提供的价值在于：保证了这个阈值存在、单调、并且可以用一个确定性平稳阈值选择器达到最优。有了这个结构性保证，后续工程上就不需要担心策略出现非单调的“抖动”了。

未来值得探索的方向包括：把高度一词对和公共射影分隔子的方法推广到三个及以上站点；在部分可观测马尔可夫决策过程（POMDP）的一般框架下，寻找更广的阈值最优性条件；以及研究当状态转移矩阵不是严格正定时的替代工具。在通用人工智能和强化学习都极其依赖“可解释策略结构”的今天，这种从历史经典问题中提炼结构性结论的工作，反而显得越来越有参考价值。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

这篇论文到底在解决什么问题？两站点移动目标搜索的Ross猜想被完整证明：本文提出未归一化幸存者坐标与搜索词对框架，补齐正行列式区域缺口，覆盖所有转移矩阵及α=1端点情形，确认阈值策略最优。悬置多年的理论问题就此闭环。

这篇工作最值得看的点是什么？通过引入未归一化幸存者动力学与搜索词条的矩阵表示，结合高度为一的词对链分解与公共射影分隔子定理，证明两站点移动目标搜索问题的最优策略具有阈值结构。

这篇工作的边界或风险在哪里？优点：理论证明严谨，结构清晰，将复杂POMDP问题转化为组合词对与射影几何问题，方法新颖且具有推广潜力。缺点：纯理论论文，缺乏实验验证，对非专业读者门槛较高。

如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★☆

通过引入未归一化幸存者动力学与搜索词条的矩阵表示，结合高度为一的词对链分解与公共射影分隔子定理，证明两站点移动目标搜索问题的最优策略具有阈值结构。

实验合理度：★★★☆☆

现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。

学术研究价值：★★★★☆

通过引入未归一化幸存者动力学与搜索词条的矩阵表示，结合高度为一的词对链分解与公共射影分隔子定理，证明两站点移动目标搜索问题的最优策略具有阈值结构；更关键的是问题定义是否可复用到同类任务。

稳定性：★★★☆☆

现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。

适应性以及泛化能力：★★★☆☆

现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。

硬件需求及成本：★★★☆☆

现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。

复现难度：★★★☆☆

现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。

产品化成熟度：★★★☆☆

论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。

可能的问题：转化为组合词对与射影几何问题，方法新颖且具有推广潜力。缺点：纯理论论文，缺乏实验验证，对非专业读者门槛较高。

主要参考文献

[1] S. M. Ross. Introduction to Stochastic Dynamic Programming. Academic Press, 1983.（Ross猜想原始出处）

[2] I. MacPhee and B. Jordan. Optimal search for a moving target. Probability in the Engineering and Informational Sciences, 2011.（之前最全面的部分证明）

[3] R. D. Smallwood and E. J. Sondik. The optimal control of partially observable Markov processes over a finite horizon. Operations Research, 1973.（POMDP分段线性值函数理论）

[4] 论文原文：Yunpeng Li. A proof of Ross's conjecture for two-site moving-target search. arXiv:2608.09368v1.

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！       

追目标，别头大，阈值策略兜底啦；读论文，找龙哥，群里一起聊方法。扫描下方二维码，或添加龙哥助手微信号：kangjinlonghelper，备注格式：研究方向+地点+学校/公司+昵称，备注齐全秒进群——五个专业群等你来。