自动编成问题(2)

无附加限制 + 有相互作用deck

上文说了穷举法只是一个“简单的想法”，缺点在于代价太大。
那么对于这类deck的自动编成问题应该如何解决呢？

首先可以考虑的是经过剪枝或缩小了检索范围的穷举法。

• 优点是简单容易实现
• 缺点是算法效果直接受到性能要求的限制，不得不牺牲精度。

举个例子：在计算编成之前，可以事先“剔除”一些“不太可能”是最优配置的成员。

其实不一定要使用穷举法，思路可以放得更开阔一点。

之所以这类问题无法使用动态规划或贪心算法，是因为“相互作用”的存在。 简单来说，就是“直到将所有角色都配置好才可以知道他们的攻击力是多少”这一点。

那么，是不是可以通过解决这个特征使得问题简单化呢？

其实在这里定义的“相互作用”的本质就是攻击力的一部分。 尽管这个值是可以变动的，但是能够变动的区间总是有限的。 既然区间有限并且可能性其实也不多，那么其实可以考虑将相互作用“换算”成攻击力计算的方法。 这样，经过换算之后，我们在全部配置完成之前就可以“知道”这个角色的攻击力值。 这个问题就转换成为了第一类问题，可以直接用贪心法解决。

关于预处理

那么如何进行预处理呢？
这里提供一个最基本的思路——攻击力的期望值。

我们首先定义一个角色的实际攻击力期望值，这个值是角色的基本攻击力+可能的攻击力加成之后的结果。
形式化的定义为：

E(A) = A * (加成1 * 加成1发动概率 + ... + 加成n * 加成n发动概率)

其中：
	加成i的发动概率 = 发动加成i的编成种类数 / deck编成可能种类总数

经过处理之后，每个角色的攻击力A转化为E(A)，直接用贪心法就可以得到结果。

其实预处理时间代价也并不低，但是由于和计算编成的过程是分开的，因此可以放到线下计算。

预处理方法也存在精度问题：玩家手中的配置常常会优于期望值，因此计算出来的攻击力常常是被“低估”的。
要解决这个问题无外乎调整期望的计算公式或者加入其他的调整参数，这里不再赘述。

有附加限制 + 有相互作用deck

这是最复杂的一种情况。不过解决思路于上一种无异。 对于相互作用可以用预处理的评估方法保证无后效性；这样就转化为“有附加限制 + 无相互作用”一类的问题。 接下来大家都知道该怎么做了。

总结：

• 对于限制不是很严格的情况，考虑到实现的复杂度，可以使用穷举法或者经过优化的穷举法。
• 可以用期望将无法事先计算的加成效果换算为攻击力以简化问题。
• 将线上计算转移到线下是一种常用的优化手段。
• 期望可以反映一些问题，但是往往不会很精确。
• 实践中的问题往往可以通过“破坏、创造条件”的方法简化问题的复杂性，当然前提是不能够违背核心需求。