Alchemy Merge合成游戏最快通关算法与元素深度计算方案

我曾游玩一款名为 Alchemy Merge 的合成类游戏，核心玩法为组合不同元素生成新元素。游戏初始提供4种基础元素，即Air、Fire、Soil、Water，通过组合基础元素可逐步解锁新元素。我通关游戏时同步记录了所有元素的合成条目，示例如下：

Air
Fire
Soil
Water
Heat = Air + Fire
Plant = Soil + Water
Tree = Plant + Plant
Forest = Tree + Tree

……完整记录共包含约400个元素。现针对该游戏提出两个技术问题：

1. 能够以最少合成步骤完成全元素解锁、通关游戏的最快算法是什么？
2. 采用何种方案可以最小时间复杂度确定元素的depth（深度）？此处深度定义为获取目标元素所需的合成操作总次数。

深度计算基础示例：

depth(Water) = 0 # 基础元素
depth(Plant) = 1 # 由Soil + Water合成，仅需1次操作
# 深度计算追溯到基础元素即停止

补充深度定义规则示例：
已知合成公式 Algae = Plant + Water，获取Algae共需要2次合成操作：

1. 合成Plant：Plant = Soil + Water
2. 合成Algae：Algae = Plant + Water
   因此 depth(Algae) = 2。

再举一例，给定合成关系：

Stone = Soil + Soil
Sand = Stone + Water
Glass = Sand + Fire
Time = Glass + Sand

逆推计算depth(Time)的展开过程如下：

1. Time = Sand + Glass
2.        = (Stone+Water) + Glass
3.        = ((Soil + Soil) + Water) + Glass
4.        = ((Soil + Soil) + Water) + (Sand + Fire)
5.        = ((Soil + Soil) + Water) + ((Stone+Water) + Fire)
6.        = ((Soil + Soil) + Water) + (((Soil + Soil)+Water) + Fire)

最终可得 depth(Time) = 6。

问题1：最少步数全解锁算法 #

别想复杂了，这个问题的理论最少步数就是非基础元素的总个数——毕竟每个非基础元素你至少要合成1次才能解锁，不可能有比这个更少的步数。要刚好达到这个下限，用拓扑排序就完事了，步骤非常简单：

• 先把4个基础元素标记为已解锁，放进待处理队列
• 给每个非基础元素维护一个计数器，记录当前已经解锁的原料数量
• 每次从队列里拿出一个已解锁元素，遍历所有把它当原料的合成配方，给对应产物的计数器加1；如果某个产物的计数器凑到2（两个原料都解锁了），就把这个产物标记为已解锁，放进队列，同时合成步数加1
• 重复直到队列为空，所有元素就都解锁了

整个过程没有任何重复合成的无效操作，时间复杂度是O(N)，N是总元素数，对于400个元素的规模来说计算量可以忽略不计，是实打实的最优解。如果想优化实际操作的手感，少翻找元素列表，可以在选下一个合成目标的时候优先选后续依赖最多的元素，但总合成步数不会变。

问题2：最小复杂度计算元素深度 #

很多人第一反应会写递归逆推、记忆化搜索，其实完全没必要。先看你给的深度定义：把元素完全拆解成基础元素时，所有合成操作的总计数。这个定义刚好满足一个非常简单的递推关系：

基础元素的depth = 0
对合成元素 X = A + B，depth(X) = depth(A) + depth(B) + 1

你可以套所有给的例子验证：

• depth(Plant) = 0 + 0 +1 =1，符合示例
• depth(Algae) = depth(Plant) + depth(Water) +1 =1+0+1=2，符合示例
• depth(Stone)=0+0+1=1，depth(Sand)=1+0+1=2，depth(Glass)=2+0+1=3，depth(Time)=3+2+1=6，和你逆推展开算的结果完全一致。

所以计算深度根本不需要展开递归树，直接顺着拓扑排序的顺序算就行：处理每个非基础元素的时候，它的两个原料的depth肯定已经算完了，直接套公式赋值就可以。整个过程只需要遍历所有元素一次，时间复杂度O(N)，是理论上的最优复杂度——毕竟你至少要把每个元素的配方读一遍，不可能比这个更快。
这里要特别注意别和DAG最长路径搞混：最长路径算出来的Time深度是4，那是“合成链的最长层数”，和你定义的“总合成操作次数”不是一个规则，别套错公式就行。

内容的提问来源于stack exchange，提问作者Amlan Saha Kundu