反向搜索枚举 | Codeboy's Blog

若所有合法对象之间可以通过小改动相互转换，直接在这张“解的图”上搜索会不断回到已经见过的对象。保存全部已见集合能去重，却可能比输入大得多。反向搜索先为每个非根对象指定唯一父亲，把解图中的许多边舍去，只遍历剩下的一棵树。

形式陈述

唯一父亲与有限到根

设S是有限的完整解集合，给定根 $r\in S$ 。对每个x≠r，父函数f(x)返回它的一个合法邻居，并保证重复应用f最终到r。f必须是确定的；“任选一个看起来更好的邻居”尚不是可供复算的父函数。[1，§2]

另外有固定邻居接口Adj(x,j)，j从0到D−1。每个槽返回x的一个邻居或空；每个邻居恰在一个槽中出现，顺序由x唯一决定。还必须有父边的反向可枚举性：对每个非根y，存在j使 $\operatorname{Adj}(f(y),j)=y$ 。无向或对称邻接足以满足它；仅知道f(y)是y可枚举的邻居，对一般有向接口并不够。反向遍历只接受满足

f(y)=x

的邻居y作为孩子。输出的是每个完整解本身，而非它的构造历史；每个对象恰一次，不默认按成本排序。首项、间隔、收尾与工作空间仍按枚举复杂性分别核算。

父指针构成一棵以r为根的树。若有父指针环，环上点就永远到不了r；若有第二个没有父亲的点，也违反唯一根约定。因而从r反向遍历父边，会且只会访问全部S。

为什么不需要保存已见集合

可以用深度优先遍历，对当前x依次尝试邻居槽，只有f(y)=x才进入。每个非根解只有一个父亲，所以不会从两条不同树边再次进入它。去重依赖这个数学不变量，不依赖“碰巧没有走回去”。

递归实现仍需保存栈，不能因此称常数空间。若还能从孩子y和父亲f(y)恢复父亲中产生y的邻居槽编号，则可在回退时重新计算父亲和槽号，只保留当前对象与一个游标，不保留整条递归栈。[1，Theorem2.4]

text

输出根 r；x ← r；j ← 0
重复：
    若 j < D：
        y ← Adj(x,j)；j ← j+1
        若 y 非空且 y 不是根且 f(y)=x：
            x ← y；j ← 0；输出 x
    否则：
        若 x=r，结束
        child ← x；x ← f(child)
        j ← 在 x 中产生 child 的槽号 + 1

最后的“+1”不可省，否则返回父亲后会重新进入刚走完的孩子。恢复槽号也有实际成本；没有这一接口时，不能直接援引无栈版本的空间/时间账本。

直觉

正向父函数负责把任意答案逐步归拢到同一个标准答案；枚举时沿这些步骤反着走。每个新对象都能自证“我的父亲恰是当前对象”，其他邻居虽合法，也不从这条边进入。

这里的根未必是某个目标函数的最优解，只须所有父链都能到它。可以人为设计一个非负整数势，每次向父亲走都严格下降，借此证明终止；这个势也不必等于用户关心的成本。

因此反向搜索与k优解排名有不同目标。它可以边发现边输出、避免存下全部历史，却不会仅凭父树结构保证输出费用非降。

例子与边界

给生成树指定一个父亲

给定非空有限简单无向图G，先找一棵固定生成树 $T_0$ ；若不连通，则没有生成树，直接结束。本页与下载接口把输入边表的位置0至m−1作为内部边ID，树的边表按此编号排序。若原输入另有任意整数标识，在线性读入时保留“内部位置→原标识”表，输出时逐边还原；父函数中的最小、最大及下文槽号均使用内部编号，不要求外部标识连续。对另一棵生成树T，作以下确定交换：

取 $e=\min(T_0\setminus T)$
把e加入T，形成唯一圈C
取 $f=\max(C\cap(T\setminus T_0))$ ，返回 $T+e-f$

第三步必有候选。若圈上除e外的边全属于 $T_0$ ，则整个圈都在 $T_0$ 内，与 $T_0$ 是树矛盾。删去圈边f后仍连通、无圈，所以父亲仍是一棵生成树。

每次父交换加入一条根树边，删去一条非根树边，因此

\Phi(T)=|T_0\setminus T|

恰下降一。势降到零当且仅当T等于 $T_0$ ；父链长度至多n−1。这既证明全部生成树最终到同一根，也给出本例的搜索深度界。

四点五边的八棵树

无向边ID为0:ab、1:bc、2:cd、3:da、4:ac，根树取 $T_0=\{0,1,2\}$ 。例如 $T=\{1,3,4\}$ 缺根边0；加入ab后，唯一圈使用0、1、4，非根边只有4，故父亲为 $\{0,1,3\}$ 。再向父亲走，加入根边2、删非根边3，回到根树。

完整父关系为：根012的孩子是123、023、013、124、024；013的孩子是134、034。这里012只是边集{0,1,2}的简写，不是一个十进制边ID。

按下载程序的邻居槽顺序，输出为

012,\ 123,\ 023,\ 013,\ 134,\ 034,\ 124,\ 024.

每项恰含三条边、连接全部四点且无圈。若令边权依次为1、2、3、4、5，前三项成本是6、9、8，已经说明它没有按成本排名。

图中箭头表示孩子到父亲的确定交换，实际枚举沿相反方向遍历。013是当前分支；每步父交换使缺失根边数减少一。

邻居槽与回退位置怎样恢复

把当前树的n−1条边按ID排序，槽j分解为

e=\lfloor j/(n-1)\rfloor,\qquad i=j\bmod(n-1).

它尝试加入原图边e，删除当前排序树中的第i条边f。若e已经在树中，或f不在加入e产生的圈上，槽为空；否则返回 $T+e-f$ 。总槽数为 $D=m(n-1)$ ，每个合法交换邻居出现一次。换边的逆操作仍是合法换边，所以父点确实能通过自己的邻居槽枚举到每个孩子。

从父树T进入孩子U后，回退时重新算T=f(U)。唯一新增边为 $e\in U\setminus T$ ，唯一被删边为 $f\in T\setminus U$ ；在T的排序边表中找到f的位置i，便恢复原槽 $e(n-1)+i$ 。例如012进入123，加入3、删除0，槽号是9；回退后从10继续。

n=1时，唯一生成树为空边集，D=0，先输出空树再结束，不执行除以n−1。零顶点图按旧生成树合同没有生成树，输出空；这与单顶点的一份空边集答案不同。

推论与应用

完备性与不重复的完整证据

每棵生成树都有有限父链到 $T_0$ ，所以都处在同一父树上。沿任意目标T的父链倒序看，从根到它的每一步都是某个合法换边邻居，且孩子的父函数返回当前树；完整扫描邻居槽不会错过这一步。因此目标必被访问。

一个非根对象只有一个父亲，邻居接口又不给同一个邻居重复槽，所以它只有一次被进入的机会。回退时恢复到刚处理槽的后一位置，每个对象的每个槽也只处理一次。由此无需保存已输出树集合，就能同时证明不漏与不重。

下载核验器会把小图的全部结果存下来与独立子集枚举比较；那份集合只属于测试器，不是枚举生成器的工作区。算法本体通过yield输出，调用者若另存全部答案，应把那份存储单列。

朴素实现也要准确收费

先用DFS求根树，时间和存储为O(n+m)。一次候选换边可在当前n−1条树边上重建邻接表、找唯一路径并判断删边，花O(n)；父函数也只需找缺失根边、找圈和选最大非根边，花O(n)。边ID有序表用线性归并找单边差、插入和删除，回退槽恢复也是O(n)。

设共有N棵生成树，每树D个槽恰检查一次，每个非根树恰回退一次，加上每份n−1条边的输出，保守总时间为

O\bigl(n+m+N(n+mn^2)\bigr).

这是容易核验的朴素界，不是生成树枚举的最优界。代码不实现原论文的优化交换表，也不借其他高级结构宣称每棵树仅花常数或线性时间。

当前树、根树、原图、一次路径搜索的数组与单个游标合计O(n+m)个机器字，且不随N增长。若用递归并在每层复制整棵树，则深度O(n)会带来O(n²)额外空间；“无已见集合”本身并不能排除这份栈成本。

在任意相邻输出之间，最多回退n−1层，再找到下一个孩子；每层至多扫描D个剩余槽。因此预处理后的间隔和收尾有保守多项式界 $O(n^2+mn^3)$ ；首项或空解集确认由初始连通搜索支付。一般反向搜索若父树高度无多项式界，这份延迟结论就不能直接迁移，尽管总时间仍可能与输出数量成正比。

以上按边ID、顶点下标、计数器和数组访问的单位成本RAM计；输入图已满足简单图合同。下载程序另外检查非法端点、自环和重复无向边；这些输入校验不会改变算法输出含义。

父函数错误会怎样

若让两棵不同树互为父亲，它们形成环，不会从根的反向遍历中出现。若允许父函数随调用随机改变，同一个对象可能被不同父亲接纳，多次输出或漏掉；若邻居槽重复列出同一孩子，即使父函数正确也会重复进入。

把父函数定义为“走向某个局部最优”，还要处理多个终点。可以扩成根森林并逐根遍历，但必须无重复列全根；只从其中一个根出发会漏掉其他分量。本页固定 $T_0$ ，用交集势明确避开了这个问题。

单元终结任务：交付四类枚举证书

用Lawler分区列出四物品选二的六向量成本 $3,4,5,5,6,7$ ，附1010的四个首次差异前缀及无解分支；解释为什么不能只翻一位
在Yen四点图上交出五条简单路径，费用 $3,4,4,5,6$ ；指出删根上旧顶点与禁同根下一弧分别保护什么
用Eppstein偏离表示交出前十二条游走费用 $3,4,4,5,5,6,6,6,7,7,7,8$ ，并解码(4,5)与(7)；再加入零权环，说明无限同价与有限k的区别
列出本页八棵生成树及每棵非根的父交换，实算123回到012后的槽号10。说明为什么这份清单完整无重复，却不是权重排名

最后按四个维度比较：输出身份、顺序保证、长期保留的数据、显式答案总长度。可以把后续应用换成排列或多面体顶点，但必须重新给出父函数、邻居完整性、有限到根证明和接口成本，不能只写一句“使用反向搜索”。

完整标准库程序与JSON结果提供可复算证据；检查均使用显式异常，在普通Python与-O模式下仍执行。有限测试用于找实现错误，上面的父树证明才覆盖任意合法规模。

参考资料

[1] David Avis and Komei Fukuda, Reverse Search for Enumeration,Discrete Applied Mathematics65(1–3),1996,21–46。§2、Property2.1给父森林，Theorem2.4单列逆邻居槽恢复成本；§3.6的基交换父函数及生成树应用。本文实现直接找树路径，未采用论文优化交换表的成本。
David Avis，Reverse Search: Origins，作者对构造来源的说明。算法、复杂度及论文卷号以原论文正文为准；本文八树、槽号例和间隔粗界独立展开。

形式陈述 ​

唯一父亲与有限到根 ​

为什么不需要保存已见集合 ​

给生成树指定一个父亲 ​

四点五边的八棵树 ​

邻居槽与回退位置怎样恢复 ​

完备性与不重复的完整证据 ​

朴素实现也要准确收费 ​

父函数错误会怎样 ​

单元终结任务：交付四类枚举证书 ​

反向链接