GitHub 源文件 Markdown English

梳形树问答：线性次筛选后为何仍有平方个候选，却不超过三次方

讨论补记：2026-10-11。本文补充多尺度梳形与混合层高中的反例，记录单棵树、线性筛选阈值、模板出现次数三个问题，并说明图示构造的复杂度。英文版见English。

1. 讨论的是哪些量

用 \(n\) 表示网格边长，用 \(R=|F|\le n^2\) 表示道路格数；其他研究文档通常把道路格数记为大写字母 N。完整已访问位移集合为 \(P\)，合法起点集合为

\[ A(P)=\{a:a+P\subseteq F\}. \]

这里的“出现”指方向固定的平移匹配，允许不同副本重叠；不是两两不交的打包，也不是任意旋转或抽象树同构。

“有效变化”在本文中指现有程序首次遇到某个位移、实际遍历候选的筛选轮次，不要求候选数量真的改变。回走旧位置不增加筛选轮数，但仍计入移动数。初始零位移也不算一次筛选。

若最终仍有候选，完整访问模板恰触发 \(|P|-1\) 次筛选。设第 j 次筛选前的候选数为 \(q_j\)，真实候选检查总数为

\[ W=\sum_j q_j. \]

单个前缀的候选数与所有轮次的候选数之和，是不同的计数对象。

2. 三个问题的结论

问题	结论
把道路森林限制为一整棵树，能否排除候选很多的反例？	不能。下面的宿主就是单棵诱导网格树。限制连通可以作为子问题，但不解决后两项。
是否存在统一的线性筛选阈值，使之后只剩线性个候选？	不存在。对任意固定正整数 \(c\)，模板有 \(cn\) 个点时仍可有平方数量级的候选。
大小为 \(n\)、\(2n\)、\(4n\) 的模板树，是否至多出现线性次？	不成立。下面给出这些大小的精确平移数。若额外要求副本两两顶点不交，面积界才给出线性数量，但这不是本题的候选模型。

已有反例还允许模板大小和候选数量同时远大于边长，见原有参数族。以下固定常数倍的版本使计数更直观。

3. 单棵梳形宿主树的精确构造

所有坐标从零开始，行向下、列向右。取正整数 \(c\)，令 \(n\ge8\) 为 \(4c\) 的倍数，并记

\[ h=4c-2,\qquad g=\frac{n}{h+2}=\frac{n}{4c},\qquad w=\frac n2. \]

宿主道路这样放置，其余格子全部为障碍：

1. 在每一行 \(r=i(h+2)\)，其中 \(0\le i<g\)，铺满一条长度为 n 的横干。
2. 每条横干的偶数列 \(0,2,\ldots,n-4\) 向下伸出 h 格长的齿。
3. 最右列 \(n-1\) 全部设为道路，连接各层横干。

非横干行的两列 \(n-3,n-2\) 保持为空，避免齿与右侧连接干额外相邻。相邻层之间还留一行仅含连接干的间隔行。每层梳子只在横干右端与连接干相接，齿之间不相邻，因此全部四邻接边组成一棵树。

模板的根是左上角原点，包含长度为 w 的横干，以及从其偶数列向下伸出的 h 格长齿。因此

\[ |P|=w+\frac w2h=\frac n4(h+2)=cn. \]

模板横干必须落在某层宿主横干上，且根的列坐标必须为偶数。最右的几何上可容纳位置会把模板最后一根齿放到已删去的列上，因此不合法。恰好剩下

\[ A(P)=\left\{\bigl(i(h+2),2j\bigr):0\le i<g,\ 0\le j<\frac n4\right\}. \]

所以

\[ \boxed{|A(P)|=g\frac n4=\frac{n^2}{16c}.} \]

可以先走完模板横干、沿旧路返回，再逐齿下探并返回。这个真实移动序列的长度是 \(O(|P|)\)，新位置筛选恰为 \(cn-1\) 次。每个最终合法起点也匹配全部较早前缀，候选从未被删除后恢复。

固定常数	模板点数	新位置筛选次数	最终候选数
1	\(n\)	\(n-1\)	\(n^2/16\)
2	\(2n\)	\(2n-1\)	\(n^2/32\)
4	\(4n\)	\(4n-1\)	\(n^2/64\)

对任意固定常数 c，候选数与边长之比为 \(n/(16c)\)，随边长增长无界。这才是否定线性上界的理由；单个例子中候选数比边长大，并不足以否定大 O 上界。给定任何更早的固定线性阈值，可以选更大的固定 c；候选集合只减不增，所以在那个更早阈值处也至少保留这些候选。

4. 图示：齿长为二的情况

灰色格和细线是道路及全部相邻边，最右侧纵干把八层梳子连成一棵树。橙色圆圈表示起点，不是游走的当前位置；蓝色是一份完整副本。把蓝色副本的左上角平移到任意圆圈，它仍全部落在道路上。相邻起点对应的副本大量重叠，不需要各自占用独立的道路。

边长	新位置筛选次数	最终候选数	候选数与边长之比
16	15	16	1
32	31	64	2
64	63	256	4
128	127	1024	8
256	255	4096	16

边长翻倍，筛选轮数约翻倍，最终候选数变为四倍。渐近论证允许参数继续增长；题面边长上限内的有限例子只是对构造的核对。

5. 为什么这套构造不能制造超三次方开销

本节先讨论图中的固定齿长二：查询按上一节的顺序完成模板，然后可以任意继续移动。证明覆盖这条查询及其任意后续，不声称由此解决所有宿主、所有初始查询。

留在原层：候选多，可探索的新位置少。 一层梳子只有线性个道路格。更稳妥地，查询位移的行坐标还在零到二之间时，任何仍可匹配的完整前缀都只有三行、至多 n 列，所以只有线性个不同位置。每轮至多扫描平方个候选，这一阶段至多三次方开销。反复回走已经访问的点不增加筛选。

第一次跨过间隔行：起点列坐标被锁定。 完整模板已经保证每个起点在某层横干上。第一次离开上述三行时，新位移的行坐标只能为负一或三；从任一候选出发，它都落在层间间隔行或地图外。间隔行唯一的道路在最右侧连接干。因此若新位移为 \((x,y)\)，任何存活起点 a 都必须满足

\[ a_{\rm col}=n-1-y. \]

这使每层最多剩一个起点，总候选降为线性个。注意该轮筛选仍按删除前的候选数收费，最多平方次；候选减少只用于后续轮次。

跨层以后：新位置可以多，候选已经少。 有候选存活时，完整模板平移进道路后是单射，故不同位移数不超过道路格数。剩余最多平方量级的筛选，各扫描线性个候选，仍至多三次方。最终清空候选的失败轮可以另外收费，之后只有移动读写。

这套构造无法同时保留平方个候选、又为它们提供平方次新位置筛选。

6. 加长梳齿或混合不同齿高，为什么仍不直接突破

加长齿会增加单层可访问位置，却减少可堆叠的层数。统一齿高下，模板规模为 \(\Theta(n(h+1))\)，候选数量为 \(\Theta(n^2/(h+2))\)，静态乘积仍为三次方量级。

静态乘积本身不是整个过程的上界。 较早前缀的候选可能更多，不能直接用最终候选数乘全部轮数。对第 3 节的构造、上述访问顺序及其任意后续，可以严格分开计费：

1. 完成初始横干并作第一次竖直筛选，费用为 \(O(nR)\)。
2. 此时起点已位于各层横干的偶数列，总数为 \(O(gn)\)。在首次离开行带零到 h 之前，仍有候选的前缀至多有 \(n(h+1)\) 个不同位移，费用为 \(O(g(h+1)n^2)\)。
3. 第一次跨过间隔行后，起点列坐标固定，剩余至多 g 个候选；之后至多道路格数级别的筛选，费用为 \(O(gR)\)。清空候选的最后失败轮另加 \(O(R)\) 即足够。

由 \(g=n/(h+2)\) 和 \(R\le n^2\)，得到

\[ W=O\bigl(nR+g(h+1)n^2+gR+R\bigr)=O(n^3). \]

带内的不同位置数上界应应用于最后仍有候选的前缀，不能假设某个已经失败的起点继续见证未来的宽度。

不同齿高放在同一张图中时，不能让每个高度重新占满棋盘。原有混合层高证明针对以空行分隔的梳子森林、先完成横干再交错增长各齿的查询，按每个候选能存活多久计费，以同一张图的总齿高支付全部费用。该结论有自己的宿主与访问顺序前提，不在这里扩张为任意连接方式的混合梳子。

7. 这次讨论的结论与后续进展

单棵树反例、线性阈值失败和一般梳形尺度关系已经记载在原有文档中。本文补充了固定常数倍模板的精确计数、可保留的静态图示，以及穿过间隔行后锁定起点列坐标的完整计费解释。

后续关于“任意森林能否补点成为一棵诱导网格树”的问题，以及两棵大树、线性数量大树之间都无法连接的反例，另见森林补树问题。该问题讨论能否从森林归约到单树，与这里已经连通的梳形宿主互为补充。

它们否定的是“经过线性轮数后候选必降到线性”这一辅助命题。候选数很大，不自动给出超三次方的总工作量。

本篇的局部解释只处理上述构造。后续一般证明已将一般诱导四邻接森林的上界从 \(O(n^3\log(n+1)+m)\) 改进为 \(O(n^3+m)\)；全部移动的读入与输出计入 \(O(m)\)。完整研究过程见研究综述。