八邻接诱导森林：三次方复杂度仍然成立¶
状态：已给出证明。日期：2026-10-12。稳定标识：grid-forest-matching-eight-neighbor。
English · 研究目录 · 仅对角邻接的不同归约
本项把原三次方证明推广到八邻接诱导森林：方向词扩为四对互逆符号，完整历史收费和有限第二轴引理不变。
结论与模型¶
在边长为 \(n\) 的正方形棋盘上，令道路集合为 \(F\)，道路数为 \(N\le n^2\)。允许的移动方向为
任意两道路格只要八邻接，就必须计入一条边；这个完整诱导图要求为森林。 对角移动只要求目标为道路，不额外要求侧面的两个格也是道路。查询是一段含 \(m\) 步的实际行走；答案为每个前缀仍合法的起点数。
将原候选列表算法的方向表扩为八方向，仍然只在首次到达一个相对位移时筛选候选。记逐候选检查总数为 \(W\)，则
空间仍为 \(O(n^2)\)。当 \(m\ge n-1\) 时，同一个算法的最坏复杂度仍是 \(\Theta(n^3+m)\)。这不是所有可能算法的时间下界。
下面通过逐项迁移已公开的完整历史收费证明证明上界。实验只是复核证据，不代替证明。原题面和四方向标准程序未修改。
1. 为什么不能直接复用“仅对角”的坐标归约¶
仅对角移动保持 \(r+c\) 的奇偶性，可以分成两个互不相连的子问题。八邻接中的上下左右移动会切换奇偶性，因此这个拆分不再适用。
另一方面，不能拿原来的任意四邻接森林直接作为八邻接合法输入。例如三个格 \((0,0),(0,1),(1,1)\) 在四邻接下是路径，在八邻接下多出一条对角边，成为三角形。
本次迁移利用的是树的方向词与收费结构，不要求把八邻接棋盘变换成四邻接棋盘。
2. 方向词从两对互逆字母扩为四对¶
给南北、东西、东南西北、东北西南分别分配四对互逆字母。只允许相邻互逆字母消去，全部约简词构成秩四自由群 \(\mathbb F_4\)；其 Cayley 图仍是一棵树。
需要区分“位移相同”和“路径词相同”。若 \(s,e,d\) 分别表示向南、向东、向东南，则
这里 \(\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\) 由两个查询点的差得到，不必是某个允许的单步方向。即使实际查询大量走对角线，也可按查询行得到水平标签。
每笔标记带有连通资源
所有连通、交集与分量均按八邻接定义。不同成功前缀在标记目标相交，故它们处在同一棵宿主树中。树中连通子树的非空交仍连通，这与边是否对角无关。
3.2 统一平移、轴与单位容量¶
一个带标记的交域分量 \(K\) 及其平移 \(K+h\) 位于同一棵宿主树中。沿对应边的方向一致，故该平移对应统一的非恒等左乘 \(g\)，满足 \(\rho(g)=h\)。
若源词为 \(\alpha\)，查询顶点词为 \(w_x\)，则
非恒等自由群左乘具有唯一平移轴；把循环约简词分成原始周期，记周期长 \(p\)、幂次 \(q\)、平移长 \(\ell=qp\)，则周期坐标位移为
与 \(g\) 交换的非恒等左乘沿同一轴移动 \(sp\) 条边，坐标位移为 \(s\delta\)，其中 \(s\ne0\) 为整数。轴的唯一性、周期分解和这个交换关系不要求自由群秩为二，在秩四中完全相同。
因此，同一查询类的不同源仍同行。若两个同类标记有相同早端资源像，它们的晚目标也相同，早查询点同行；该目标、该行的最早星心唯一，强迫两个标记相同。所以同类标记仍可按早端像单射收费。
3.3 共同切口和参考类¶
固定标签，取最大早下标作共同切口。达到这个下标的标记使共同前缀及其平移能同时放入一棵宿主树。利用子树交的连通性，切口先支付部分属于同一查询类，费用至多 \(|G_h|\)。
剩余严格资源满足 \(S\cap(S+h)=\varnothing\)。每个交域分量选早下标最大的严格标记作参考，参考查询类再支付至多一份分量预算。对任何非参考标记仍有
所以每个非参考源都成功匹配完整参考晚前缀，包括参考查询轴上的一段实际路径 \(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_*\) 为参考平移的原始根。两个源都匹配这段实际路径，故下列两个真实宿主点都存在，并且坐标相同：
在同一实际道路树内使用坐标单射，得到
于是 \(T\) 的唯一轴既是当前宿主轴，也是参考查询轴在该源处的像，强迫非参考查询轴等于参考查询轴，矛盾。不同查询类的轴确实不同：它们平移长度相等、坐标位移同为非零 \(h\)；同轴只能是相同平移或其逆，而逆的坐标位移为 \(-h\)。
因此仍有
这个证明只比较实际有限轴段中的点。即使八方向引入更多同位移的不同词，也没有在虚拟轴上错误地使用坐标单射。
3.5 分组容量和四份预算¶
严格资源与其标签平移不交，树的凸性保证其轴投影跨度至多 \(\ell-1\)。按投影左端点所在的长度 \(\ell\) 区间分组：同组早端互异，可以按早下标递增分配尚未使用的完整前缀资源点；一个固定资源点只可能参与至多两组。
所以每标签仍有以下预算：
| 部分 | 预算 |
|---|---|
| 共同切口先支付的标记 | \(\lvert G_h\rvert\) |
| 分量内参考查询类 | \(\lvert G_h\rvert\) |
| 非参考严格标记 | \(2\lvert G_h\rvert\) |
从而
这里的四来自 \(1+1+2\)，不来自四邻接的方向数量。将方向数增至八，不需要把预算系数也增至八。
4. 总费用仍为三次方¶
每个起点至多失败一次，因此失败检查总数至多 \(N\)。若第 \(r\) 行有 \(k_r\) 个道路格，则
这个恒等式只是在数同行道路格的有序对，不依赖它们是否相邻。
于是
再加读入棋盘及逐步处理、输出的费用，得到 \(O(n^2+m+nN)\)。空道路、立即清空候选、重复位移等情况仍由原算法的处理覆盖。
5. 匹配下界不变¶
取第 \(0,2,4,\ldots\) 行的全部格为道路，奇数行全部留空。每条道路行是一条水平路径；不同行相差至少二，所以八邻接也不会在行间增加边。这仍是合法诱导森林。
查询连续向右走 \(n-1\) 步。第 \(j\) 次筛选前仍有 \(\lceil n/2\rceil(n-j+1)\) 个候选，因此
后续移动可在已经访问的路径上往返，使移动数增加到任意 \(m\ge n-1\)。每步输出还需要 \(\Omega(m)\) 时间，所以候选列表算法的最坏复杂度为 \(\Theta(n^3+m)\)。
6. 有限复核、覆盖范围与复现¶
脚本：verify_eight_neighbor.py。报告：eight-neighbor-results.json，最终状态为 passed。
本轮复核包括：
- 边长 \(1,2,3\) 的全部道路子集，分别有 \(2,11,194\) 个八邻接诱导森林，共 \(207\) 个。
- 对每个合法森林穷举全部 \(8^4\) 条四步行走，共 \(847,872\) 例。位集候选筛选与“每一步都移动所有剩余绝对位置”的独立答案计算一致，检查次数均满足上界。
- 共 \(881\) 例完整历史收费证书，包括上述小棋盘的逐根遍历、固定种子的随机森林和行走、水平条带，以及混合八种方向的左右早横枝、弯曲幂次一、嵌套梳实例。
- 完整证书累计检查 \(304,032\) 次候选扫描、\(423\) 笔非参考标记、\(163\) 对同早端相邻副本；其中包含非空的弯曲幂次一和重复早端情形。
- 大型混合方向实例最多含 \(5,305\) 个道路点。构造先把四邻接边按六倍尺度替换为弯折八邻接路径，使各分枝在原顶点附近沿不同对角方向离开；随后显式检查全部诱导八邻接边。没有把未检查的四邻接构造直接当作八邻接合法输入。
- 三格直角路径作为负对照：四邻接森林检查接受，八邻接检查拒绝其三角形。
完整收费部分复用原验证器的证书算法，在独立模块中替换方向、森林判断、查询树和答案计算依赖；因此不是另一份完全独立实现的收费证明检查器。独立答案核对与逐笔证书复核是不同层面的检查。
本轮实际观察到的最大非参考资源使用次数为一，全部类别合计每标签每点最大为二。它们满足已证容量二、容量四，但不能据此宣称这些通用系数可降低。
实验准备时，一个缩短层距的旧构造参数被原四邻接森林检查拒绝，已换回原验证器使用的合法参数；另一个要求实验必须触达非参考容量二的覆盖断言未满足，已改为检查实际使用次数在一到二之间，并保留上面的实际统计。这两项均不构成上界反例。
在仓库根目录运行：
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，见引用说明。证明状态表示仓库提供文字证明，不表示外部同行评审或证明助手形式化验证。
后续推广：顶点与路径障碍并存允许选择性封边，要求实际可通行图为森林，并说明算法与交域的必要修改。