顶点障碍与边障碍并存：四邻接、八邻接的森林匹配¶

状态：已给出证明。日期：2026-10-12。稳定标识：grid-forest-matching-edge-obstacles。

本项将已有三次方界推广到允许独立封闭路径的模型。核心是按实际开放边构造查询树和公共交域，同时修改重复位置的处理规则。

1. 模型和结论¶

棋盘边长为 \(n\)，可用格集合为 \(F\)，\(N=|F|\le n^2\)。输入另指定开放的无向边集 \(E\)；边的端点必须可用，方向来自四邻接或八邻接方向集。其余潜在邻接边可以单独封闭。要求实际可通行图 \(G=(F,E)\) 是森林，不再要求格点集合的完整几何邻接图为森林。

障碍静态、封边双向有效。八邻接仍以格点为顶点，对角边的几何交叉不自动产生路口。起点合法要求完整执行全部移动前缀，既不能进入障碍格，也不能穿过封闭边，失败后不能恢复。

对下面修正后的候选列表算法，两种方向集都满足

\[ W\le(5n-3)N,\qquad T=O(n^2+m+nN)\subseteq O(n^3+m),\qquad S=O(n^2). \]

\(W\) 只统计逐候选筛选，整体判零不产生逐候选检查。若不利用森林做整体判零，而是在首次闭环时扫描候选，则至多额外花 \(N\) 次检查，仍是三次方上界；这不属于上面显式常数所指的算法。

当 \(m\ge n-1\) 时，这个候选列表算法仍有匹配的 \(\Theta(n^3+m)\) 最坏下界。以下不是对所有可能算法的下界断言。

2. 算法确实要改：只记位置不够¶

记当前相对位置为 \(p\)，下一步到达 \(q\)。

如果 \(q\) 是新位置，对每个候选起点 \(a\) 检查目标 \(a+q\) 和边 \(\{a+p,a+q\}\) 是否可通行，删除失败候选。
如果 \(q\) 是旧位置，且 \(\{p,q\}\) 已经走过，所有存活候选都验证过这条无向边，无需再次筛选。
如果 \(q\) 是旧位置，但 \(\{p,q\}\) 从未走过，直接清空全部候选。

实现第三条时，只需把候选数组的有效长度置零，保留其已分配存储；不逐项删除候选。

第三条的理由：只要还有候选，已走过的相对位置和边构成一棵树。两旧点之间已有唯一路径，添加它们之间的新边会形成环。平移是顶点单射，不可能将这个环嵌入可通行森林。

四邻接例子：四格方块依次命名为左上 \(A\)、右上 \(B\)、右下 \(C\)、左下 \(D\)，仅开放 \(AB,BC,CD\)，封闭 \(DA\)。从 \(A\) 执行右、下、左后三步仍合法，第四步向上回到旧点 \(A\) 却必须失败。旧的“只看终点是否访问过”规则会错误地跳过它。

A──B
×  │
D──C

上图实线为开放路径，叉号为封闭路径；四个格点都可用。

八邻接例子更短：开放 \(AB,BC\)，封闭对角边 \(CA\)。右、下、左上形成一个三步闭环，最后一步同样应整体判零。四邻接的最短简单环为四条边，八邻接允许三条边，但处理原则相同。

可以记录每个首次发现点的父节点：已走图仍是树时，旧点间的已知边恰好是父子边，因此是否走过当前无向边能用常数时间判断。无需逐次搜索路径或运行并查集。空候选与整体越界继续沿用原来的常数时间处理。

3. 把“诱导查询树”换成“实际走过的查询树”¶

令 \(Q_j=(P_j,A_j)\) 为首次发现前缀中实际走过的点与边。只考虑仍有匹配的最长前缀：每次成功扩展增加一个点及其发现边，故这些前缀是嵌套的树。

成功起点 \(a\) 现在意味着

\[ a+P_j\subseteq F,\qquad a+A_j\subseteq E. \]

它不只是点集包含，还包括整棵查询树的边都开放。任意一次成功匹配仍把查询树映入一棵实际宿主树。两个成功前缀的非空交仍是连通子树，因为树中两点间的路径唯一。

注意：查询点的完整几何四邻接或八邻接图可以有额外边；那些边不一定开放，也不一定被查询走过。证明不能再把完整几何邻接当成查询边集。

4. 公共交域必须同时检查边¶

仍按“宿主目标、查询行”挑选最早星心。每笔非星心成功产生标记 \((a,e,f)\)，水平标签 \(h=f-e\)，并有

\[ a+Q_{t(f)}\subseteq G,\qquad a+h+Q_{t(e)}\subseteq G. \]

这里包含关系是图的包含。固定标签，定义图交域 \(H_h\)：

\[ V(H_h)=F\cap(F-h), \]

\[ E(H_h)=\{\{x,y\}\in E:\{x+h,y+h\}\in E\}. \]

边集的端点自动属于上述顶点集。完整早前缀资源 \(a+Q_{t(e)}\) 是这个图的连通子树，因为两份早前缀在两个源处都成功匹配。

不能只取公共顶点后，按几何邻接连边，甚至不能直接沿用原宿主在这些顶点上的全部开放边。例如三点 \((0,0),(0,1),(0,2)\) 都可用，只开放第一、第二点之间的边。取 \(h=(0,1)\)，公共顶点为前两点；它们之间的原边开放，但平移后的边封闭，故图交域内必须是两个孤立点。

5. 原收费证明如何迁移¶

依赖原完整历史收费证明以及八方向的方向词说明。关键调整如下。

证明对象	边障碍模型中的对应对象
道路诱导树	实际开放边构成的宿主树
几何邻接确定的查询树	实际已走过的查询树 \(Q_j\)
道路点集交域的诱导连通分量	同时保留两侧开放边的 \(H_h\) 的连通分量
查询前缀平移交集	查询树及其平移的图交集，边同样需在两侧存在

在每个带标记的交域分量 \(K\) 内，\(K\) 与 \(K+h\) 都连通。某笔标记的早晚成功前缀在目标处相交，保证它们处于同一棵宿主树；因此整个 \(K\) 与 \(K+h\) 也在这棵树中。

在任一共同开放边两端，平移保持方向，故平移仍对应一个统一左乘 \(g\)。四方向使用秩二自由群，八方向使用秩四自由群。实际树的路径词嵌入、坐标在实际树上的单射、唯一轴与周期交换性质均不依赖“所有几何邻接边都开放”。

共同切口中需要的连通性也保留：早晚前缀同时是一个宿主树中的子树，顶点交内的唯一路径必须在两份前缀中都出现，所以这些路径边也在它们的图交中。该论证使用实际树中的路径，而不是未经验证的几何邻接边。

于是原来的同查询类单位容量、共同切口的一份预算、分量内参考类的一份预算、有限第二轴引理和非参考分组的两份预算全部适用：

\[ \widetilde M_h\le4|V(H_h)|. \]

严格资源仍与其标签平移顶点不交，故其树轴投影跨度短于一个标签轴长。有限第二轴引理比较的两点仍在真实存在的有限成功副本中；它不需要宿主的所有潜在邻接边存在。整个推导没有增加“每个方向再收费一次”的因素。

查询树的行数至多 \(n\)，所以星心至多 \(nN\)；每个候选至多经历一次扫描失败，总量至多 \(N\)。若宿主第 \(r\) 行有 \(k_r\) 个可用点，则

\[ \sum_{h=(0,d),\ d\ne0}|V(H_h)| =\sum_r k_r(k_r-1) \le(n-1)N. \]

封边改变了交域的连通分量，但没有改变这个同行有序点对预算。因此

\[ W\le nN+N+4\sum_h|V(H_h)|\le(5n-3)N. \]

这个结论针对静态无向可通行森林的边感知候选算法。不能对原先只检查目的格的未修改 C++ 标准程序直接宣称正确性或这个复杂度结论。

6. 四邻接还有一个简单的常数尺度归约¶

作为较弱常数的独立理解：将原格点映到 \((2r,2c)\)，每条开放正交边的中点也置为道路，封闭边的中点设为障碍。得到边长 \(2n-1\) 的四邻接诱导森林，正是原图的边细分。

每步原移动变成同方向的两步；候选起点限制在原格点像上。顶点和边通行性完全对应。新的道路数为 \(N+|E|\le2N\)，所以原定理给出 \(O(nN)\) 检查量，足够再次推出三次方上界。限制起点只会减少候选数，不会增加同一移动序列的筛选费用。

八邻接不能直接照搬这个中点归约：两条交叉对角边会共用中点，错误地变成一个路口。上面的图交域与方向词证明覆盖八邻接，不依赖这种几何细分。

7. 更一般的输入仍有三次方匹配下界¶

现在可以令所有 \(n^2\) 个格都可用，只开放每行内部的水平边，封闭全部竖直边；八邻接时再封闭全部对角边。实际道路图是 \(n\) 条长度为 \(n\) 个顶点的水平路径，合法且 \(N=n^2\)。

连续向右走 \(n-1\) 步，产生

\[ W=n\sum_{j=1}^{n-1}(n-j+1) =\frac{n(n-1)(n+2)}2=\Theta(n^3). \]

后续在已走路径上往返，补足任意 \(m\ge n-1\)；逐步输出需要 \(\Omega(m)\)。两种方向集因此都有候选列表算法的匹配最坏界。

8. 有限复核与范围¶

验证脚本和结果报告已随本文公开，最终状态为 passed。报告保留逐例统计与收费分配指纹，并记录验证源码的 SHA-256；它不保存全部原始收费分配。

四邻接：二阶棋盘上全部可用点集与开放边集中的 46 个森林，穷举 11,776 条四步移动组合；另有 271 个完整历史收费实例。
八邻接：对应 83 个森林、339,968 条四步移动组合和 406 个完整历史收费实例。
合计 351,744 个短行走组合、677 个收费实例。独立答案计算逐步移动绝对位置，不跳过重复位置。
较大样例包括固定种子随机开放边森林、全道路水平条带、左右早横枝、弯曲幂次一和嵌套梳；八方向还包含全部八种移动方向的细化实例。
显式核对了“新边到旧点”的四步正交闭环与三步对角闭环：最后一步整体清空候选。三点交域负对照核对了必须同时检查平移边的开放性。
收费核心复用公开验证器，并显式替换开放边判断、查询树、宿主路径词和图交域分量；这不是完全独立实现的收费证明检查器。两种模型均有非空的非参考标记、重复早端和幂次一覆盖。

实验没有证明无穷范围的复杂度；一般结论来自第 2～5 节的算法与证明迁移。本文也没有新增“固定封边情况下补点成树”的结论，不能把允许改变边障碍与只添加顶点混为一谈。

python topics/simulation/grid-forest-matching/research/verify_edge_obstacles.py --output tmp/grid-forest-matching/edge-obstacles-results.json --check-published

--check-published 要求复跑报告与公开 JSON 完全一致；网站发布流程也执行这项检查。源码哈希统一按 UTF-8、LF 换行计算，以便不同系统复现。

9. 引用¶

引用键：OccamGC2026EdgeObstacleGridForest。固定版本与 BibTeX 见仓库引用说明。本项依赖原完整历史收费证明及八邻接方向词推广，不新增补树障碍结论。