Lawler的k优解枚举 | Codeboy's Blog

找到一个最低成本方案以后，第二个方案不一定只改一个选择。若把第一份答案的每个坐标分别反过来求解，子问题又可能相互重叠，同一个方案会反复出现。Lawler方法保留这个“重新求最优”的想法，但用首次不同的位置划出互不相交的区域。

形式陈述

输入是一族有限解和受限最优化器

设可行解集 $F\subseteq\{0,1\}^p$ ，成本 $c:F\to\mathbb R$ ，请求数 $k\ge0$ 。本页输出成本非降的前 $\min\{k,|F|\}$ 个不同向量；同成本的不同向量分别占一项，平局次序任意。依据枚举接口，若可行解不足k个，要明确终止，不能复制最后一项凑数。

对前缀 $a\in\{0,1\}^r$ ，记

F(a)=\{x\in F:x_0\cdots x_{r-1}=a\}.

假设有精确子程序 Opt(a)：若 $F(a)$ 为空则报告无解，否则返回其中一个成本最小的完整向量及其成本。Opt须支持本算法产生的所有前缀条件。只有原问题的一个最优解算法，而不能处理受限子问题，并不足以运行此方法。[1][2]

删除一个最优解后的互斥划分

设Opt(a)返回x，a长r。对每个 $j=r,\ldots,p-1$ ，建立前缀

a^{(j)}=(x_0,\ldots,x_{j-1},1-x_j).

则有不交并

F(a)\setminus\{x\}=\bigsqcup_{j=r}^{p-1}F(a^{(j)}).

每个新前缀仍以a开头；它先与x一致，到j才第一次不同。空子问题丢弃，非空子问题各求一个最优解，连同前缀放入最小优先队列，键为该解的成本。

先对空前缀调用Opt。此后反复取出队列中成本最小的子问题，输出它的最优向量，再用上式划分它的剩余解。队列必须跨轮保留其他子问题，不能每输出一项便把未选区域清空。

可执行的核心

下面的oracle返回 (cost, full_tuple) 或None。serial只是平局时的稳定编号，不参与数学成本，也不要求比较整条答案。

python

from heapq import heappush, heappop

def lawler_enumerate(p, opt, k):
    if k == 0:
        return
    best = opt(())
    if best is None:
        return
    heap = [(best[0], 0, (), best[1])]
    serial, produced = 1, 0
    while heap and produced < k:
        cost, _, prefix, x = heappop(heap)
        yield cost, x
        produced += 1
        if produced == k:
            return
        for j in range(len(prefix), p):
            child = x[:j] + (1 - x[j],)
            answer = opt(child)
            if answer is not None:
                heappush(heap, (answer[0], serial, child, answer[1]))
                serial += 1

输入需满足非负整数p、k和oracle合同。完整下载程序另检查参数；有限精确成本的比较是计费模型的一部分。

直觉

队列里每个候选不是“一条可能不错的答案”，而是一整片尚未输出区域的最好代表。只看这些代表便能找到全局下一名：如果某片区域藏着更便宜的解，它的最优代表也必然至少同样便宜。

输出代表后，这片区域还不能整体扔掉。首次差异划分把余下方案交给若干孩子，每个方案恰有一个负责它的孩子。于是队列始终同时承担两项责任：区域覆盖保证不漏，区域互斥保证不重。

这与按0/1逐层深搜的顺序不同。新子问题可能一次固定很多位，而且每个节点都保存一个完整最优解；排名来自子问题最优成本，而不是前缀长度或当前已选物品的成本。

例子与边界

四件物品恰好选两件

物品成本依次为 $(1,3,2,4)$ ，向量的一表示选中，约束为恰好两个一。最优解是1010，成本三。首次划分如下：

首次不同位置j	新前缀	最优完成	成本
0	0	0110	5
1	11	1100	4
2	100	1001	5
3	1011	无解	—

取出成本四的1100时，前缀11已经用满两个名额；其余两个孩子111和1101都不可行。原来前缀0和100的两个成本五候选仍留在队列里，不能因本轮没有新孩子而误报结束。

全部六个答案的成本为 $3,4,5,5,6,7$ ；对应向量是1010、1100、1001/0110、0011、0101，其中成本五两项可交换先后。Opt在这个例子中不难：数出前缀已选数量，再从剩余物品里补足最便宜的若干件；已超额或剩余数量不够便无解。

四物品选二实例的首次差异分区。已输出向量不属于任何子问题；队列比较各份最优值，而不比较前缀长短。

为什么只“翻一位”会重复

若分别取“与x在第0位不同”和“与x在第1位不同”两个区域，却不限制更早位置，那么同时改变这两位的方案属于两边。保存所有已见答案能补救部分重复，却改变空间和成本；本方法直接在区域定义中消除重叠。

反过来，若把“首次不同”误写成“只有这一位不同”，又会漏掉需要同时改变多个坐标的可行解。恰好选两件的例子中，两个不同选择至少要取消一件、加入另一件，仅翻一位根本不满足约束。

空解集、零维与oracle错误

k=0时不必调用Opt。p=0时宇宙含唯一空向量：若它可行，就输出这一个零长度记录并结束，没有孩子；若不可行，输出为空。这两种情形不能混为一谈。

若Opt只返回一个可行解而非最优解，队列键便不再代表区域下界，非降序保证失效。若Opt在某个非空前缀上误报无解，整个区域都会消失。Lawler框架不会修复子程序的近似误差或漏解。

推论与应用

正确性由一个队列不变量串起

初始化时，唯一活动区域F(空前缀)正好是全部可行解。假设每轮前队列的区域两两不交，且其并集恰为尚未输出的解；每个键都是对应区域的真实最小成本。

取出最小键的代表x。任意未输出y都在某个活动区域中，该区域代表成本不大于c(y)，而x又不贵于这个代表，所以 $c(x)\le c(y)$ 。x确为下一名。划分恒等式将其原区域准确替换成原区域去掉x，且不改变其他区域。因此不变量继续成立，x也不会在以后再次出现。

首次差异恒等式本身有直接证明：对任意 $y\ne x$ ，取它们在尚未固定坐标中的第一个差异j；y满足且只满足相应前缀。不同j的区域不可能相交，因为较早的区域要求该位异于x，较晚的区域却要求该位等于x。

oracle调用不等于全部运行时间

设每次受限最优化最多花T时间，用S工作空间，完整向量有p位。输出q项期间，初次调用加每项至多p个孩子，调用数不超过 $1+qp$ 。这是最重要的通用账本，但不能将T直接当常数。

显式复制每个前缀及完整见证需要O(p)时间和空间。用二叉堆管理至多 $1+qp$ 个候选，成本比较与编号按单位成本计，本页实现的保守总时间为

O\bigl((1+qp)T+qp^2+qp\log(qp+2)+1\bigr),

外层工作空间为 $O((1+qp)(p+1))$ ，再加一次oracle所需S。输出本身的qp位也已计入。若成本或计数器是多字整数，须另计其算术和比较；Python字典、共享前缀或持久化表示可以改变具体账本，但不能仅凭算法名称省去复制成本。

q取实际输出数量；若刚好在第k项后停止，不必再划分最后一项。若必须确认已耗尽，则仍要完成剩余子问题的无解检查。随着输出增长的候选队列说明此方法没有自动获得“工作空间只依赖原输入”的保证。

从位向量移到路径

Yen算法把“首次不同”落实到路径根前缀与下一条边，但还必须防止后缀走回根上的旧顶点。反向搜索采用另一种组织方式：给每个完整解一个唯一父亲，再遍历这棵隐式树；它可避免随答案数增长的已见集合，却不默认按成本排名。

手算终点：写出1010的四个区域，指出哪个为空；再选择前缀0中的最优0110，继续划分并找出0011和0101归属哪个孩子。最后把oracle换成一般0–1整数规划，说明调用数仍成立，而单次受限求解可能很难。

参考资料

[1] Eugene L. Lawler, “A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem”, Management Science18(7),1972,401–405，DOI：通用k优解分区方法。原文元数据及摘要可核；本页未借其精细空间改进替代显式实现账本。
[2] David Eppstein, k-best enumeration,2014，§2.3“Solution-Space Partitions”：首次差异的多路互斥子问题。本文二进制前缀版本、六解例与完整不变量证明独立展开。

形式陈述 ​

输入是一族有限解和受限最优化器 ​

删除一个最优解后的互斥划分 ​

可执行的核心 ​

四件物品恰好选两件 ​

为什么只“翻一位”会重复 ​

空解集、零维与oracle错误 ​

正确性由一个队列不变量串起 ​

oracle调用不等于全部运行时间 ​

从位向量移到路径 ​

反向链接