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

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

## 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$ 的模板树，是否至多出现线性次？ | 不成立。下面给出这些大小的精确平移数。若额外要求副本两两顶点不交，面积界才给出线性数量，但这不是本题的候选模型。 |

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

## 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. 图示：齿长为二的情况

![32 乘 32 的单棵梳形宿主树；圆圈标出全部 64 个合法起点，蓝色标出起点为第 4 行第 4 列的一份 32 点模板副本。](../../assets/comb-candidates.svg)

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

| 边长 | 新位置筛选次数 | 最终候选数 | 候选数与边长之比 |
| ---: | ---: | ---: | ---: |
| 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).
$$

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

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

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

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

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

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

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