Minecraft 合成规划算法

1 简介

我们正在基于 Minecraft 中的所有配方进行合成规划。合成规划是指，给定要合成的单个物品以及合成它的数量，找出每个配方需要使用多少次。合成可能不止一种方式，而我们想要总合成步数最少的那一个。自然，在游戏中玩家其实注意不到最优，所以较优的可行解也是能接受的。

这里“步数”指的是底层 Minecraft 配方真正被执行的次数，而不是规划器里配方列的个数。一个普通配方执行一次就是一步；tag 边（合成 tag 的那个合成配方）不计步数，因为选哪个成员来填充 tag 在游戏里是免费的；而Section 1.2一节提到的概率配方则是被批量折叠起来的，每一个代表 $𝑐_{𝑟}$ 次真实执行，也就需要 $𝑐_{𝑟}$ 步。所以每条配方 $𝑟$ 都有一个成本 $𝑐_{𝑟}$ ，而目标是最小化 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟}$ 。

传统的规划方法完全失效。AE2 认为配方是一棵树，在这棵树上进行深度优先搜索。它的各类优化模组认为配方是一个 DAG，并在图上利用图论算法传播信息。然而，下文会告诉我们巨型 SCC 是不可避免的。

一部分求解器会选择将 SCC 切断成 DAG。这不保证最优性，所以自然也是不完备的，但它非常快速。所以我们采用的方法是，先通过预处理剪枝，再用一次 Section 3 的贪心 DAG 预扫描快速给出一个可行解，最后才交给 CP-SAT 求解器去优化。

1.1 SCC 为什么这么大？

考虑一个随机的二分图，分为 $𝐴$ , $𝐵$ 两部分，占比分别为 $𝛼$ , $𝛽$ ( $𝛼 + 𝛽 = 1$ )。设 $𝐴$ 指向 $𝐵$ 的平均出度为 $𝑚$ ， $𝐵$ 指向 $𝐴$ 的平均出度为 $𝑛$ 。

先求解巨型出分量的概率。设从属于 $𝐴$ 或 $𝐵$ 的节点开始，能走到无穷远处的概率分别是 $𝑥_{𝐴}$ , $𝑥_{𝐵}$ ，而灭绝（也就是最终有限）的概率是 $𝑢_{𝐴}$ , $𝑢_{𝐵}$ 。既然 $𝐴$ , $𝐵$ 节点的出度符合泊松分布，那么如果 $𝑎 \in 𝐴$ 要灭绝，它的每一个 $𝐵$ 邻居都必须灭绝，所以

𝑢_{𝐴} = \sum_{𝑖 = 0}^{\infty} 𝑒^{- 𝑚} \frac{𝑚^{𝑖}}{𝑖!} 𝑢_{𝐵}^{𝑖}

其中 $𝑒^{- 𝑚} \frac{𝑚^{𝑖}}{𝑖!}$ 正是泊松分布中 $𝑎$ 有 $𝑖$ 个邻居的概率，而 $𝑢_{𝐵}^{𝑖}$ 则是邻居全部灭绝的概率。我们熟知

𝑢_{𝐴} = 𝑒^{- 𝑚} \sum_{𝑖 = 0}^{\infty} \frac{{(𝑚 𝑢_{𝐵})}^{𝑖}}{𝑖!} = 𝑒^{- 𝑚 + 𝑚 𝑢_{𝑏}}

同理， $𝑢_{𝐵} = 𝑒^{- 𝑛 + 𝑛 𝑢_{𝐴}}$ 。

对于巨型入分量的概率，原理类似，只是要注意 $𝐴$ 和 $𝐵$ 的入度现在是 $𝛽 \frac{𝑛}{𝛼}$ 和 $𝛼 \frac{𝑚}{𝛽}$ 。这说明灭绝概率 $𝑣_{𝐴} = 𝑒^{- \frac{𝛽}{𝛼} 𝑛 (1 - 𝑣_{𝐵})}$ ，而 $𝑣_{𝐵} = exp (- \frac{𝛼}{𝛽} 𝑚 (1 - 𝑣_{𝐴}))$ ，自然无限概率即为 $𝑦_{𝐴} = 1 - 𝑣_{𝐴}, 𝑦_{𝐵} = 1 - 𝑣_{𝐵}$ 。

那么 $𝐴$ 中节点落在 SCC 中的概率自然是 $𝑥_{𝐴} 𝑦_{𝐴}$ ，有 $𝛼$ 的部分属于 $𝐴$ 节点； $𝐵$ 中节点落在 SCC 中的概率是 $𝑥_{𝐵} 𝑦_{𝐵}$ ，有 $𝛽$ 的部分属于 $𝐵$ 节点。从而整个 SCC 的大小是 $𝛼 𝑥_{𝐴} 𝑦_{𝐴} + 𝛽 𝑥_{𝐵} 𝑦_{𝐵}$ 。

现在我们从物品出发，检查其反向可达的子图，那么可达的概率应当是入分量的概率。所以在这个子图中，SCC 的占比是

\frac{𝛼 𝑥_{𝐴} 𝑦_{𝐴} + 𝛽 𝑥_{𝐵} 𝑦_{𝐵}}{𝛼 𝑦_{𝐴} + 𝛽 𝑦_{𝐵}}

在我们所用的数据集上，这个值大概在 75% - 80% 之间，除了原版只有 50%。在 ATM 上占比实测为 14%，然而我也不知道为什么这么小。

1.2 概率配方

在求解器内部，我们并不处理概率配方。所以，这里描述的是从 Minecraft 中的实际配方编码为 AW 配方的过程，不归 JNI 管。

首先，概率是小数，所以我们当然要放大成整数，而且可以逐级放大：乘以 1, 4, 16, … 之类的，当做一个四进制数来凑出最终的需求量。这个底数 $𝑚 = 4$ 是可以调整的。接下来就是具体如何放大了。

假设原始配方以 $𝑝$ 的概率产出 1 个物品，而放大 $𝑖$ 级的配方应该产出 $𝑛$ 个物品。我们希望以 $𝑐 = 90 %$ 的概率保证这条配方在实际执行时可以产出至少 $𝑛$ 个，并将 $𝑐$ 称作置信度。从而

𝑃 (𝑥 < 𝑛) < 𝜀 = 1 - 𝑐

这里的 $𝜀$ 就是容错。然而，这是给全体放大配方一起执行的容错，而分到每个配方头上的自然要少一些。假设分到 $𝑖$ 级配方的是 $𝑚_{𝑖}$ ，而一共有 $𝑘$ 级，它们的输出是独立的。那么最坏的情况就是所有的配方都会执行 $𝑚 - 1$ 次，所以必须满足

\prod {(1 - 𝜀_{𝑖})}^{𝑚 - 1} \leq 𝜀

我们知道最高级配方可能执行不止 $𝑚 - 1$ 次，但这也没有什么办法，所以选择妥协。更何况最高级配方批量已经足够大，可以稳定在期望附近，一般不会出太大问题的。

至于 $𝜀_{𝑖}$ 的分配方式，我们希望最小化总的相对误差。

我们要在执行 $𝑛$ 次的情况下以置信度 $𝑐$ 产出 $𝑑$ 个物品，也就是 $𝑃 (𝑥 < 𝑑) < 𝑐$ ，这时绝对误差是 $𝑛 𝑝 - 𝑑$ ，而相对误差则是 $𝑅 = \frac{𝑛 𝑝 - 𝑑}{𝑛}$ 。我们高中就学过，在 $𝑛 𝑝$ 足够大时，二项分布近似于正态分布 $𝑁 (𝑛 𝑝, 𝑛 𝑝 (1 - 𝑝))$ 。设标准正态分布的概率密度函数为 $Φ$ ，自然有

Φ (\frac{𝑑 - 𝑛 𝑝}{\sqrt{𝑛 𝑝 (1 - 𝑝)}}) < 1 - 𝑐

考虑到 $Φ (𝑥) + Φ (- 𝑥) = 1$ ，可以解出

𝑑 \leq 𝑛 𝑝 - Φ^{- 1} (𝑐) \sqrt{𝑛 𝑝 (1 - 𝑝)}

不妨将 $Φ^{- 1} (𝑐)$ 记作常数 $𝑧$ ，那么我们有

{(𝑛 𝑝 - 𝑑)}^{2} \geq 𝑧^{2} 𝑝 (1 - 𝑝) 𝑛

也就是

𝑝^{2} 𝑛^{2} - (2 𝑝 𝑑 + 𝑧^{2} 𝑝 (1 - 𝑝)) 𝑛 + 𝑑^{2} \geq 0

考虑到 $𝑛 > 𝑑$ ，自然有

𝑛 \geq \frac{2 𝑑 + 𝑧^{2} (1 - 𝑝) + \sqrt{𝑧^{2} (1 - 𝑝) (4 𝑑 + 𝑧^{2} (1 - 𝑝))}}{2 𝑝}

在零附近的泰勒展开告诉我们， $\sqrt{1 + 𝑎} = 1 + \frac{𝑎}{2} - \frac{𝑎^{2}}{8} + \dots$ 。现在 $𝑑$ 很大，所以 $𝑧^{2} \frac{1 - 𝑝}{𝑑}$ 应当足够小。那么

\sqrt{4 𝑑 (1 - 𝑝) + 𝑧^{2} {(1 - 𝑝)}^{2}} = \sqrt{4 𝑑 (1 - 𝑝)} (1 + \frac{𝑧^{2} {(1 - 𝑝)}^{2}}{8 𝑑 (1 - 𝑝)} + 𝑂 (𝑑^{- 2}))

接下来再将外面的根号乘进去，化简，就可以得到

𝑛 𝑝 \geq 𝑑 + \frac{𝑧^{2} (1 - 𝑝)}{2} + 𝑧 \sqrt{𝑑 (1 - 𝑝)} + \frac{𝑧^{3} {(1 - 𝑝)}^{\frac{3}{2}}}{8 \sqrt{𝑑}}

所以，相对误差 $𝑅$ 其实是 $𝑧 \frac{\sqrt{𝑑 (1 - 𝑝)}}{𝑛} + 𝐶 + 𝑂 (𝑛^{- 1} 𝑑^{- \frac{1}{2}})$ ，其中 $𝐶 = \frac{𝑧^{2} (1 - 𝑝)}{2}$ ，是个常数，跟我们最小化的目标无关。我们忽略小量，并且认为 $𝑑 \sim 𝑛 𝑝$ ，那么 $𝑅 \sim 𝑧 \sqrt{\frac{𝑝 (1 - 𝑝)}{𝑛}}$ 。具体忽略了多少其实我也懒得算了，就先这样吧，恐怕有个 $𝑂 (𝑛^{- \frac{1}{2}})$ ？但是大概问题不大（不大在哪，这玩意也是 $𝑂 (𝑛^{- \frac{1}{2}})$ 的）。

总之，接下来就是拉格朗日乘数法了。我们的约束是

\prod_{𝑖} {(1 - 𝜀_{𝑖})}^{𝑚 - 1} = 𝜀

需要最小化 $\sum_{𝑖} 𝑅_{𝑖}$ 。

那么我们自然直接求导。这里 $𝑝$ 和 $𝑛$ 都和 $𝜀_{𝑖}$ 没有关系，但 $𝑧 = Φ^{- 1} (𝑐) = 1 - Φ^{- 1} (𝜀)$ 。这时 $\frac{𝑑 𝑧}{𝑑 𝜀} = - \frac{1}{𝜀}$ 。

\frac{𝜕 𝑅_{𝑖}}{𝜕 𝜀_{𝑖}} = - \frac{1}{𝜀_{𝑖}} \sqrt{\frac{𝑝 (1 - 𝑝)}{𝑛}}

而不同层级的 $𝑧$ 之间没有关系，所以 $\sum_{𝑖} 𝑅_{𝑖}$ 求导之后只剩这一项。从而 $𝜀_{𝑖}$ 应当正比于 $𝑛^{- \frac{1}{2}}$ 。这样就好了，最后归一化就完了。

2 基于支配的剪枝

2.1 Tag 剪枝

2.1.1 合成图

合成图是一个二分图。物品只能指向配方，而配方只能指向物品。

它还是一个 AND-OR 图，同时配方指向物品的边是超边（AND 边）：我们熟悉的边（OR 边）是任选一条边即可，而这里的超边则需要同时走完所有边。

2.1.2 支配

我们考虑这样的一个例子：假设我们要合成钢制机壳，它需要 4 个任意种类的玻璃。我们知道 Minecraft 中有 16 种染色玻璃，它们通过普通玻璃和染料合成。注意到在合成任何一种染色玻璃时，我们都需要经过普通玻璃，所以普通玻璃支配了所有的合成路径。这时，额外花费物品去合成染色玻璃自然是不划算的。

在编译原理中，我们熟知计算支配关系的算法。然而，那个算法没法直接用在这里，因为它只能处理普通的图，而这是一个 AND-OR 图。

所以，我们接下来就需要根据我们的使用场景，找出计算支配关系的算法，然后基于它进行剪枝。

我们的直觉可能会 $𝑤$ 支配 $𝑚$ 定义为：合成 $𝑚$ 时，一定绕不开 $𝑤$ 。然而，这样其实还不够：假设 $8 𝑚 \leftarrow 𝑤$ 是 $𝑚$ 唯一的合成方式。这时，合成 $𝑚$ 时确实一定绕不开 $𝑤$ ，但这能说明我们不需要 $𝑚$ 、直接用 $𝑤$ 了吗？其实是不可以的，因为如果有一个配方中 $𝑚$ , $𝑤$ 可以互换，那么显然用 $𝑚$ 更赚。

所以，我们给出支配的定义。这两种情况都算作 $𝑤$ 支配 $𝑚$ ：

合成 $𝑚$ 的任何一种方法，至少会消耗等量的 $𝑤$ 。
合成 $𝑚$ 的任何一种方法，至少会消耗等量的某个 tag，而其中所有不是 $𝑤$ 的资源都支配 $𝑤$ 。

我们将这个关系记作 $dominate (𝑚, 𝑤)$ 。

2.1.3 支配关系的计算

最直接的计算方式是直接遍历所有的 $(𝑚, 𝑤)$ ，然后根据定义判断。这肯定很慢，所以为了加速，我们只想收集有用的 $(𝑚, 𝑤)$ ，排除一些明显不可能支配 $𝑚$ 的 $𝑤$ 。

具体怎么算有用呢？对于一个物品 $𝑚$ 与合成 $𝑎$ 个它的配方 $𝑟$ 而言，如果 $𝑟$ 中含有至少 $𝑎$ 个 $𝑤$ 作为输入，那么 $𝑤$ 确实有可能支配 $𝑚$ ，这时 $(𝑚, 𝑤)$ 是有用的。如果 $𝑟$ 中含有的不是某个具体的资源，而是一个 tag $𝐽$ ，那么 $𝐽$ 的每一种资源都可以当做上述的 $𝑤$ ，这时所有的 $(𝑚, 𝑤)$ 都是有用的。我们将这个集合称作 $witness (𝑟)$ .

接下来，将 $𝑚$ 所有配方 $𝑟$ 的 $witness (𝑟)$ 取交集，得到的结果称作 $𝑐_{1} (𝑚)$ 。这里取交集是因为根据定义，每一个配方都必须用到 $𝑤$ 。

有了所有的 $(𝑚, 𝑤)$ ，我们又该如何精确判断 $𝑤$ 是否支配 $𝑚$ 呢？

我们的想法是，首先假设所有的 $(𝑚, 𝑤)$ 都满足 $dominate (𝑚, 𝑤)$ ，然后逐渐删除明显不正确的那些。我们将算法过程中逐渐缩小的这个关系称作 $alive (𝑚, 𝑤)$ ，在结束时它应当收敛于 $dominate (𝑚, 𝑤)$ 。由于 $dominate$ 的定义是递归的，不动点迭代是常规方法。

我们不妨将支配定义的条件记作 $valid (𝑚, 𝑤)$ ，展开写就是

\forall 𝑟 \in recipes (𝑚) . \exists (𝑗, 𝑎) \in input (𝑟) . \underset{条件 1}{\underset{⏟}{𝑗 = 𝑤}} \lor \underset{条件 2}{\underset{⏟}{isTag (𝑗) \land \forall 𝑧 \in 𝑀 (𝑗) . alive (𝑧, 𝑤)}}

注意第二个条件并不要求 $𝑤 \in 𝑀 (𝑗)$ ，这指的正是 $𝑗$ 这个 tag 的每一个成员都绕不开 $𝑤$ 。

注意到，这和 $dominate$ 的定义是一样的，只是将递归检测 $dominate$ 的部分改换为了检测 $alive$ 。下面的代码实现中我们将用到这个辅助函数。

在删除 $valid (𝑚, 𝑤)$ 不成立的节点时，一些节点可能受到影响，不再成立。对于普通的资源倒还好说，但如果遇到的是 tag 就比较麻烦了。将 tag 记作 $𝐽$ ，它的成员记作 $𝑀$ ，其中 $𝑤 = 𝑀 [𝑖]$ 是 $𝑀$ 中的第 $𝑖$ 个资源。根据定义，如果 $𝑀$ 里除了 $𝑤$ 以外，使得 $dominate (𝑧, 𝑤)$ 成立的 $𝑧$ 数量恰好是 $| 𝑀 | - 1$ ，那么 $𝑤$ 就支配 $𝑚$ 。我们不妨将这个数量称作 $cnt (𝐽, 𝑖)$ 。当且仅当 $cnt (𝐽, 𝑖)$ 从 $| 𝑀 | - 1$ 掉到 $| 𝑀 | - 2$ 的时候， $alive (𝑚, 𝑤)$ 从成立变为不成立，才会产生影响。这就是维护 $cnt$ 的作用。

我们维护一个 worklist，来将 $alive$ 迭代至不动点：

for (m, w) in universe:
  worklist.push(m, w)

# 不断删除不可能的节点
while not empty(worklist):
  m, w = worklist.pop()
  if alive(m, w) and not valid(m, w):
    kill(m, w)

def kill(m, w):
  dominate(m, w) = 0
  for (J: tag) in tagsOf(m).intersect(tagsOf(w)):
    M = members(J)
    i = lowerBound(M, w)
    cnt(J, i) -= 1
    if cnt(J, i) + 1 == len(M) - 1:
      for m2 in consumers(J):
        push(m2, w) # may not exist; skip if absent

2.1.4 传递闭包

上面的 $valid$ 还有一个递归没有展开：第一个条件只接受 $𝑗 = 𝑤$ ，但如果 $𝑗$ 自己也被 $𝑤$ 支配，那么合成 $𝑚$ 同样绕不开 $𝑤$ 。补上这一条后， $valid$ 就是 $dominate$ 的传递闭包：

valid (𝑚, 𝑤) = \forall 𝑟 \in recipes (𝑚) . \exists (𝑗, 𝑎) \in input (𝑟) . 𝑗 = 𝑤 \lor alive (𝑗, 𝑤) \lor (isTag (𝑗) \land \forall 𝑧 \in 𝑀 (𝑗) . alive (𝑧, 𝑤))

实现上，tag 那一条是 $alive (𝑗, 𝑤)$ 在 tag 上的特例，所以把 $(𝑚, 𝑤)$ 与 $(𝑗, 𝑤)$ 放进同一个不动点：前者是配方上的 OR，后者是其成员上的 AND。kill 的传播也由维护 $cnt$ 改为维护这两个队列。

这两个放宽都会破坏最优性： $𝑗$ 链条可能靠批量余料绕过 $𝑤$ ，tag 那条则可能剪掉整数规划真正需要的边。所以它们不会在最优模式下启用。这样一来，关系不再是精确的 $dominate$ ，而只是它的一个上近似。

2.1.5 关系索引

不动点把所有的 $(𝑥, 𝑤)$ 混在一个 worklist 里，但它们之间其实有一个很强的结构：上面每一步传播都只改变 $𝑥$ ，而 $𝑤$ 始终不变。 $valid$ 里查的 $(𝑗, 𝑤)$ 、tag 的 $(𝑧, 𝑤)$ 、kill 里通知消费者的 $(𝑚_{2}, 𝑤)$ ，用的都是同一个 $𝑤$ 。所以，我们可以遍历 $𝑤$ ，并且对每个 $𝑤$ 生成需要的 $𝑚$ 与 $𝑧$ 。

Section 2.1.7 的 SCC 阶段是唯一需要跨行信息的步骤，我们只要存储 $𝑚$ 即可。

2.1.6 列支配

支配定义里的 $𝑤$ 必须出现在 $𝑚$ 的每一个配方里。除此之外，还有一类更简单的情况：只要 $𝑠$ 的产出不少于 $𝑟$ ，每种输入都不多于 $𝑟$ ，且 $𝑐_{𝑠} \leq 𝑐_{𝑟}$ ，那么 $𝑚$ 的某条配方 $𝑟$ 可以被 $𝑤$ 的某条配方 $𝑠$ 直接替换。实现上，在 $valid$ 里把 $𝑟$ 记为已满足即可。

值得注意的是，只有 $𝑚$ 的配方一次只产出一个 $𝑚$ 时，逐次替换才能把 $𝑇 \leftarrow 𝑚$ 换成 $𝑇 \leftarrow 𝑤$ 而不增加总步数。如果 $𝑚$ 产出了不止一个，那么对其他消耗者来说，剩下的部分相当于是免费的，这时如果删掉 tag，就得拿更多的 $𝑤$ 去补。所以在最优模式下，只有当 $𝑚$ 的每一条配方产出都恰好为 1 时，才允许剪掉 $𝑇 \leftarrow 𝑚$ 。

FIXME：列支配会保证收支平衡，却不保证计划可以启动。

2.1.7 剪枝

对于含有成员 $𝑀$ 的 tag $𝑇$ ，在 $𝑀$ 中对所有留下的 $alive (𝑚, 𝑤)$ 建立一条边 $𝑚 \to 𝑤$ 。注意这可能成环，所以我们需要先缩点：计算强连通分量（SCC），然后在所有出度为 0 的 SCC 中挑选一个代表元。这时，其他的所有标签都可以到达这个代表元，只要产出恰好为 1，就可以将它们替换。

2.2 配方剪枝

前面的 tag 剪枝只会删去人工添加的 tag 边。同样的想法自然也可以推广到真实存在的配方。

2.2.1 动机

考虑下面这组配方：

黑色蜡烛 x1 <- 黑染料 x1，蜡烛 x1
黑色蜡烛 x1 <- 黑颜料 x256，蜡烛 x1
黑颜料 x256 <- 黑染料 x1
黑颜料 x224 <- 黑色蜡烛 x1

如果你熟悉通用机械，这里的黑颜料就是来自它，由颜料提取机产出。不过与 tag 剪枝不同，这里的支配只是消耗量的比较： $𝑅$ 和 $𝑆$ 完全可能使用不同的机器。若玩家只有 $𝑅$ 的机器而没有 $𝑆$ 的，删去 $𝑅$ 就丢掉了合成 $𝑋$ 的唯一途径，所以机器在这里不能忽略。

注意区分黑颜料 (mek 模组) 和黑染料 (原版 MC)。

在合成黑颜料时，如果玩家没有黑蜡烛的存货，那么通过合成黑蜡烛来合成黑颜料的方式永远不划算：黑蜡烛要么由黑染料合成，那还不如直接把黑染料变成 256 个黑颜料；要么由黑颜料合成，但那净亏 32 个黑颜料。所以它可以被删掉。

注意 $dominate (黑染料, 黑蜡烛)$ 并不成立，因为合成黑蜡烛并不是总需要黑染料的，还可以通过黑颜料合成。所以，为了删除配方 $𝑟 : 𝑋 \leftarrow 𝑌$ ，我们需要把 $𝑌$ 的生产配方内联进 $𝑟$ 之后，再和其他的配方比较。

2.2.2 定义

考虑配方 $𝑟 : 𝑝_{𝑟} \times 𝑜 \leftarrow 𝑞_{1} \times 𝑖_{1}, 𝑞_{2} \times 𝑖_{2}, \dots$ ，其中 $𝑜, 𝑖_{1}, 𝑖_{2}, \dots$ 是物品，而 $𝑝, 𝑞_{1}, 𝑞_{2}, \dots$ 是固定的系数。

它可以写成一个列向量 $𝑣_{𝑟}$ ：在输出 $𝑜$ 这一行取 $𝑝$ ，在每个输入 $𝑖_{𝑛}$ 这一行取 $- 𝑞_{𝑛}$ ，其余为 0。两个向量比较时按分量进行。

设 $𝑅 : 𝑝 \times 𝑋 \leftarrow 𝑞 \times 𝑌, \dots$ 是产出 $𝑋$ 的一条配方，其中 $𝑌$ 是真实资源； $𝑆 : 𝑝_{𝑆} \times 𝑋 \leftarrow \dots$ 是 $𝑋$ 的另一条配方。对 $𝑌$ 的每一条生产配方 $𝑟$ ，令 $𝛼_{𝑟} = ⌈ \frac{𝑞}{𝑝_{𝑟}} ⌉$ ，并称

𝑐_{𝑟} = 𝛼_{𝑟} 𝑣_{𝑟} + 𝑣_{𝑅}

为把 $𝑟$ 内联进 $𝑅$ 之后的组合。若对 $𝑌$ 的每一条生产配方 $𝑟$ ，都有

𝑐_{𝑟} \leq 𝑣_{𝑆} \lor 𝑐_{𝑟} \leq 0

就称 $𝑆$ 支配 $𝑅$ 。

$𝑐_{𝑟}$ 本身表示用 $𝑟$ 造出至少 $𝑞$ 个 $𝑌$ 、再用 $𝑅$ 处理掉，这一整套下来的资源变化量。如果它 $\leq 𝑣_{𝑆}$ ，那么这 $𝛼_{𝑟} + 1$ 步可以整体换成 $𝑆$ ：这只需一步，而且产出不减少、消耗不增多。而 $𝑐_{𝑟} \leq 0$ 的意思是，这是纯亏的，可以直接删掉。第二种情况只删掉执行，成本非负，所以一定不会变差；第一种情况是一次执行换 $𝛼_{𝑟} + 1$ 次执行，所以要额外要求

𝑐_{𝑆} \leq 𝛼_{𝑟} 𝑐_{𝑟} + 𝑐_{𝑅}

也就是换过去不会更贵。

除了这个消耗条件以外，还必须要让替换发生时 $𝑆$ 也能开工。每个查询都会带上可用的机器集合，所以剪枝时再检查即可；在预处理时，为每条被支配的 $𝑅$ 记下可能的替换者就行了。

2.2.3 支配关系的计算

对每个真实资源 $𝑋$ ，在它的配方集合上建一张有向图： $𝑅 \to 𝑆$ 表示 $𝑆$ 支配 $𝑅$ 。因为 $𝑅$ 与 $𝑆$ 产出同一个 $𝑋$ ，比较只需要在同一个 $𝑋$ 的配方之间进行。

判断一条边 $𝑅 \to 𝑆$ 时，依次尝试 $𝑅$ 的每个真实输入 $𝑌$ ，并对 $𝑌$ 的每条生产配方 $𝑟$ 做一次稀疏向量的分量比较。只要存在一个 $𝑌$ 使条件对所有 $𝑟$ 成立，就记下这条边，并记下这个 $𝑌$ 作为守卫。若某个 $𝑌$ 下没有合法替换，就换 $𝑅$ 的下一个输入继续尝试。注意这里不再检查机器，因为可用性已经推迟到查询时。

和 tag 剪枝一样，这些边可能成环，所以对每个 $𝑋$ 的支配子图按照 SCC 缩点，在每个出度为 0 的 SCC 中保留一个代表元即可。被删去的 $𝑅$ 可以到达若干个保留的代表元，其中任意一个都能替换它，于是预处理时为 $𝑅$ 记下这些代表元的可用机器集合的并集 $𝑊 (𝑅)$ ：只要它与玩家的机器相交，就有一个能开工的代表元可以接手。

在真正剪枝的时候，配方的支配还需要检查两件事。其一， $𝑅$ 可能正是玩家消耗存货 $𝑌$ 的途径，所以只有当 $𝑌$ 没有存货时才能真正删去 $𝑅$ ：预处理时除了标记被支配的配方，还要记下 $𝑌$ 到底是哪一个。其二，替换者必须真的能开工，也就是玩家持有的机器要与 $𝑊 (𝑅)$ 相交。只要这两条同时满足，就可以删去 $𝑅$ 。

2.2.4 一个无法剪枝的例子

考虑

黑色玻璃 x8 <- 黑染料 x1，玻璃 x8
黑色玻璃 x1 <- 黑颜料 x32，玻璃 x1
黑颜料 x256 <- 黑染料 x1
黑颜料 x16 <- 黑色玻璃 x1

第一眼看上去似乎由黑色玻璃合成黑颜料的边也可以删除，毕竟这要么纯亏，要么被黑染料支配。但这条边是不能删的，因为如果有一个什么东西需要 16 黑颜料和 7 个黑色玻璃，那么显然是使用黑染料 1 次更划算，而删掉之后就需要用两次了。这本质上是整数限制所导致的。

不在最优模式下时，我们会删除这条边。

2.3 列支配剪枝

上一篇的支配关系要先内联输入的生产配方，比较的是“走完整条子链”之后的列。除此之外，和 Section 2.1.6 类似，也有更简单的情况：如果同一物品的两条配方中，其中一条的列向量逐分量地不小于另一条，那么可以直接删去后者。

考虑产出同一物品 $𝑋$ 的两条配方：

𝑅 : 𝑝 \times 𝑋 \leftarrow 𝑞_{1} \times 𝐼_{1}, 𝑞_{2} \times 𝐼_{2}, \dots

𝑆 : 𝑝^{'} \times 𝑋 \leftarrow 𝑞_{1}^{'} \times 𝐼_{1}, 𝑞_{2}^{'} \times 𝐼_{2}, \dots

若 $𝑝^{'} \geq 𝑝$ ，对每个输入都有 $𝑞_{𝑛}^{'} \leq 𝑞_{𝑛}$ （换言之， $𝑣_{𝑆} \leq 𝑣_{𝑅}$ ），且 $𝑐_{𝑆} \leq 𝑐_{𝑅}$ ，则把任何一次 $𝑅$ 换成一次 $𝑆$ ，所有物品的收支状况都不会变差，目标也不会变大，所以最优解一定可以不用 $𝑅$ 。这不需要守卫输入：即使玩家持有某个输入，换成 $𝑆$ 也不会更差。

在实现时，可以将偏序 $𝑣_{𝑆} \geq 𝑣_{𝑅}$ 定义的范畴直接看做一个图，对它缩点后，在每个出度为 0 的 SCC 中保留一个代表元，就保留了所有极大列。

替换者可能需要 $𝑅$ 没有的机器，所以和其他剪枝一样，可用性推迟到查询时判定： $𝑅$ 只有在某个代表元的机器可用时才能真正删去。

2.4 替换剪枝

前面两次真实配方支配都要把输入 $𝑌$ 的生产配方内联进来。但有一类情况其实不用真的内联：如果合成 $𝑌$ 的任何一种方法都至少消耗等量的某个真实资源 $𝑤$ ，那么在比较列的时候，就可以把 $𝑅$ 里的一份 $𝑌$ 直接换成一份 $𝑤$ 。

2.4.1 定义

设 $𝑅 : 𝑝 \times 𝑋 \leftarrow 𝑞 \times 𝑌 + 𝑍$ ，其中 $𝑍$ 是其余输入。若每生产一个 $𝑌$ 至少要消耗一个 $𝑤$ ，令 $𝑅_{𝑤}$ 为把 $𝑅$ 中的 $𝑞 \times 𝑌$ 换成 $𝑞 \times 𝑤$ 得到的列：

𝑣_{𝑅_{𝑤}} = 𝑣_{𝑅} + 𝑞 (𝑒_{𝑌} - 𝑒_{𝑤}) .

对 $𝑌$ 的任意一组恰好产出 $𝑞$ 个 $𝑌$ 的生产配方 $𝑟$ ，每条配方产出 $𝑝_{𝑟}$ 个 $𝑌$ 就要消耗至少 $𝑝_{𝑟}$ 个 $𝑤$ ，所以 $𝑤$ 那一行不高于 $- 𝑞$ ；又因为配方只有唯一产出，其余行都不高于 $𝑅$ 。于是

\sum_{𝑟} 𝑣_{𝑟} + 𝑣_{𝑅} \leq 𝑣_{𝑅_{𝑤}} .

$𝑅$ 的每一次执行都必须消耗 $𝑞$ 个 $𝑌$ ，所以整条「生产 $𝑌$ + 执行 $𝑅$ 」的链的列都不高于 $𝑅_{𝑤}$ 。因此，若 $𝑅$ 的同门配方 $𝑆$ 满足 $𝑣_{𝑆} \geq 𝑣_{𝑅_{𝑤}}$ ，或 $𝑣_{𝑅_{𝑤}} \leq 0$ ，就可以删去 $𝑅$ 。

这本质上就是把配方剪枝里的 $𝑐_{𝑟}$ 从“内联每一个生产者”换成“用代价下界 $𝑤$ 代替”。这不需要递归展开，也不会因为生产链成环而发散。

这里同样是一次执行换一次执行，只是换掉的 $𝑌$ 改由 $𝑤$ 顶替，所以也需要 $𝑐_{𝑆} \leq 𝑐_{𝑅}$ 。

2.4.2 用哪条支配关系

这里要的是“生产 $𝑌$ 至少消耗 $𝑤$ ”的代价关系。在 tag 剪枝里，我们的确计算了看起来差不多的 $alive$ ，但实际上 $alive$ 还接受 colCover，因此不能直接复用。这是因为，colCover 说的是 $𝑌$ 的配方可以改造成 $𝑤$ 的配方，但这不等于生产 $𝑌$ 会消耗 $𝑤$ ，例如 Y x1 <- A x5 与 w x1 <- A x1 会通过 colCover 让 $𝑤$ 支配 $𝑌$ ，但 $𝑌$ 根本不消耗 $𝑤$ 。代价关系的递归形式和 $valid$ 一样：

costs (𝑌, 𝑤) = \forall 𝑟 \in recipes (𝑌) . \exists (𝑗, 𝑎) \in input (𝑟) . 𝑗 = 𝑤 \lor costs (𝑗, 𝑤),

其中被消费的 tag 取其全体成员的交。注意这和 tag 剪枝的候选集方向相反：候选集是从种子向下展开的，也就是从配方到输入；而真实输入链必须向上传递。所以实现里不是逐个查询 $(𝑌, 𝑤)$ ，而是逐行求解：固定 $𝑤$ ，从 $𝑤$ 出发沿合格输入的逆向边向上闭包，只记录真正成立的对。闭包规则与 $costs$ 一一对应：某个物品进入行内，就让它作为合格输入的每条配方立即被满足（递归只需要一条这样的输入）；一个真实物品在它的每一条配方都被满足时进入，一个 tag 在所有成员都进入时进入。层数记录推导高度，因此在 maxCostDepth 处停下正好对应原来的深度上限。这样只会访问真正成立的少数对（在大型包上只有几千对），而关系里占绝大多数的假对完全不展开，也不会因为环而反复重算。

2.4.3 守卫

和其他剪枝一样，删除推迟到查询时判定：

若 $𝑌$ 有存货，玩家可以直接花掉它，所以只有当 $𝑌$ 没有存货时才能删去 $𝑅$ 。对于 tag 来说，需要所有的成员都没有存货，所以守卫是一组物品，而不是单个输入。
替换者 $𝑆$ 可能只在别的机器上可用，所以和列支配一样要记录代表元的机器并集。
在最优模式下，链上每个物品的所有配方都必须恰好产出一个单位。否则一条批量配方留下的余料可以反过来满足 $𝑅$ ，删掉它反而抬高最优值；这与 tag 篇的批量守卫同源。非最优模式放宽这一条。

3 贪心 DAG 预扫描

我们下面提到了很多基于上界的剪枝，所以我们迫切地想要一个可行的上界；更何况 CP-SAT 也可以通过可行解来加速。所以，我们可以采用启发式算法，也就是贪心，来尝试获得第一个可行解。

我们需要先把 SCC 切成 DAG，然后再在 DAG 上推理。

3.1 切环

最直接的切法是从目标出发做一次拓扑排序。它可以删掉回边，但是删完之后可能会让某些物品不再可达，导致漏解。所以，我们需要考虑一个尽量切得更大的方法。

我们先对物品的投影图做 SCC 分解，再拓扑排序。我们知道拓扑排序是一个不断移除入度为 0 的点的过程，而如果有多于一个可以移除，我们需要按照某种顺序来决定到底动哪个。

为此，我们为每个物品分级：

如果有配方可以无限产出，那么称为 2 级；
如果有库存，那么称为 1 级；
否则，称为 0 级。

我们优先选择级别高的物品。我们还会基于当前 DAG 的深度以及原图中到目标物品的最短距离来排序。如果直接这么写的话需要比较四次，而为了减少比较数量，我们将它们打包在一个 uint64_t 中。这意味着物品数量必须小于 $2^{22}$ ，而 DAG 深度必须小于 $2^{18}$ ，不过在达到这么多之前恐怕 Minecraft 自己先崩溃了。

有了排序之后，在同一个 SCC 内部，对于边 $𝑢 \to 𝑣$ ，如果 $𝑢$ 排在 $𝑣$ 后面就删除，而在 SCC 之间的边不会成环，可以全部留下。这时我们就留下了 SCC 中的所有点，不会出现 DFS 中让某些点不可达的情况。

我们会跑两次：第一次启用第二条规则，第二次禁用。两条规则给出的是两种不同的切点。在实验之后发现，两种规则无法相互覆盖，所以我们都保留了。

3.2 乐观容量

在朴素的 DFS 下，结果可能会差距七个数量级。我们需要修复这一点，所以得搞个上限。换言之，我们需要为每一个物品 $𝑥$ 计算：为了合成足够数量的目标物品，到底最多需要多少个 $𝑥$ 。我们把它叫做 $𝑥$ 的乐观容量，记作 $cap (𝑥)$ 。

首先，我们考虑生产 $𝑥$ 的配方 $𝑟 : 𝑝_{𝑟} \times 𝑥 \leftarrow 𝑞_{𝑟 1} \times 𝑖_{1}, 𝑞_{𝑟 2} \times 𝑖_{2} \dots$ 。它能生产 $𝑥$ 的个数自然是

producible (𝑟) = min_{𝑖 \in input (𝑟)} ⌊ \frac{cap (𝑖)}{𝑞_{𝑟 𝑖}} ⌋ \times 𝑝_{𝑟}

$𝑥$ 的最大需求量一定不会超过它的最大生产量加上库存。那么

cap (𝑥) = stock (𝑥) + max_{𝑟 \in recipes (𝑥)} producible (𝑟)

这里我们采用的是 max 而不是求和，这可能是一个问题。对于下文的两种遍历方式来说，朴素遍历只挑一条配方，所以确实不必求和。但容量遍历则不一样，例如 A <- B, A <- C 的情况下，假如 B 和 C 各有 5 个，那这样算出来的 $cap (𝐴)$ 等于 5。如果之后有一个物品 T x1 <- A x10，就会被误认为无法合成。然而，贪心本就是不完备的，而且实验之后我们发现这样拒绝的内容并不多，所以我们依然保留这个方式。

3.3 朴素遍历

我们从目标出发进行逆后序遍历 (RPO)。

对于当前的物品 $𝑥$ ，如果它有亏空，也就是需要的量大于库存的量，那么我们就去找一个“好”的配方 $𝑟$ ，然后全情投入。我们采用的判别方式有两种：

$𝑟$ 产出的 $𝑥$ 数量越多越好；
$𝑟$ 需要的物品数量越少越好。

我们会用这两个判断方式分别遍历一次。不过不论哪一种，我们都要求配方的所有输入都是可达的。

这里的可达和可达性剪枝处计算的可达并不相同。在剪枝中，我们考虑的是未切环的完整子图，而这里则是在询问切出的 DAG 中是否可达。

3.4 容量遍历

这是朴素遍历的升级版。

我们不再为 $𝑥$ 选择一条最好的配方，而是按能合成的 $𝑥$ 的总数从大到小逐个使用 $𝑥$ 的生产配方，能做多少就做多少。我们把这个值称作配方的容量：

craftable (𝑟) = min_{𝑖 \in input (𝑟)} ⌊ \frac{𝑑}{𝑞_{𝑟 𝑖}} ⌋ \times 𝑝_{𝑟}

这里的 $𝑑$ 是 $𝑥$ 的亏空，每合成完一条配方都会减少。

如果两条配方的容量相同，我们按照 Section 3.3 所说的两种方式来打破平局。

这可以解决一些朴素方法中的问题。如果朴素遍历选中了数值很大的转换，例如 1x A <- 1000x B，就会大幅度提高需求量，这也就是我们刚开始提到的结果差距七个数量级的来源。而基于容量的方法会发现这条路容量不够。

3.5 回退

我们会先使用最普通的 DFS 切环法，最后取 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟}$ 最小的那个。如果普通视图一种可行解都没有找到，再用基于分级的切环重新跑一遍。如果全部失败了，就交给 CP-SAT。

这样求出来的解不一定收支平衡。在 Section 3.4 中，我们求出的只是乐观容量，而且传播过程中也可能因为按批取整而偏离实际。所以，我们必须再检查一次。

4 CP-SAT 求解

这个部分其实没什么太多说的，主要是调用 Google OR-Tools。

我们依然进行了一些优化。虽然每个数值都有 $[0, 2^{63})$ 的自然范围，但是对于 CP-SAT 来说，这个范围太大了，初值经常和最优解偏离十万八千里，甚至可以偏差七个数量级。为了减轻搜索的压力，我们会优先计算出一个更小的上限 $cap$ 。

我们知道，如果使用普通的线性规划 (LP)，可以求出一个有理数域上的解。这时这个解自然可以作为下界估计，然而我们并不知道上界在哪里。所以，我们将这个值乘以 $\frac{9}{8}$ 作为第一次尝试的上界。如果无解，就持续翻倍上界，直到达到预先计算好的、保证中间结果不可能溢出的最大上界。

LP 是非常迅速的，在我们的问题规模下通常仅需数十毫秒，因此这种上界估算一般不会出现性能问题。

不过，在只合成一个目标物品的时候，LP 和 ILP 之间的差距通常也很大，而乘法能增加的并不够多。因此，如果 LP 太小，我们就转而增加一个固定的数值（这里选择的是 64），而不是乘以 $\frac{9}{8}$ 。

4.1 基于价值的剪枝【无法启用】

考虑我们规划的对偶。我们原本的目标是：在约束 $\sum_{𝑟} 𝐴_{𝑖, 𝑟} 𝑥_{𝑟} \geq 𝑏_{𝑖}$ 下，求出 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟}$ 的最小值，其中 $𝑐_{𝑟}$ 是简介里说的配方成本（普通配方为 1，批次级为批大小，tag 边为 0）。其中对于配方 $𝑟 : 𝑝 \times 𝑜 \leftarrow 𝑞_{1} \times 𝑖_{1}, \dots$ ，有 $𝐴_{𝑜, 𝑟} = 𝑝$ ， $𝐴 (𝑖_{𝑛}, 𝑟) = - 𝑞_{𝑛}$ ， $𝑏_{𝑖}$ 是物品 $𝑖$ 的净需求（目标物为正，库存取负）。

它的对偶是：在 $\sum_{𝑖} 𝐴_{𝑖, 𝑟} 𝑦_{𝑖} \leq 𝑐_{𝑟}$ （每条配方一个约束，右边就是它的成本）下最大化 $\sum_{𝑖} 𝑏_{𝑖} 𝑦_{𝑖}$ 。我们知道， $𝑦_{𝑖}$ 可以理解为物品 $𝑖$ 的边际价值，也就是多得到一个 $𝑖$ 所需要付的成本。于是 $𝑟$ 的等效成本是 ${(𝐴^{𝑇} 𝑦)}_{𝑟} = 𝑝 𝑦_{𝑜} - \sum_{𝑛} 𝑞_{𝑛} 𝑦_{𝑖_{𝑛}}$ ，从直觉上来说，是它的工作量。这个值称作折合成本，但 $𝑟$ 本身执行一次的花费是 $𝑐_{𝑟}$ ，与它的产出结构无关。二者之差

𝑑_{𝑟} = 𝑐_{𝑟} - (𝑝 𝑦_{𝑜} - \sum_{𝑛} 𝑞_{𝑛} 𝑦_{𝑖_{𝑛}}) \geq 0

就是配方 $𝑟$ 亏掉的工作量，称作缩减成本，在 LP 最优处可以直接读出。

由对偶可行性，对任意可行解 $𝑥$ 都有 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \geq 𝑙 + \sum_{𝑟} 𝑑_{𝑟} 𝑥_{𝑟}$ ，其中 $𝑙$ 是 LP 的最优值。设 $𝑢$ 是某个已知可行解的成本。若某个满足 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \leq 𝑢$ 的可行解用到了配方 $𝑟$ （即 $𝑥_{𝑟} \geq 1$ ），则 $𝑢 \geq \sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \geq 𝑙 + 𝑑_{𝑟} 𝑥_{𝑟} \geq 𝑙 + 𝑑_{𝑟}$ 。所以只要

𝑑_{𝑟} > 𝑢 - 𝑙

就必有 $𝑥_{𝑟} = 0$ ：步数不超过 $𝑢$ 的解一定不会用到配方 $𝑟$ 。我们可以直接把这一列删掉。

更进一步地说，即使不能直接得到 $𝑥_{𝑟} \leq 0$ ，我们也可以得到这个结果，加快 CP-SAT 的处理速度：

𝑥_{𝑟} \leq ⌊ \frac{𝑢 - 𝑙}{𝑑_{𝑟}} ⌋

实现上，LP 松弛本来就要算一次来估计 $cap$ ，我们顺便取出所有 $𝑑_{𝑟}$ 。 $𝑢$ 则由一次紧上界探测给出：拿 $⌈ 𝑙 + gap ⌉$ 当作 $cap$ 跑一次 CP-SAT。如果它直接不可行，就说明 $𝑢 - 𝑙 > gap$ ，方法不划算，跳过；否则拿到 $𝑢$ ，按上面的条件删列，再在删过的模型上以 $𝑢$ 为 $cap$ 正式求解。返回的 $𝑥$ 会补回被删的列（取 0），所以对外仍然是一列一个配方。

在一些额外的测试之后，我发现这个东西反而会拖慢速度：最开始想要拿到 $𝑢$ 并不是一件容易的事情。文档后面也有一些基于 $𝑢$ 的想法，也一并都不启用。

5 针对多个零库存物品的推广

前面的剪枝只针对零库存的单个物品。我们自然想知道能否同时利用多个零库存物品，剪掉某个配方 $𝑅$ ，也就是说明 $𝑥_{𝑅} = 0$ 。

我们考虑这样的一组配方：

铜镐 x1 <- 铜锭 x3, 木棍 x2
铜粒 x1 <- 铜镐 x1
铜锭 x1 <- 铜粒 x9

如果这三个配方同时被用到，那就亏到姥姥家了：按照 1:9:1 的情况计算，我们亏掉了 18 个木棍和 26 个铜锭。但是如果按照 1:1:1 的比例计算，我们反而“赚到”了 8 个铜粒，尽管这仍然是亏的，不如直接通过铜锭合成来得多。

我们希望通过“打包配方”的形式，来用数学描述这个事实。

沿用 Section 4.1 中的记号： $𝐴$ 是以物品为行、以配方为列的收支矩阵，其中 $𝐴_{𝑖, 𝑟}$ 为配方 $𝑟$ 对物品 $𝑖$ 的净产出（产出取正、消耗取负）。可行解 $𝑥$ 满足 $𝐴 𝑥 \geq 𝑏, 𝑥 \geq 0$ 且 $𝑥$ 取整数，目标是最小化 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟}$ 。

我们将上述的配方包记作向量 $𝑧 = [𝑧_{1}, 𝑧_{2}, \dots, 𝑧_{𝑛}]$ ，其中 $𝑧_{𝑖}$ 是第 $𝑖$ 个配方在这个配方包里执行的次数。

引理. 若 $𝑧 \neq 0$ 是非负整数向量且 $𝐴 𝑧 \leq 0$ ，则任何满足 $𝑥 \geq 𝑧$ 的可行解 $𝑥$ 都不是最优解。

证明. $𝐴 (𝑥 - 𝑧) = 𝐴 𝑥 - 𝐴 𝑧 \geq 𝐴 𝑥 \geq 𝑏$ ，同时 $𝑥 - 𝑧$ 非负，所以 $𝑥 - 𝑧$ 是可行解。它和 $𝑥$ 相比则减少了 $𝑐^{𝑇} 𝑧 = \sum_{𝑟} 𝑐_{𝑟} 𝑧_{𝑟}$ 的成本。 $𝑧$ 里一定含有被认证的那条真实配方（ $𝑧_{𝑅} = 1$ ），而真实配方的 $𝑐_{𝑅} \geq 1$ ，其余 $𝑐_{𝑟} \geq 0$ ，所以 $𝑐^{𝑇} 𝑧 > 0$ ，一定更优。

这个引理在说， $𝑧$ 这个配方包在最优解中一次都不能执行。那么，我们可以做出如下推论：

对于配方 $𝑅$ ，如果能找到某个正整数 $𝑘$ 并证明对所有的可行解 $𝑥$ 都有 $𝑥_{𝑅} \geq 𝑘 \Rightarrow 𝑥 \geq 𝑧$ ，且 $𝐴 𝑧 \leq 0$ ，则任何最优解都有 $𝑥_{𝑅} \leq 𝑘 - 1$ 。当 $𝑘 = 1$ 时结论最强，这时我们可以直接剪掉配方 $𝑅$ 。

5.1 蕴含关系的证明

这个蕴含关系 $𝑥_{𝑅} \geq 𝑘 \Rightarrow 𝑥 \geq 𝑧$ 是最大的难点。既然是自动证明，我们不妨考虑一个形式证明系统，也就是一组推理规则。

维护一个下界向量 $𝑧$ ，初始值为 $𝑧_{𝑅} = 𝑘$ ，而其他的 $𝑧_{𝑖} = 0$ 。容易说明此时必然有 $𝐴 𝑧 \leq 0$ 。我们希望保证 $𝑧 \leq 𝑥$ 。我们将当前 $𝑧$ 对物品 $𝑖$ 的消耗量记作 $𝑐_{𝑖} (𝑧) = \sum_{𝑟} max (- 𝐴_{𝑖, 𝑟}, 0) 𝑧_{𝑟}$ ，并将零库存的物品集合称作 $𝐺$ 。

R1. 唯一生产者的下界

如果只有一个生产物品 $𝑖 \in 𝐺$ 的配方 $𝑝$ ，并且生产 $𝑎$ 个，那么 $𝑥_{𝑝} \geq ⌈ \frac{𝑐_{𝑖} (𝑧)}{𝑎} ⌉$ 。这是因为 $𝑖$ 的消耗量至少是 $𝑐_{𝑖} (𝑧)$ ，而产量减去消耗量必须大于零。

我们可以把下界 $𝑧_{𝑝}$ 提高到这个值，依然能满足 $𝑧 \leq 𝑥$ 。

在更新 $𝑥_{𝑝}$ 后，我们自然会更新 $𝑥$ 对各种资源的消耗量，从而更新 $𝑥$ 的生产量，那么就可以继续使用其他基于生产量的规则了。

R2. 被支配的输入

假设物品 $𝑖$ , $𝑗$ 都在 $𝐺$ 中。如果生产 $𝑖$ 的每个配方 $𝑝$ 都以不小于 $𝛼$ 的比率消耗另一种资源 $𝑗$ ，则 $𝑐_{𝑗} (𝑥) \geq 𝛼 𝑐_{𝑖} (𝑧)$ 。这是对 R2 在生产者不唯一时的补充。

R3. 分支

如果前两条都不能处理，说明 $𝑖$ 有多条配方，需要一起产出需求。设 $𝑖$ 有 $𝑚$ 条配方 $𝑝_{1}, \dots, 𝑝_{𝑚}$ ，分别产出 $𝑎_{1}, \dots, 𝑎_{𝑚}$ 个。对任意可行解都有

\sum_{𝑗} 𝑎_{𝑗} 𝑥_{𝑝_{𝑗}} = {produced}_{𝑖} (𝑥) \geq {consumed}_{𝑖} (𝑥) \geq 𝑙_{𝑖}

因此至少有一条配方满足 $𝑎_{𝑗} 𝑥_{𝑝_{𝑗}} \geq \frac{𝑙_{𝑖}}{𝑚}$ ，也就是 $𝑥_{𝑝_{𝑗}} \geq ⌈ \frac{𝑙_{𝑖}}{𝑚 𝑎_{𝑗}} ⌉$ 。我们对每条配方分出一支：在第 $𝑗$ 支中把 $𝑧_{𝑝_{𝑗}}$ 提高到 $⌈ \frac{𝑙_{𝑖}}{𝑚 𝑎_{𝑗}} ⌉$ ，再继续用 R1、R2 传播。最后取所有分支算出的 $𝑧$ 的逐分量最小值，作为这一层的结果。这是因为，对任意满足 $𝑥_{𝑅} \geq 𝑘$ 的可行解 $𝑥$ ，一定存在某个 $𝑗$ 可以给出下界 $𝑧^{(𝑗)} \leq 𝑥$ 。而逐分量取最小值可以使得 $𝑧$ 不超过任何 $𝑧^{(𝑗)}$ ，所以它也 $\leq 𝑥$ 。所以，分支必然是有限的：每一次分支都至少把某条配方的下界抬高一点，而 $𝑧$ 的总量被预算限制。

将 R1 到 R3 展开成一棵搜索树；每个叶子给出一个对相应分支假设成立的下界，取所有叶子的逐分量最小值，就得到对每个满足 $𝑥_{𝑅} \geq 𝑘$ 的可行解都成立的下界 $𝑧$ 。最后检查 $𝐴 𝑧 \leq 0$ ，若成立则记录证书 $(𝑅, 𝑘, 𝑧, 𝐺)$ 。

在实测中，我注意到 R3 效果不佳，而过于耗时。所以我选择禁用 R3，仅使用 R1 和 R2 处理，效果反而更好。

5.2 预处理与查询

目前而言，我的想法是只保留 $𝑘 = 1$ ，因为这是最有用的。

预处理时，为每个配方 $𝑅$ 保存一组 $(𝑧, 𝐺, 𝑊)$ ： $𝑧$ 是上述得到的配方包， $𝐺$ 是零库存的物品集合，而 $𝑊$ 是 $𝑧$ 中配方所需的工作台集合。查询时，如果 $supp (𝑧) = {𝑖 | 𝑧_{𝑖} \neq 0}$ 落在可达子图内、 $𝐺$ 与有库存物品不交、 $𝑊$ 可用，即可删除 $𝑅$ 这条边。

5.3 利用配方的价值

对任意对偶可行的 $𝑦 \geq 0$ ，我们有 $𝐴^{𝑇} 𝑦 \leq 𝑐$ 。仍然考虑缩减成本 $𝑑 = 𝑐 - 𝐴^{𝑇} 𝑦 \geq 0$ ，那么对任意的 $𝑧 \geq 0$ 且 $𝐴 𝑧 \leq 0$ 有

\sum_{𝑟} 𝑑_{𝑟} 𝑧_{𝑟} = 𝑑^{𝑇} 𝑧 = 𝑐^{𝑇} 𝑧 - 𝑦^{𝑇} 𝐴 𝑧 \geq \sum_{𝑟} 𝑐_{𝑟} 𝑧_{𝑟} > 0

也就是说，每个处置环里一定含有缩减成本为正的列。这带来一个有用的改写：设 $𝐻 = {𝑟 : 𝑑_{𝑟} > 𝑢 - 𝑙}$ 是基于价值的剪枝所删去的列。如果能证明 $𝑥_{𝑅} \geq 𝑘$ 必然会用到 $𝐻$ 中的某个配方至少 $𝑡$ 次，那么自然有 $\sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \geq 𝑙 + 𝑑_{𝑅} 𝑘 + 𝑡 {min}_{ℎ \in 𝐻} 𝑑_{ℎ}$ ；第二项 $𝑑_{𝑅} 𝑘$ 是执行了 $𝑘$ 次配方 $𝑅$ 导致的，而第三项 $𝑡 {min}_{ℎ \in 𝐻} 𝑑_{ℎ}$ 则是执行了 $𝑡$ 次 $𝐻$ 中的配方导致的。这时，既然 $𝑢 \geq \sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \geq 𝑙$ ，自然有

𝑥_{𝑅} \leq 𝑘 \leq ⌊ \frac{𝑢 - 𝑙 - 𝑡 {min}_{ℎ \in 𝐻} 𝑑_{ℎ}}{𝑑_{𝑅}} ⌋

比起之前的 $⌊ \frac{𝑢 - 𝑙}{𝑑_{𝑅}} ⌋$ 更紧了。

我们可以直接用上一节求出 $𝑧$ 的方法来求解，只需要把得到的 $𝑧$ 里属于 $𝐻$ 的配方次数加起来就是 $𝑡$ 了。

5.4 与线性规划变量上界的关系

上面的 $𝐴 𝑧 \leq 0$ 是一个纯组合的最优性论证，但它不总是强过线性规划。事实上，更强的界是直接求解线性规划

𝑈_{𝑅} = max {𝑥_{𝑅} : 𝐴 𝑥 \geq 𝑏, \sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \leq 𝑢, 𝑥 \geq 0}, 𝑥_{𝑅} \leq ⌊ 𝑈_{𝑅} ⌋ .

我们知道 $𝑢 \geq \sum_{𝑟} 𝑐_{𝑟} 𝑥_{𝑟} \geq 𝑙 + \sum_{𝑟} 𝑑_{𝑟} 𝑥_{𝑟}$ ，其中 $𝑙 = 𝑏^{𝑇} 𝑦$ 是对偶目标。那么自然有

\sum_{𝑟} 𝑑_{𝑟} 𝑥_{𝑟} < 𝑢 - 𝑏^{𝑇} 𝑦

然而，这是有理数。我们乘以一个 $𝐷$ 使得左边的每一个 $𝑑_{𝑟}$ 都是整数：

\sum_{𝑟} (𝐷 𝑑_{𝑟}) 𝑥_{𝑟} \leq ⌊ 𝐷 𝑢 - 𝐷 𝑏^{𝑇} 𝑦 ⌋ = 𝐷 𝑢 - ⌈ 𝐷 𝑏^{𝑇} 𝑦 ⌉

将 $𝑥_{𝑅}$ 单独留在左边，移项之后就可以得到

𝑥_{𝑅} \leq \frac{𝑢 - \frac{⌈ 𝐷 𝑏^{𝑇} 𝑦 ⌉}{𝐷} - \sum_{ℎ \neq 𝑅} 𝑑_{ℎ} 𝑥_{ℎ}}{𝑑_{𝑅}}

这其实就是一阶 CG 切割。之前剪枝时的 $⌊ \frac{𝑢 - 𝑙}{𝑑_{𝑅}} ⌋$ 只是它的一个特例：不考虑其他项的亏损 $𝑑_{ℎ} 𝑥_{ℎ}$ ，同时令 $𝐷 = 1$ ，就会得到这个结果。

6 孤岛消除

6.1 动机

你一定知道为大家所“津津乐道”的更新：Mojang 更新了铜块、斑驳的铜块、锈蚀的铜块、氧化的铜块、涂蜡的铜块、涂蜡的斑驳铜块、涂蜡的锈蚀铜块、涂蜡的氧化铜块等数百种排列组合（但是仍然没有竖半砖）。它们和普通铜块可以转换，所以和铜块这个基础形态一起被卷进同一个强连通分量，而它们自己却除了作为装饰品以外没有什么作用。

以此为引，直觉告诉我们：如果一块区域只通过一个出口 $𝑖$ 与外界相连，而它没法凭空产出 $𝑖$ ，那么它不可能出现在最优解里。

“与外界相连”不必是（无向图中的）割点。各种氧化程度的铜在通用机械中可以通过氧气转换，所以铜块不是割点。但循环没有净产出任何物品，只是在额外消耗氧气，所以它仍然不该出现在最优解里。所以我们给出这个比较通用的引理：

引理. 取一些不包含合成目标的物品 $𝐼$ ，记 $𝐺$ 为所有消费或生产 $𝐼$ 中物品的配方。设 $𝐼$ 中每个物品的库存都是 $0$ ，并存在一个出口物品 $𝑖 \notin 𝐼$ ，使得 $𝐺$ 中每个配方产出的物品都在 $𝐼 \cup {𝑖}$ 中，也就是对产出封闭。这时，若不存在 $𝐺$ 上的配方向量 $𝑧 \geq 0$ ，使得

{(𝐴 𝑧)}_{𝑖} > 0 \land \forall 𝑗 \in 𝐼 . {(𝐴 𝑧)}_{𝑗} \geq 0

则任何最优解都满足 $\forall 𝑟 \in 𝐺 . 𝑥_{𝑟} = 0$ 。

证明. 假设 $𝑥$ 是最优解，而 $𝑧 = 𝑥 |_{𝐺}$ 是 $𝑥$ 被限制在 $𝐺$ 上的那一部分。因为 $𝐺$ 包含了所有与 $𝐼$ 中物品相邻的配方， $𝐼$ 中物品的收支行只与 $𝐺$ 内的配方有关；又因为库存为 $0$ ，可行性给出 ${(𝐴 𝑧)}_{𝑗} = {(𝐴 𝑥)}_{𝑗} \geq 𝑏_{𝑗} = 0$ （ $𝑗 \in 𝐼$ ）。根据条件， $𝑧$ 不能同时满足该条件与 ${(𝐴 𝑧)}_{𝐴} > 0$ ，那么自然有 ${(𝐴 𝑧)}_{𝑖} \leq 0$ 。令 $𝑥^{'} = 𝑥 - 𝑧$ ：在 $𝐼$ 内 ${(𝐴 𝑥^{'})}_{𝑗} = 0 \geq 𝑏_{𝑗}$ ；对于出口本身有 ${(𝐴 𝑥^{'})}_{𝑖} = {(𝐴 𝑥)}_{𝑖} - {(𝐴 𝑧)}_{𝑖} \geq {(𝐴 𝑥)}_{𝑖} \geq 𝑏_{𝐴}$ ；而对于不在 $𝐼 \cup {𝐴}$ 中的物品 $ℎ$ ，条件告诉我们 $𝐺$ 不会产出 $ℎ$ ，即 ${(𝐴 𝑧)}_{ℎ} \leq 0$ ，所以 ${(𝐴 𝑥^{'})}_{ℎ} \geq {(𝐴 𝑥)}_{ℎ} \geq 𝑏_{ℎ}$ 。于是 $𝑥^{'}$ 可行且执行次数更少，矛盾。

出口 $𝑖$ 并不是本质的，它只是为了描述岛漏出的产出。若 $𝐼$ 自身就对产出封闭，也就是 $𝐺$ 中每个配方产出的物品都在 $𝐼$ 中，那么任取一个 $𝐼$ 外的物品作为出口 $𝑖$ ， $𝐺$ 都产不出它，判定条件自动成立，对偶解取 $𝑦 = 0$ 即可。真正被用到的是 $𝐺$ 在 $𝐼$ 之外没有净产出，而不是“只有一个出口”。

6.2 判定

值得注意的是，正产出环是不能用 Bellman-Ford 的方法计算的，这是因为合成图是 AND-OR 图，和前面无法使用 LT 算法计算代价支配的理由一样：一条配方需要它的全部输入，于是环的利润是若干配方共享子产物之后的结果，不能逐物品地用一个势函数刻画。注意这里被卡住的是“ $𝐺$ 能否净产出 $𝐴$ ”这个判定，而不是候选 $𝐼$ 的寻找： $𝐼$ 只关于可达性，而可达性在配方上是 OR，下面会看到一个普通的支配树就够了。

要证明不存在是很困难的。所以，我们不如将它转化为 Farkas 对偶形式，证明存在就简单了。它的对偶是：存在 $𝐼$ 上的 $𝑦 \geq 0$ 使得

\forall 𝑟 \in 𝐺 . \sum_{𝑗 \in 𝐼} 𝑦_{𝑗} 𝐴_{𝑗, 𝑟} + 𝐴_{𝐴, 𝑟} \leq 0

所以，我们只需要以 $\sum_{𝑗} 𝑦_{𝑗}$ 为目标求解上述线性规划，得到任何一个可行的 $𝑦$ 即可。这样算出来的 $𝑦$ 是有理的，所以我们得乘以一个数去消除浮点误差，确认是否可行。（TODO：这种猜一个分母 $𝐷$ 再用 int128 验算的方法看起来好难受。真的没有别的方法了吗？）

实现上，我们先跑无向图的割点枚举，取每个连通块作为 $𝐼$ ；再取每个候选出口 $𝐴$ 所能支配的最大集合。后者就是依赖图 $𝑥 \to$ 生产 $𝑥$ 的配方的每个输入上 $𝐴$ 所支配的物品集合：不经过 $𝐴$ 就不能到达目标或库存物品的物品，自动满足输出条件。它能把只有输入的岛屿也一并收进来。

这个支配关系是普通有向图上的可达性，所以实现时给依赖图加一个连到目标和每个有库存的物品的虚拟根，然后跑一次 Lengauer-Tarjan。这时， $𝐴$ 的岛就是它在这棵树里的真子树。

出口为空的情形既不需要线性规划，也不需要枚举，而且有一个唯一的最大岛。记 $𝐵$ 为从目标和所有有库存的物品出发、在下面这条规则下闭包得到的最小集合：若某条配方产出 $𝐵$ 中的物品，就把该配方的所有物品并入 $𝐵$ 。 $𝐵$ 的补集就是对产出封闭的岛：某条配方若触及这个补集，就不可能产出 $𝐵$ 中的物品，否则闭包会把被它触及的那个物品也拉进 $𝐵$ 。反过来，若 $𝐼$ 避开目标与库存且对产出封闭，令 $𝐵^{'}$ 为 $𝐼$ 的补集：任何产出 $𝐵^{'}$ 中物品的配方都不能触及 $𝐼$ （否则它就产出了一个 $𝐼$ 外的物品），所以它的所有物品都在 $𝐵^{'}$ 里，即 $𝐵^{'}$ 也满足这条闭包规则；而 $𝐵$ 是最小的，于是 $𝐵$ 包含于 $𝐵^{'}$ ，即 $𝐼$ 包含于 $𝐵$ 的补集。所以 $𝐵$ 的补集是最大的岛。

6.3 不止一个出口的孤岛

我们已经说过出口 $𝑖$ 并不本质。对于多出口的岛 $𝐼$ ，如果出口集合是 $𝑂$ ，只需要满足对任意的 $𝑜 \in 𝑂$ 都没有 $𝑧$ 使得

{(𝐴 𝑧)}_{𝑜} > 0 \land \forall 𝑗 \in 𝐼 . {(𝐴 𝑧)}_{𝑗} \geq 0

就同样可以剪枝。所以，现在问题变成了我们到底如何找到这样的岛。

我们可以考虑先固定一个种子 $𝑠$ ，首先令 $𝐼 = {𝑠}$ ，并记 $𝑁 (𝐼)$ 为所有产出或消耗任意 $𝐼$ 中元素的所有配方。令 $𝑂 = out (𝑁 (𝐼)) - 𝐼$ ，也就是 $𝐼$ 当前产出的不属于 $𝐼$ 的部分。如果对于某个 $𝑜 \in 𝑂$ 可以找到上述的 $𝑧$ ，那么 $𝑜$ 就必须加入 $𝐼$ ，直到遇到目标 $𝑇$ 或者 $𝑜$ 有库存的时候失败。如果一直都没有遇到，最终成型的闭包 $𝐺$ 就是我们想要的孤岛，并且无需额外证明。

对每一个物品都这么跑一遍太久了，而且结果无法复用：即使从 $𝑠$ 开始得到的闭包 $𝐺$ 失败了，也不意味着任何 $𝑠^{'} \in 𝐺$ 都会失败，同时也无法推出 $𝑠$ 的输入一定会失败。考虑这个例子：

X <- S
S + A <- Y
T + B <- A
Z <- X

如果目标为 $𝑇$ ，那么自然从 $𝑆$ 开始会失败，因为闭包会包含 $𝑇$ 。然而闭包已经包含了 $𝑋$ ，从 $𝑋$ 开始则不会失败。这是因为 $𝑆$ 产出了多个物品，其中牵扯到了 $𝐴$ ，但 $𝑋$ 则没有这个烦恼。同时， $𝑌$ 产出了 $𝑆$ ，但是如果从 $𝑌$ 开始，我们会发现闭包在 $𝑆$ 处就已经结束了，而 $𝑌$ 本身就是一个孤岛。

实际上，这并不是由多产出所带来的。考虑：

S <- A
U <- S
V <- S
T <- V

目标同样为 $𝑇$ ，从 $𝑆$ 开始会失败，而 $𝑈$ 不会。这大概是因为这个闭包的扩张不是对称的。不过，这两个例子也说明了正向和反向的可达性分析都是孤岛消除的一个特例。

所以为了避免在求解之前花费太多时间，我在考虑启发式地跑：优先尝试处于二元环中的物品。一般这种压缩/分解或者互相转换的二元环比较多。

在尝试之后，即使这样似乎也只能多剪掉 0.2% 左右的边，完全不值得。所以这个想法被放弃了。

7 变体消除

7.1 动机

Minecraft 的 16 种染色旗帜都出现在同一个 tag 里，而这个 tag 的唯一用途是合成线；任意一种旗帜又能通过染料和“除它以外的旗帜”的 tag 来染色成别的旗帜，但这些旗帜最终还是只能合成线，所以这样的染色是没有用的。

因此，我们以这两个条件来定义物品变体集合 $𝑉$ ：

不可区分：存在一个 tag $𝑇$ ，使得 $𝑉$ 不在 $𝑉$ 中的消费者必定是 $𝑇$ 。
无正产出： $𝑉$ 中配方产出的量不超过它的消耗。

那么， $𝑉$ 中的互相转换就可以删除。下面我们来看更加形式化的定义。

7.2 定义与引理

取一组物品 $𝑉$ 。记配方 $𝑟$ 对 $𝑉$ 的净贡献为 $𝐶_{𝑉} (𝑟) = \sum_{𝑣 \in 𝑉} 𝐴_{𝑣, 𝑟}$ 。如果一个 tag $𝐽$ 的成员 $𝑀 (𝐽)$ 都在 $𝑉$ 中，就称它是 $𝑉$ -tag；反过来，如果 $𝑉 \subseteq 𝑀 (𝐽)$ ，那么称 $𝐽$ 是出口 tag。

我们把 $𝑉$ 中的配方叫做内部配方。具体的定义是这样的：如果满足下列两条之一，那么 $𝑟$ 就是内部配方。

$𝑟$ 是产出 $𝑉$ 中物品的真实配方，而且它的全部产出都在 $𝑉$ 中，并且 $𝐶_{𝑉} (𝑟) \leq 0$ 。我们把最后一个条件称为 $𝑟$ 对 $𝑉$ 中性。
$𝑟$ 是 $𝑉$ -tag 的成员边。

引理. 设目标 $𝑡 \notin 𝑉$ 。若

$𝑉$ 中物品的每个消费者要么是内部配方，要么是通向出口 tag 的成员边；
每条内部实配方都对 $𝑉$ 中性，

则任何最优解都不执行内部配方。

证明. 设 $𝑥$ 可行， $𝑧 = 𝑥 |_{𝐺}$ 是它限制在内部配方集 $𝐺$ 上的部分。先看 $𝑉$ 的总量。由条件 2，内部实配方的 $𝐶_{𝑉} \leq 0$ ；对每个 $𝑉$ -tag $𝐽$ ，既然它的收支 ${(𝐴 𝑧)}_{𝐽} \geq 0$ ，那么消耗 $𝐽$ 的内部配方次数不超过成员边产出 $𝐽$ 的次数。我们又知道每条成员边恰好消耗 1 个 $𝑉$ 中的物品，所以成员边消耗的 $𝑉$ 不少于内部配方产出的 $𝑉$ ，即 ${(𝐴 𝑧)}_{𝑉} \leq 0$ 。所以 ${(𝐴 (𝑥 - 𝑧))}_{𝑉} \geq {(𝐴 𝑥)}_{𝑉} \geq 0$ 。 $□$

这和孤岛消除不一样，就算内部能净产出外部物品也不会破坏引理。

7.3 寻找 $𝑉$

我们在每次查询时都检查一次，而不是预处理，因为这个 pass 够快。

我们从每个可能作为出口的 tag $𝑡_{0}$ 开始，先把 $𝑉$ 设置成 $𝑀 (𝑡_{0})$ ，然后反复删去破坏条件的物品，直到不再变化。删除的规则是

物品被某条真实配方直接消费。
物品所在的某个 tag 既不是 $𝑉$ -tag，也不是出口 tag。
物品所在的某个 $𝑉$ -tag 还有存活的外部消费者。

最后，我们重新检查一遍 $𝑉$ 是不是满足我们引理。如果通过的话，就删掉所有内部配方，以及死掉的 $𝑉$ -tag 的成员边。

7.4 独占物品的推广

直觉. 我们不一定要找一个完整的 tag 消除。如果有一个物品 $𝑢$ 只在某个 tag 里使用，而合成它的所有配方都包含可以用于 tag 的物品，那么 $𝑢$ 其实就没有用了——直接把合成它的物品拿去满足配方会更好。

不过，这只是直觉，我们还要处理数量以及副产物之类的问题。下面我们形式化这个直觉。

考虑一个 tag $𝑇$ 。如果所有用到 $𝑢$ 的配方都是 $𝑇$ 的成员边，我们就称实物 $𝑢$ 被 $𝑇$ 独占。

我们将 $𝑟$ 对 $𝑀 (𝑇)$ 的净贡献记为 $𝐶_{𝑀 (𝑇)} (𝑟)$ ，这个东西在 Section 7.2 里已经定义过一次了。简单理解就是“ $𝑟$ 产出 $𝑀 (𝑇)$ 中物品的数量”。

引理. 如果实配方 $𝑟$ 的所有产出都被同一个 $𝑇$ 独占，且 $𝐶_{𝑀 (𝑇)} (𝑟) \leq 0$ ，那么任何最优解都不会执行 $𝑟$ 。

证明与变体消除相同，只是把类换成整个 $𝑀 (𝑇)$ 。设可行解为 $𝑥$ ，而 $𝑧 = 𝑥 |_{𝑟}$ 。我们可以重新指派 $𝑥 - 𝑧$ 中 $𝑇$ 的成员边，而 $𝑀 (𝑇)$ 之外的物品收支只增不减。 $□$

7.5 多出口的推广

普通的变体消除要求 $𝑉$ 存在一个唯一的出口 tag。实际上，这个条件并不必要。

动机. 在 ATM 中，有各种各样的玻璃：{Scratched, Connecting, Clear, $𝜀$ } $\times$ 颜色 $\times$ {玻璃，玻璃板}（很遗憾，这些东西在游戏内部也没有中文翻译）。它们没有库存的时候，在合成图中一般都不会用到，直接替换为普通的玻璃和玻璃板就可以了。

所以，我们将这样的装饰物集合称作 $𝐷$ ，并考虑一个映射 $𝜎 : 𝐷 \to Item - 𝐷$ ，将 $𝜎 (𝑑)$ 映射到它的本体。举个例子，“连接的绿色染色玻璃板”将会被映射到“玻璃板”。我们可以将 $𝜎$ 扩张到 $Item \to Item$ ，只要在原有的那些映射之外令 $𝜎$ 恒等就可以了。

我们用 $𝜋 (𝑣)$ 表示原始的收支向量 $𝑣$ 经过 $𝜎$ 传播后的结果，也就是将 $𝑢$ 的部分转移到 $𝜎 (𝑢)$ 上。具体而言，

\forall 𝑖 \notin 𝐷, {𝜋 (𝑣)}_{𝑖} = 𝑣_{𝑖} + \sum_{𝑗 \in 𝜎^{- 1} (𝑖)} 𝑣_{𝑗}

而如果 $𝑖$ 在 $𝐷$ 中，那么 ${𝜋 (𝑣)}_{𝑖} = 0$ 。

这样，我们就可以提出消除的条件了。

引理. 如果对于任意 $𝐷$ 中的配方 $𝑟$ ，都存在一个向量 $𝑟^{*}$ ，使得 $\forall 𝑖 \in 𝐷 . {(𝑟^{*})}_{𝑖} = 0$ （也就是 $𝑟^{*}$ 是 D-free 的），而且 $𝐴 𝑒_{𝑟} = 𝜋 (𝐴 𝑟^{*})$ 并且 $𝑐_{𝑟^{*}} \leq 𝑐_{𝑟}$ ，那么只要 $𝐷$ 不包含合成目标，最优解就可以不使用 $𝐷$ 。

这里的 $𝑐_{\cdot}$ 是代价，而 $𝐴$ 则是收支矩阵。

证明. 设 $𝑥$ 是最优解，我们下面证明 $𝑥^{'} = \sum_{𝑟} 𝑥_{𝑟} 𝑟^{*}$ 也是最优解。

𝐴 𝑥^{'} = 𝐴 \sum_{𝑟} 𝑥_{𝑟} 𝑟^{*} = \sum_{𝑟} 𝑥_{𝑟} 𝜋 (𝐴 𝑒_{𝑟}) = 𝜋 (𝐴 𝑥)

最后一步是因为 $𝜋$ 是线性的。既然 $𝐴 𝑥 \geq 𝑏$ ，对任意的 $𝑖 \notin 𝐷$ ，都有

{𝜋 (𝐴 𝑥)}_{𝑖} = {(𝐴 𝑥)}_{𝑖} + \sum_{𝑗 \in 𝜎^{- 1} (𝑖)} {(𝐴 𝑥)}_{𝑗} \geq {(𝐴 𝑥)}_{𝑖} \geq 𝑏_{𝑖}

对 $𝑖 \in 𝐷$ ， ${𝜋 (𝐴 𝑥)}_{𝑖} \geq 0$ 。既然目标不在 $𝐷$ 中，必然有 $𝑏_{𝑖} \leq 0$ ，所以 $𝑥^{'}$ 是可行解。

而 $𝑐_{𝑥^{'}} = \sum 𝑥_{𝑟} 𝑐_{𝑟^{*}} \leq \sum 𝑥_{𝑟} 𝑐_{𝑟} = 𝑐_{𝑥}$ ，所以 $𝑥^{'}$ 是最优解。

7.6 寻找 $𝐷$ 与 $𝜎$

我们没有任何名字可用，所以只能从图的结构里找。（TODO：其实按照名字进行启发式搜索也是可以接受的，而且 JNI 本来就会传递 .names.tsv 给模糊搜索的部分。要这么做吗？）

大部分配方转换都会包含等量转换的配方 $𝑎 \times 𝑏 \leftarrow 𝑎 \times 𝑢$ 。如果合成图里存在这条边，我们就在新的图 $𝐺$ 中连边 $𝑢 \to 𝑏$ ，而 $𝐺$ 的弱连通分量就是互相可以转换的轨道，其中的成员应当被 $𝜎$ 映射成同一个物品。至于本体，我们选参与合成的配方最多的那个成员。一般而言，装饰物只会经过 tag 或者参与转换配方，只有本体才会被别的配方指名道姓地需要。

TODO：如果没有任何成员被外部配方直接需求，那么孤岛消除应该已经删掉它了才对。但是好像还留下来了一点？

不过矿物锭、块和粒之间的转换并非只有装饰作用。所以，为了排除这种情况，我们只在 $𝑀 (𝑢) \subset 𝑀 (𝑏)$ 的时候才让 $𝜎 (𝑢) = 𝑏$ ；此外， $𝑢$ 的某个 tag 还得真的被配方消费。（TODO：或许需要先进行死物品消除）

在确定了一系列 $𝑢$ 之后，它不见得就是完整的 $𝐷$ 了，还可能有更多的物品。如果配方 $𝑟$ 的投影 $𝜋 (𝐴 𝑟)$ 还不可实现，就在同型配方里找一个 $𝑟^{'}$ ，把 $𝑟^{'}$ 与 $𝜋 (𝐴 𝑟)$ 不一致的那几个输入或输出折叠到本体。这可以解决“连接玻璃板”与“连接玻璃”折叠不进去的问题。

最后，任何一次折叠都要验证一次引理条件。

8 启动可达性

8.1 动机

求解器看到的约束只有收支条件：

\forall 𝑖 . produced (𝑖) - consumed (𝑖) \geq 𝑏_{𝑖} .

它把整个计划里每一次产出和消耗加在一起，所以如果存在环，它可以把之后产出的物品用来补充之前的需求。这意味着 CP-SAT 的输出可能是无法执行的。考虑这个环：

1x A <- 1x B
1x B <- 1x A

如果在没有库存的情况下想要 4 个 A，那么 CP-SAT 会认为 $𝑥 = [8, 4]$ 是合法的，这时 $𝐴$ 产出 4 个， $𝐵$ 产出 0 个。但从空库存出发，两个配方都无法执行。

所以 $𝐴 𝑥 \geq 𝑏$ 只是可达性的必要条件， $𝑥$ 还需要一个合法的执行序列。

容易想到的一点是，如果这个环从已有库存不可达，那么自然可以剪去，我们自然也这么做了。然而，这忽略了一点：即使环可达，CP-SAT 也不会规划为它点火的路线，而是单纯地让环自己补足自己，因为这样通常更赚。

所以我们必须再检查一次求解器的计划。我们建立一张仅由配方构成的图，如果配方 $𝑟$ 消耗 $𝑝$ 的产出，那么就从 $𝑟$ 往 $𝑝$ 建一条边，然后对 SCC 缩点，形成 DAG。而 DAG 一定是可行的，所以只需要判断 SCC 可以利用库存和已经拿到的净产出来启动循环。DAG 上的传播使用贪心的方式，而 SCC 则是普通的搜索，通常都很小。

它不具有完备性，因为贪心本就不完备，而且就算不能通过这个规划启动环，也还可能存在一个其他的可行规划。所以如果失败，我们只会返回 CYCLE_UNFULFILLED，也就是推测无解，但未证明。

8.2 启动切断

我们可以预先排除一部分环路情况。

考虑一组配方 $𝑅$ 。我们需要给每个环 $𝑅$ 一套布尔变量 $𝑠_{𝑟}$ ，表示配方 $𝑟$ 是其中最先启动的那一个。写成约束的话：

𝑥_{𝑟} \geq 𝑠_{𝑟}, 𝑥_{𝑟} \leq {dom}_{𝑟} \sum_{𝑝 \in 𝑅} 𝑠_{𝑝}, gross (𝑟, 𝑖) 𝑠_{𝑟} \leq {stock}_{𝑖} + \sum_{𝑘 \notin 𝑅, {net}_{𝑘 𝑖} > 0} {net}_{𝑘 𝑖} 𝑥_{𝑘}

其中 $gross (𝑟, 𝑖)$ 是配方 $𝑟$ 的输入量。在收支矩阵中，我们存储的是输出减去输入的结果，但在这里我们只需要真正的输入量。不过， ${net}_{𝑘 𝑖}$ 是配方 $𝑘$ 对 $𝑖$ 的净输出，的确是输出减去输入的。这是因为要启动 $𝑟$ ，我们输入量一定不能超过存货加其他配方的净输出。我们将最后一项称作 $avail (𝑖)$ ，也就是物品 $𝑖$ 的可用量。

这里考虑的 $𝑅$ 虽然对任何配方集合都有效，但有用的主要是净产出的一元环和二元环。

以及，单独一对配方上的约束经常能被其他配方满足，比如说 tag 的合成：配方 $𝑃$ 消耗 tag 节点、产出 tag 的全部成员，而每个成员各有一条 tag 边 $𝑇$ 把成员变回 tag 节点。这时 $(𝑃, 𝑇)$ 这个二元环上的约束总可以由另一个 tag 元素来满足，尽管实际上这样来的配方也执行不了。所以真正要切的组不是一对，而是互相消耗关系的连通分量，一般就是所有的 tag 元素。

目前的切断方式仍然是不完备的。考虑配方

A x64 <- B x16
B x1 <- A x1

如果库存仅有 8 个 A，约束是可以满足的，因为启动一轮只需要 $1$ 个 $𝐴$ ，但第二、第三轮攒不够 $16$ 个 $𝐵$ ，模型仍然会返回执行不了的计划。

8.2.1 虚拟物品

为了解决上面提到的问题，我们考虑了引入虚拟物品。以这套配方作为例子：

# 环
A x64 <- B x16
B x1 <- A x1
# 种子
A x1 <- C x1
B x1 <- D x1

这个环需要 16 个 A 或者 16 个 B 才能无限运行。所以，直觉告诉我们可以额外加入两个新的配方，它们的 cost 变为原本的 16 倍：

A x16 + S x1 <- C x16
B x16 + S x1 <- D x16

引入一个额外变量 $𝑦 = min (𝑥_{1}, 𝑥_{2})$ ，也就是环整体所运行的次数。在 CP-SAT 中，这次的约束就是 $𝑦 > 0 \Rightarrow 𝑆 > 0$ 。

然而，这样做其实是不对的。如果只有 7 个 A 和 9 个 B，其实这个循环也是可以启动的。所以，我们没有真正引入物品 $𝑆$ ，而是使用了一个类似的方式。

设配方为

𝐴 : 𝑝_{1} \times 𝑓 \leftarrow 𝑞_{1} \times 𝑒, 𝐿

𝐵 : 𝑝_{2} \times 𝑒 \leftarrow 𝑞_{2} \times 𝑓, 𝑇

如果环启动了至少一次，而且在第一次启动 $𝐴$ 之前，已经执行了 $𝑚$ 次 $𝐵$ ，那么就有 $𝑚 𝑞_{2} \leq avail (𝑓)$ 。这是因为 $avail (𝑓)$ 是外界能提供的 $𝑓$ 总量，而既然 $𝐴$ 没有启动，那么 $𝑓$ 只能从外界输入。

同样，为了能够启动 $𝐴$ ，我们必须有 $𝑝_{1} \leq avail (𝑒) + 𝑚 𝑝_{2}$ 。既然我们无法得到 $𝑚$ 的值，就应该尝试消去 $𝑚$ 。这也算是一步 Fourier-Motzkin，总之可以得到

\frac{𝑝_{1} - avail (𝑒)}{𝑝_{2}} \leq 𝑚 \leq \frac{avail (𝑓)}{𝑞_{2}}

既然所有东西都是正的，我们会有

𝑞_{2} 𝑝_{1} \leq 𝑞_{2} avail (𝑒) + 𝑝_{2} avail (𝑓)

同样的，如果在第一次启动 $𝐵$ 之前已经启动了 $𝑚$ 次 $𝐴$ ，我们自然可以写出对称的式子：

𝑞_{1} 𝑝_{2} \leq 𝑞_{1} avail (𝑓) + 𝑝_{1} avail (𝑒)

它们就是在 $min (𝑥_{1}, 𝑥_{2}) > 0$ 的情况下必须要满足的条件。