# 候选列表算法的一般三次方上界

日期：2026-10-12。本文件给出独立的证明链，接续[容量二证明稿](reference-capacity.zh.md)的审计。关键间距引理只使用两份实际存在的有限轴段，**不依赖无限物理轴延长、平面分离或高幂条件**。

## 1. 结论与宏观思路

设正方形网格中的道路诱导图是一片森林，记棋盘边长、道路数、移动数和候选检查总数为

$$
n,\qquad N\le n^2,\qquad m,\qquad W.
$$

则仅在新位移出现时筛选的候选列表算法满足

$$
\boxed{W\le(5n-3)N},\qquad
\boxed{T=O(n^2+m+nN)\subseteq O(n^3+m)}.
$$

空间仍为平方量级。已知水平道路条带族在移动数至少为棋盘边长减一时给出匹配的三次方加移动数下界，因此一般最坏上界中的对数可以去掉。

旧证明逐时刻估计候选数，再对前缀大小求和，给每个尺度重复领取了一份道路预算。本证明改为把**全部历史成功检查**按“宿主目标与查询行”配对，再按水平位移标签付费：

1. 每个目标、每个查询行只保留最早一次成功，直接支付这些星心。
2. 其余成功与星心组成带水平标签的标记，每笔标记携带完整早前缀作为资源。
3. 固定标签，先支付共同切口前的一类标记；剩余资源各自沿宿主轴短于一个标签长度。
4. 在每个宿主交域分量中删去一个参考类。同早端的其他副本沿轴相隔超过一个标签长度，因此可按标签长度分组：组内早端互异，一个道路点至多参与两组。
5. 每个标签至多占四份交域预算。对全部标签求和，交域大小只是同行道路点的有序对数，故总量为道路数乘棋盘边长。

这些分组只用于证明，不增加算法步骤。

### 1.1 符号与对象速查

| 符号 | 含义与所在空间 |
| --- | --- |
| $n,N,m,W$ | 棋盘边长、道路点数、实际移动数、逐候选检查总数；不要把边长与道路数混用 |
| $P_j,t(x)$ | 查询的前 $j+1$ 个不同位移，以及点的首次发现下标；下标不是实际行走步数 |
| $a,e,f,h=f-e$ | 晚候选起点、早查询点、晚查询点、水平标签；早候选是 $a+h$ |
| $G_h,K,S_{a,e}$ | 道路与其平移的交域、交域的一个连通分量、标记的完整早前缀资源；资源是一组宿主道路点 |
| $w_x,\alpha,\rho$ | 查询路径词、宿主源的路径词、路径词到网格位移的映射；同位移的抽象词未必相同 |
| $g,k_e$ | 宿主分量上的统一平移词及其拉回查询后的平移词；两者通过源的路径词共轭 |
| $L,J$ | 当前宿主平移轴、选定的参考查询轴；轴属于方向词树，不是网格中的水平直线 |
| $p,q,\ell=qp,\delta=h/q$ | 原始方向周期的边数、标签的周期重复次数、标签轴长、每周期的网格位移 |
| $\lambda_{a,e}$ | 资源向宿主轴投影后的最左坐标；分组使用这个坐标和树上边数，不能用水平包围盒代替 |

“给标记分配资源点”只是一个计数对应：给每笔真实成功检查找一个允许归账的道路点，并限制每点的归账次数。道路不会真的被删除或消耗，程序也不需要计算这些轴和分组。

### 1.2 四份预算各付了什么

| 固定一个标签后的类别 | 每个交域点最多承担 | 为什么足够 | 证明位置 |
| --- | --- | --- | --- |
| 共同切口先支付的标记 | 一次 | 属于同一查询平移类，早端资源像单射 | 第 3.3、4 节 |
| 每个交域分量内的参考类 | 一次 | 同类单射；不同交域分量点不交 | 第 3.3、5 节 |
| 其余严格标记 | 两次 | 每组有单位分配，一个资源点至多参与两组 | 第 6、7 节 |

因此每标签的系数四来自“一加一加二”。再在标签之外支付星心和每候选最多一次的失败，就得到总扫描界中的系数。不能为不同前缀尺度重新领取这四份预算，因为这里已经包含固定标签的**全部历史**。

单份资源短于一个标签轴长，并不表示多份资源的连通并也短；左右早横枝反例恰好否定后者。新证明允许这样的并集很长，只控制它在每个点上的分组参与数。

## 2. 成功检查、星心和资源

按首次发现顺序，把不同查询位移记为

$$
q_0=0,q_1,\ldots,q_L,\qquad P_j=\{q_0,\ldots,q_j\}.
$$

这里只保留至少有一个候选成功匹配的最长前缀。它记为查询树；最后一次可能清空候选的失败筛选单独计入失败费用。实际行走保证前缀连通，存在完整匹配保证它们是诱导树，最终成功查询的行数至多为棋盘边长。

对每次非根成功检查，设晚候选为起点，查询点映到宿主道路目标。固定目标和查询行，取最早成功点作星心。此组之后的每次成功形成唯一标记

$$
(a,e,f),\qquad t(e)<t(f),\quad h=f-e=(0,d),\quad d\ne0.
$$

最早星心对应的候选为晚候选加标签。完整历史给出

$$
a+P_{t(f)}\subseteq F,\qquad a+h+P_{t(e)}\subseteq F.
$$

固定标签，定义交域和每笔标记的资源：

$$
G_h=F\cap(F-h),\qquad S_{a,e}=a+P_{t(e)}\subseteq G_h.
$$

每份资源是连通子树。记标签的标记数为

$$
\widetilde M_h.
$$

每目标每查询行只有一个星心，每个候选至多失败一次，所以

$$
W\le(n+1)N+\sum_h\widetilde M_h.
$$

以后只需证明固定标签的标记数不超过四倍交域大小。

## 3. 方向词树与三个基本事实

用东西、南北两对互逆字母记录网格路径，并允许相邻互逆字母消去。全部约简词构成自由群，其 Cayley 图是一棵树。把一棵实际道路树任意选根，每个顶点用从根到它的唯一路径词表示，就得到这棵自由树中的一个子树。

理由是实际树路没有立即回头，方向词已经约简；方向确定下一格，所以不同树路不会成为同一个约简词。词到网格坐标的映射是群同态，但在全部自由树上不单射；**只有同一实际道路树的顶点上才可用“同坐标则同顶点”。**

记坐标同态和查询根词为

$$
\rho:\mathbb F\longrightarrow\mathbb Z^2,\qquad w_x\in\mathbb F.
$$

若宿主源在方向词树中的顶点为

$$
\alpha,
$$

则其完整前缀中的查询点像为

$$
\alpha w_x.
$$

保持全部边方向的连通平移对应一个统一的左乘。

### 3.1 一个宿主交域分量有统一平移

取含标记的交域连通分量。资源包含源和早端像，而早、晚两个合法前缀在标记目标处相交，所以该分量及其标签平移都位于同一棵实际道路树。标签平移在整个分量中对应同一个非恒等左乘，记为

$$
g:K\longrightarrow K+h,\qquad \rho(g)=h.
$$

在早端像处使用它，得到

$$
g\alpha w_e=\alpha w_f,\qquad
k_e:=w_f w_e^{-1}=\alpha^{-1}g\alpha.
$$

称相同查询平移词的标记为同一查询类。

### 3.2 轴、周期及坐标

非恒等左乘有唯一平移轴。把群元素写为循环约简词的共轭，再将循环词向两端重复，即得到该轴。离轴点到其像的距离等于轴向平移长度加两倍离轴距离，故轴唯一。

取轴方向为标签移动方向，令最短方向周期、标签轴长和幂次为

$$
p\ge1,\qquad \ell=qp,\qquad q\ge1.
$$

这里没有高幂假设。每个最短周期的网格位移为

$$
\delta=h/q\ne0.
$$

交换该左乘的非恒等左乘保持其轴，不能反转非零平移，也不能固定轴点；它沿轴作非零整数平移。保持边方向又要求平移量是最短周期的整数倍。因此其轴位移和网格位移分别为

$$
sp,\qquad s\delta,\qquad s\in\mathbb Z\setminus\{0\}.
$$

非恒等左乘也不能保持另一条不同轴：轴上的反射会给出固定顶点或翻转边，均不可能由自由群左乘产生；非零平移的轴已经唯一。

### 3.3 固定查询类有单位资源容量

先在一个宿主分量内取同类的两个源，其顶点记为

$$
\alpha,\beta.
$$

相同查询平移词的共轭关系说明

$$
T=\beta\alpha^{-1},\qquad Tg=gT.
$$

如果两源不同，上一节说明源差为非零整数倍的水平周期，所以两源同行。若它们的早端资源像相同，则晚目标也相同，两个查询早端也同行。最早星心在该目标、该行唯一，因此早端和源都相同。

所以同一查询类的标记可单射到各自的早端资源像。不同宿主交域分量的像不相交，这条单位容量结论也可跨分量合并。

## 4. 一次共同切口：先付一份交域预算

固定标签，令最大早下标、共同前缀和其中的旧配对集合为

$$
t_* =\max t(e),\qquad P=P_{t_*},\qquad I=P\cap(P-h).
$$

达到最大早下标的标记，其两个候选都匹配整个共同前缀。因此共同前缀与其平移像可同时放入一棵宿主树，旧配对集合连通或为空。

任一标记对应的集合

$$
R_{e,f}=P_{t(e)}\cap(P_{t(f)}-h)
$$

连通并含早端：平移后它正是两个完整成功前缀的交，交中含标记目标。

在查询的任一连通平移交集中，查询词

$$
w_{x+h}w_x^{-1}
$$

沿边恒定，因为原边及平移边方向相同。

于是以下标记全属于旧配对集合的同一个查询类：晚端已经在共同前缀内的标记；或者早前缀碰到旧配对集合的标记。后一种情形中，取相交点，利用上面的连通集合把早端接到旧配对集合；沿路查询平移词相同。第 3.3 节可用一份交域预算支付所有这些标记。

其余标记称为严格标记。令旧配对集合的首次访问时刻为截止；若它为空，截止取共同前缀之后一位。则严格标记满足

$$
\tau=\min_{x\in I}t(x)\quad(I\ne\varnothing),\qquad
\tau=t_*+1\quad(I=\varnothing),
$$

$$
t(e)<\tau,\qquad t(f)>t_*,\qquad
P\cap(P_{\tau-1}+h)=\varnothing.
$$

特别地，每份严格资源单独满足

$$
S_{a,e}\cap(S_{a,e}+h)=\varnothing.
$$

故只需继续支付严格部分：

$$
\widetilde M_h\le |G_h|+\widetilde M_h^{\rm strict}.
$$

## 5. 参考晚前缀为什么被所有剩余源匹配

在一个宿主交域分量内，选严格标记中早下标最大的为参考，记为

$$
(a_*,e_*,f_*),\qquad J=\operatorname{Axis}(k_{e_*}).
$$

参考查询类按第 3.3 节支付一份分量预算。

对任一非参考标记，早端先于参考早端；若它的晚端不晚于参考晚端，则参考标记的连通集合

$$
R_{e_*,f_*}=P_{t(e_*)}\cap(P_{t(f_*)}-h)
$$

同时包含该早端与参考早端，强迫两者查询平移词相同，矛盾。因此

$$
t(e)<t(e_*)<t(f_*)<t(f).
$$

非参考晚源完整匹配自己的晚前缀，因而完整匹配参考晚前缀。参考早晚点的查询唯一路径包含一段参考轴，其边数至少为标签轴长。固定其中一段，记为

$$
A\subseteq P_{t(f_*)}\cap J,\qquad |E(A)|=\ell.
$$

每个剩余源都完整匹配这同一段实际查询路径。

## 6. 有限第二轴引理：同早端副本必须相隔超过标签轴长

取同一宿主分量中具有相同早端、不同源的两个非参考标记。晚端由早端加标签唯一确定，所以它们有同一个查询词及查询轴，记为

$$
I_e=\operatorname{Axis}(k_e),\qquad L=\operatorname{Axis}(g).
$$

相同词的共轭关系给出

$$
\alpha I_e=\beta I_e=L,\qquad
T=\beta\alpha^{-1},\qquad Tg=gT.
$$

不同查询类的轴不同：它们都共轭于同一个宿主平移，平移长度相等、网格位移同为非零标签；若轴相同，只可能是同一个平移或其逆，逆的网格位移相反，故不能发生。因此

$$
I_e\ne J.
$$

按第 3.2 节，相对平移的轴位移与网格位移为

$$
sp,\qquad b-a=s\delta,\qquad s\ne0.
$$

反设轴间距不超过标签轴长：

$$
|s|p\le\ell.
$$

参考轴的最短周期同样是周期边数和周期位移。令其原始平移为

$$
u_*,\qquad k_{e_*}=u_*^q,\qquad \rho(u_*)=\delta.
$$

实际参考轴段长度为标签轴长，所以可在其中找到两点

$$
v,\quad u_*^s v\in A.
$$

它们沿轴相差相应周期数，网格坐标相差相应周期位移。两份完整参考晚前缀保证下面两个宿主点都真实存在于同一道路树中；它们坐标相同：

$$
a+\rho(u_*^s v)=a+s\delta+\rho(v)=b+\rho(v).
$$

实际道路树中的坐标单射便给出群顶点相同，进而

$$
\alpha u_*^s v=\beta v,\qquad
T=\beta\alpha^{-1}=\alpha u_*^s\alpha^{-1}.
$$

相对平移的轴因此既是宿主轴，又是参考轴在该源处的像。唯一轴性质给出

$$
L=\alpha J=\alpha I_e,
$$

与查询轴不同矛盾。所以严格有

$$
\boxed{|\Delta_{\rm axis}(a,b)|>\ell.}
$$

**依赖边界。** 两个被比较的点都在同一段实际查询路径的两个成功副本中。没有把虚拟轴上的同坐标点当成同顶点，也没有声称整个交域能周期延长。证明对直轴、弯曲轴和所有正整数幂次同时成立。

## 7. 资源左端点分组：非参考部分容量二

在宿主轴上选整数坐标，以最近点投影记资源的左端点和跨度。单份严格资源的跨度小于标签轴长：否则连接两个极端投影的轴段包含在这份连通资源中，可取一对相差标签轴长的轴点。它们在宿主平移下对应，网格相差标签，违反该资源与其平移不交。

因此

$$
\lambda_{a,e}=\min\pi_L(S_{a,e}),\qquad
\operatorname{diam}\pi_L(S_{a,e})\le\ell-1.
$$

同早端的两份资源是保持宿主轴的相对左乘像，最近点投影随该平移移动。因此第 6 节的间距也适用于资源左端点：

$$
e=e',\quad a\ne b\quad\Longrightarrow\quad
|\lambda_{a,e}-\lambda_{b,e}|>\ell.
$$

按以下半开区间分组：

$$
\lambda_{a,e}\in[j\ell,(j+1)\ell),\qquad j\in\mathbb Z.
$$

每组早端互异。按早下标递增逐笔分配资源点：第几笔的完整早前缀包含此前所有不同的查询早端、自己的早端和根，点数超过此前已经分配的点数，故总能选到一个未使用的资源点。于是组内有单位分配。

一个宿主点若属于某笔资源，其投影坐标和资源左端点必须满足

$$
x=\pi_L(z),\qquad \lambda_{a,e}\in[x-\ell+1,x].
$$

该整数区间最多遇到两个分组。因此合并所有组的单位分配，每个资源点最多被使用两次。非参考严格部分容量至多二；参考类另占一次，合计

$$
\widetilde M_h^{\rm strict}(K)\le3|K|.
$$

**无需不交的连通资源并。** 多份资源可向相反方向伸展并跨过标签长度；其并甚至可以跨许多分组。计费只要求每份资源短、同早端副本间距大，以及每点至多参与两组。

![容量二分组示意：包含固定点的资源，其左端只可能落入两个相邻分组。](../../assets/cubic-axis-bins.png)

图中标签轴长为六，固定点的投影为九；包含该点的资源左端只能是四到九，至多落入两个组。这是轴投影的计数示意，不声称图中各区间共同构成某个实际查询。可用[绘图脚本](../plot_cubic_bins.py)重建。

## 8. 合并分量、标签及全部历史

每个宿主交域分量独立选择参考，分量彼此点不交。加入共同切口的一份预算，得到

$$
\boxed{\widetilde M_h\le4|G_h|.}
$$

若第几行的道路数记为

$$
k_r,
$$

则跨全部正负水平标签求和恰好计数同行不同道路点的有序对：

$$
\sum_{h=(0,d),\ d\ne0}|G_h|
=\sum_r k_r(k_r-1)\le(n-1)N.
$$

再加星心和每候选最多一次的失败检查，最终得到

$$
\begin{aligned}
W&\le(n+1)N+\sum_h\widetilde M_h\\
&\le(n+1)N+4(n-1)N=(5n-3)N.
\end{aligned}
$$

读图、处理全部移动和输出仍要计入，故

$$
T=O(n^2+m+nN)\subseteq O(n^3+m).
$$

空道路或没有移动时扫描为零；只有根成功时没有标记；某次检查清空候选后的所有移动只花常数处理时间。证明没有假定最后失败的查询前缀仍然是树。

下界也可以直接核对：取隔行铺满的水平道路路径，连续向右走到最右端。每一行的候选数依次从棋盘边长降至二，因而

$$
W=\left\lceil\frac n2\right\rceil
\sum_{j=1}^{n-1}(n-j+1)
=\left\lceil\frac n2\right\rceil\frac{(n-1)(n+2)}2
=\Theta(n^3).
$$

之后可沿已访问边来回补足移动数，输出仍需线性时间。因此在下列移动范围内，最坏复杂度上下界匹配：

$$
m\ge n-1\quad\Longrightarrow\quad
T_{\rm worst}=\Theta(n^3+m).
$$

## 9. 审计记录

理论审计完成了上述逐项推导。与上一稿相比，有限第二轴引理移除了无限物理延长和高幂限制，固定标签费用由五份降为四份。已否定的连通资源不交猜想不参与证明。

程序验证用于检查定义、分类和资源分配实现，不替代第 4—8 节的一般论证。后续使用[独立完整收费验证器](../verify_cubic_bound.py)，逐笔构造收费证书；[结果文件](../cubic-bound-results.json)的状态为 `passed`。中英题解、研究综述与历史文档的状态也已同步。

### 9.1 独立验证的范围

新实现从真实行走重算每次候选集合，收集成功事件后再取星心；不使用旧脚本的历史、场景分类或分组验证函数。轴坐标通过抽象方向词树上到两个远端轴点的距离差计算，不使用物理轴延长或水平包围盒。每个标签、每个实际交域分量分别选择参考，检查共同切口类、时间反序、单份资源短跨度、同早端间距和逐笔收费映射。

| 检查项目 | 实际范围或结果 |
| --- | --- |
| 全部实例 | 1,886 个，全部通过 |
| 三阶网格穷举 | 全部 512 个点集中的 416 种诱导森林；对每个道路根检查一种深度优先发现顺序，共 1,710 个实例（含空图） |
| 构造与顺序扰动 | 24 个；包括原八例、左右早横枝、低幂、幂次一、嵌套梳、弯曲梳及较小弯曲梳的三根乘三种顺序 |
| 随机与边界 | 固定种子的 120 个森林、30 条随机行走及两个单点边界实例 |
| 候选扫描 | 604,846 次；全部答案和扫描数与独立位集实现一致 |
| 额外答案复核 | 1,871 个小例按完整前缀字面枚举；17 个实例与原 C++ 程序比较 |
| 全部历史标记 | 13,750 笔，分布于 748 个实例内标签组；每笔恰被分配一次 |
| 收费分解 | 共同切口 3,137 笔，参考类 8,390 笔，非参考 2,223 笔 |
| 同早端间距 | 1,367 对排序后相邻副本通过严格间距检查；其中两对来自幂次一弯曲轴 |
| 非空幂次覆盖 | 有非参考标记的分量中，幂次一、二、三各一个，至少四的十九个；其中五个为弯曲轴 |
| 实际最大占用 | 非参考分配为一、每标签全部分配为二；均在证明的二和四以内，不说明常数最优 |

三阶网格部分穷举的是道路点集和起点，**没有穷举所有发现顺序或所有行走**。较大的弯曲梳保留原顺序验证；三根、三种顺序的扰动放在 1,375 点的同族实例上，避免完整收费证书的计算量过大。此前较大扰动运行未完成，不计入上表。

### 9.2 幂次一弯曲轴不是空验证

该构造先指定粗图中所需的前缀边：查询沿竖干经过高度三、九、二十一，随后从下往上各访问一条向右边；宿主放入相位零、二的晚前缀与对应平移早前缀，并连接横轴。粗图的点集本身不满足诱导森林条件，不能直接当作正式输入。

将顶点坐标乘六；竖边换成六步竖路径，横边换成“右二、下二、右二、上二、右二”的十步弯曲路径。只细分指定的粗边，再检查最终点集的**全部**四邻接边确实构成树。最终构造有 811 个道路点，真实行走 294 步，产生七笔标签标记；三笔参考标记、四笔非参考标记。

这个标签的网格位移为向右六格，但沿树轴走十条边才到对应点。十步方向周期已经原始，所以幂次为一。两个非参考查询早端各有两个副本；副本相差两个原始周期，严格大于一个标签轴长。它同时验证“弯曲”“最低幂次”“重复早端”和“参考类不同”，而非只检查没有剩余标记的空场景。完整逐笔分配保存在结果文件中。

### 9.3 从一次真实成功检查走到资源分配

仍用上一节保存的幂次一实例，坐标采用生成器的构造坐标。选取记录中的非参考标记

$$
a=(-54,0),\quad e=(54,0),\quad f=(54,6),\quad h=(0,6),\qquad t(e)=54,\quad t(f)=146.
$$

早候选与晚候选的对应成功，恰好到达同一宿主目标：

$$
(a+h)+e=(0,6)=a+f.
$$

早查询点是该目标、该查询行的最早成功点，因此是星心。早候选完整匹配到早下标，晚候选完整匹配到晚下标；这才允许形成标记，不能只核对上面两个终点。该例前五十五个查询点沿竖干依次发现，所以这笔标记的资源恰为

$$
S_{a,e}=\{(r,0):-54\le r\le0\},\qquad |S_{a,e}|=55.
$$

它属于第零组，证书把它分配到资源中的源点。下面列出同一标签的全部七笔分配；早晚列均为不同位移的首次发现下标，不是实际移动步数。分组编号依赖所选轴坐标原点，本身没有额外几何含义。

| 晚源 | 早下标 | 晚下标 | 收费类别 | 分配的宿主点 |
| --- | --- | --- | --- | --- |
| (-126, 0) | 126 | 136 | 参考类 | (0, 0) |
| (-126, 6) | 126 | 136 | 参考类 | (0, 6) |
| (-126, 12) | 126 | 136 | 参考类 | (0, 12) |
| (-54, 0) | 54 | 146 | 第零组 | (-54, 0) |
| (-54, 12) | 54 | 146 | 第二组 | (-54, 12) |
| (-18, 0) | 18 | 156 | 第零组 | (-18, 0) |
| (-18, 12) | 18 | 156 | 第二组 | (-18, 12) |

同组内部实际按早下标递增分配：第零组先支付早下标十八的标记，再支付早下标五十四的标记。后者的资源包含前者已经领取的点，但还含有未领取的点，因此资源相交没有妨碍单位分配。同一早端的两个副本则分别进入第零组和第二组，符合间距限制。

这个例子展示真实账目如何对应定义；七个分配点恰好互异，并不证明所有实例都只需单位容量。一般证明仍使用两份非参考预算及四份总预算。

该记录验证了证明在上述输入上的各项断言；所有规模、根和发现顺序上的一般结论来自第 2—8 节。