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

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

[English](edge-obstacles.en.md) · [研究目录](../README.md) · [八邻接诱导森林](eight-neighbor.zh.md)

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

## 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$。

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

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

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

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

```text
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. 原收费证明如何迁移

依赖原[完整历史收费证明](../proofs/cubic-bound.zh.md)以及[八方向的方向词说明](eight-neighbor.zh.md)。关键调整如下。

| 证明对象 | 边障碍模型中的对应对象 |
| --- | --- |
| 道路诱导树 | 实际开放边构成的宿主树 |
| 几何邻接确定的查询树 | 实际已走过的查询树 $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++ 标准程序](../../std.cpp)直接宣称正确性或这个复杂度结论。

## 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. 有限复核与范围

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

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

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

```text
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 见[仓库引用说明](../../../../../CITATION.md)。本项依赖原完整历史收费证明及八邻接方向词推广，不新增补树障碍结论。