# 八邻接诱导森林：三次方复杂度仍然成立

状态：**已给出证明**。日期：2026-10-12。稳定标识：`grid-forest-matching-eight-neighbor`。

[English](eight-neighbor.en.md) · [研究目录](../README.md) · [仅对角邻接的不同归约](diagonal-only.zh.md)

本项把原三次方证明推广到八邻接诱导森林：方向词扩为四对互逆符号，完整历史收费和有限第二轴引理不变。

## 结论与模型

在边长为 $n$ 的正方形棋盘上，令道路集合为 $F$，道路数为 $N\le n^2$。允许的移动方向为

$$
D_8=\{(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(1,1),(-1,1),(1,-1)\}.
$$

**任意两道路格只要八邻接，就必须计入一条边；这个完整诱导图要求为森林。** 对角移动只要求目标为道路，不额外要求侧面的两个格也是道路。查询是一段含 $m$ 步的实际行走；答案为每个前缀仍合法的起点数。

将原候选列表算法的方向表扩为八方向，仍然只在首次到达一个相对位移时筛选候选。记逐候选检查总数为 $W$，则

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

空间仍为 $O(n^2)$。当 $m\ge n-1$ 时，同一个算法的最坏复杂度仍是 $\Theta(n^3+m)$。这不是所有可能算法的时间下界。

下面通过逐项迁移[已公开的完整历史收费证明](../proofs/cubic-bound.zh.md)证明上界。实验只是复核证据，不代替证明。原题面和四方向标准程序未修改。

## 1. 为什么不能直接复用“仅对角”的坐标归约

仅对角移动保持 $r+c$ 的奇偶性，可以分成两个互不相连的子问题。八邻接中的上下左右移动会切换奇偶性，因此这个拆分不再适用。

另一方面，不能拿原来的任意四邻接森林直接作为八邻接合法输入。例如三个格 $(0,0),(0,1),(1,1)$ 在四邻接下是路径，在八邻接下多出一条对角边，成为三角形。

本次迁移利用的是**树的方向词与收费结构**，不要求把八邻接棋盘变换成四邻接棋盘。

## 2. 方向词从两对互逆字母扩为四对

给南北、东西、东南西北、东北西南分别分配四对互逆字母。只允许相邻互逆字母消去，全部约简词构成秩四自由群 $\mathbb F_4$；其 Cayley 图仍是一棵树。

需要区分“位移相同”和“路径词相同”。若 $s,e,d$ 分别表示向南、向东、向东南，则

$$
\rho(d)=\rho(s)+\rho(e),\qquad d\ne se\quad(\mathbb F_4).
$$

这里 $\rho:\mathbb F_4\to\mathbb Z^2$ 是坐标同态。不能把对角字母替换成两步直角路径，也不能在词中施加这个额外关系。

给一棵实际八邻接道路树选根，各顶点对应从根出发的唯一路径词。树路不会立即折返，所以词已约简；每个方向确定唯一的下一格，所以不同树路不会给出同一个词。由此实际道路树嵌入抽象方向词树。

坐标同态在整个抽象树上不单射，但在一棵实际道路树的顶点集合上单射。原证明恰好只在这个有限、实际存在的范围内使用坐标单射。

## 3. 逐项核查原证明的依赖

### 3.1 查询前缀、星心与交域

令 $P_j=\{q_0,\ldots,q_j\}$ 是首次发现顺序中的前缀，$q_0=0$。只考虑仍有候选的最长前缀。实际行走使每个前缀连通；它能平移嵌入宿主诱导森林，因此其八邻接诱导图是树。这个最长成功前缀至多占据 $n$ 个查询行。

将每次非根成功检查按“宿主目标格、查询行”分组，每组最早一次作星心，至多 $nN$ 个。其余检查与星心组成标记 $(a,e,f)$，有

$$
h=f-e=(0,d),\quad d\ne0,\qquad
a+P_{t(f)}\subseteq F,\quad a+h+P_{t(e)}\subseteq F.
$$

标签 $h$ 由两个查询点的差得到，**不必是某个允许的单步方向**。即使实际查询大量走对角线，也可按查询行得到水平标签。

每笔标记带有连通资源

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

所有连通、交集与分量均按八邻接定义。不同成功前缀在标记目标相交，故它们处在同一棵宿主树中。树中连通子树的非空交仍连通，这与边是否对角无关。

### 3.2 统一平移、轴与单位容量

一个带标记的交域分量 $K$ 及其平移 $K+h$ 位于同一棵宿主树中。沿对应边的方向一致，故该平移对应统一的非恒等左乘 $g$，满足 $\rho(g)=h$。

若源词为 $\alpha$，查询顶点词为 $w_x$，则

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

非恒等自由群左乘具有唯一平移轴；把循环约简词分成原始周期，记周期长 $p$、幂次 $q$、平移长 $\ell=qp$，则周期坐标位移为

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

与 $g$ 交换的非恒等左乘沿同一轴移动 $sp$ 条边，坐标位移为 $s\delta$，其中 $s\ne0$ 为整数。轴的唯一性、周期分解和这个交换关系不要求自由群秩为二，在秩四中完全相同。

因此，同一查询类的不同源仍同行。若两个同类标记有相同早端资源像，它们的晚目标也相同，早查询点同行；该目标、该行的最早星心唯一，强迫两个标记相同。所以同类标记仍可按早端像单射收费。

### 3.3 共同切口和参考类

固定标签，取最大早下标作共同切口。达到这个下标的标记使共同前缀及其平移能同时放入一棵宿主树。利用子树交的连通性，切口先支付部分属于同一查询类，费用至多 $|G_h|$。

剩余严格资源满足 $S\cap(S+h)=\varnothing$。每个交域分量选早下标最大的严格标记作参考，参考查询类再支付至多一份分量预算。对任何非参考标记仍有

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

所以每个非参考源都成功匹配完整参考晚前缀，包括参考查询轴上的一段实际路径 $A$，长度为 $\ell$。以上步骤只用树的连通性、首次发现顺序和沿边一致的平移。

### 3.4 有限第二轴引理不变

考虑同一早端的两个非参考副本，源词为 $\alpha,\beta$。它们的相对左乘 $T=\beta\alpha^{-1}$ 与宿主平移交换。因此它们的轴向间距为 $|s|p$，物理源差为 $b-a=s\delta$。

若 $|s|p\le\ell$，参考轴段 $A$ 内可找到 $v,u_*^s v$ 两点，其中 $u_*$ 为参考平移的原始根。两个源都匹配这段实际路径，故下列两个真实宿主点都存在，并且坐标相同：

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

在同一实际道路树内使用坐标单射，得到

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

于是 $T$ 的唯一轴既是当前宿主轴，也是参考查询轴在该源处的像，强迫非参考查询轴等于参考查询轴，矛盾。不同查询类的轴确实不同：它们平移长度相等、坐标位移同为非零 $h$；同轴只能是相同平移或其逆，而逆的坐标位移为 $-h$。

因此仍有

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

这个证明只比较实际有限轴段中的点。即使八方向引入更多同位移的不同词，也没有在虚拟轴上错误地使用坐标单射。

### 3.5 分组容量和四份预算

严格资源与其标签平移不交，树的凸性保证其轴投影跨度至多 $\ell-1$。按投影左端点所在的长度 $\ell$ 区间分组：同组早端互异，可以按早下标递增分配尚未使用的完整前缀资源点；一个固定资源点只可能参与至多两组。

所以每标签仍有以下预算：

| 部分 | 预算 |
| --- | --- |
| 共同切口先支付的标记 | $\lvert G_h\rvert$ |
| 分量内参考查询类 | $\lvert G_h\rvert$ |
| 非参考严格标记 | $2\lvert G_h\rvert$ |

从而

$$
\widetilde M_h\le4|G_h|.
$$

这里的四来自 $1+1+2$，不来自四邻接的方向数量。将方向数增至八，不需要把预算系数也增至八。

## 4. 总费用仍为三次方

每个起点至多失败一次，因此失败检查总数至多 $N$。若第 $r$ 行有 $k_r$ 个道路格，则

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

这个恒等式只是在数同行道路格的有序对，不依赖它们是否相邻。

于是

$$
W\le nN+N+4\sum_h|G_h|
\le(n+1)N+4(n-1)N
=(5n-3)N.
$$

再加读入棋盘及逐步处理、输出的费用，得到 $O(n^2+m+nN)$。空道路、立即清空候选、重复位移等情况仍由原算法的处理覆盖。

## 5. 匹配下界不变

取第 $0,2,4,\ldots$ 行的全部格为道路，奇数行全部留空。每条道路行是一条水平路径；不同行相差至少二，所以八邻接也不会在行间增加边。这仍是合法诱导森林。

查询连续向右走 $n-1$ 步。第 $j$ 次筛选前仍有 $\lceil n/2\rceil(n-j+1)$ 个候选，因此

$$
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$。每步输出还需要 $\Omega(m)$ 时间，所以候选列表算法的最坏复杂度为 $\Theta(n^3+m)$。

## 6. 有限复核、覆盖范围与复现

脚本：[verify_eight_neighbor.py](../verify_eight_neighbor.py)。报告：[eight-neighbor-results.json](../eight-neighbor-results.json)，最终状态为 `passed`。

本轮复核包括：

- 边长 $1,2,3$ 的全部道路子集，分别有 $2,11,194$ 个八邻接诱导森林，共 $207$ 个。
- 对每个合法森林穷举全部 $8^4$ 条四步行走，共 $847,872$ 例。位集候选筛选与“每一步都移动所有剩余绝对位置”的独立答案计算一致，检查次数均满足上界。
- 共 $881$ 例完整历史收费证书，包括上述小棋盘的逐根遍历、固定种子的随机森林和行走、水平条带，以及混合八种方向的左右早横枝、弯曲幂次一、嵌套梳实例。
- 完整证书累计检查 $304,032$ 次候选扫描、$423$ 笔非参考标记、$163$ 对同早端相邻副本；其中包含非空的弯曲幂次一和重复早端情形。
- 大型混合方向实例最多含 $5,305$ 个道路点。构造先把四邻接边按六倍尺度替换为弯折八邻接路径，使各分枝在原顶点附近沿不同对角方向离开；随后显式检查全部诱导八邻接边。没有把未检查的四邻接构造直接当作八邻接合法输入。
- 三格直角路径作为负对照：四邻接森林检查接受，八邻接检查拒绝其三角形。

完整收费部分复用原验证器的证书算法，在独立模块中替换方向、森林判断、查询树和答案计算依赖；因此不是另一份完全独立实现的收费证明检查器。独立答案核对与逐笔证书复核是不同层面的检查。

本轮实际观察到的最大非参考资源使用次数为一，全部类别合计每标签每点最大为二。它们满足已证容量二、容量四，但**不能据此宣称这些通用系数可降低**。

实验准备时，一个缩短层距的旧构造参数被原四邻接森林检查拒绝，已换回原验证器使用的合法参数；另一个要求实验必须触达非参考容量二的覆盖断言未满足，已改为检查实际使用次数在一到二之间，并保留上面的实际统计。这两项均不构成上界反例。

在仓库根目录运行：

```text
python topics/simulation/grid-forest-matching/research/verify_eight_neighbor.py --output tmp/grid-forest-matching/eight-neighbor-results.json
```

数学结论依赖第 2～4 节的逐项证明迁移；实验只用于排查八方向邻接、候选答案和收费实现的不一致。

本项只推广匹配复杂度结论；四邻接和仅对角模型中的补点成树障碍不由本文迁移到八邻接。复核使用 Python 3.10+ 标准库。引用键为 `OccamGC2026EightNeighborGridForest`，见[引用说明](../../../../../CITATION.md)。证明状态表示仓库提供文字证明，不表示外部同行评审或证明助手形式化验证。

后续推广：[顶点与路径障碍并存](edge-obstacles.zh.md)允许选择性封边，要求实际可通行图为森林，并说明算法与交域的必要修改。