拉密数字牌(2)-性能优化

一、背景

之前介绍了《拉密数字牌》的游戏规则，以及我做了一个网站来计算答案。

当时遗留两个问题：

问题1：遗漏了“百搭”牌。
问题2：算法复杂度比较高，牌数较多时，几乎计算不出结果。

所以，我便思考怎么去优化，最终找到一种优化算法。
原先 10 分钟都无法跑出来的数据，现在可以在 1 秒内计算出结果。
实际上任何输入都可以在 1 秒内计算出来了。

二、问题回顾

游戏规则如下：

规则1：所有牌共有四个颜色，每个颜色的数字是 1 到 13，每个颜色的相同数字至多两个（两副不含大小王的纸牌）。
规则2：顺子，颜色相同，数字连续，至少 3 张，至多封顶为 13 张。
规则3：对子，数字相同，颜色不同，至少 3 张，至多封顶为 4 张。

问题：给 N 张牌，问是否可以拆分为若干组，每组都是顺子或对子。

暴力算法：指数级复杂度，不可行。

分组优化：枚举对子，剩余的四种颜色分别判断是否可以组成顺子。
枚举对子复杂度：O(21^13)
相同颜色判断：可以 DP 预处理计算所有合法值，O(1)判断。

上次发布的网站就是使用分组优化来实现的。
N 较小时，很快就可以计算出答案。
N 变大时，就会跑的比较慢，甚至 1 分钟还跑不出来。

二、时间优化

之前的分组优化之所以很慢，是由于是 DFS 枚举的，复杂度是指数级的。
对于这类问题，最经典的做法是动态规划。

我的想法很简单，每次从牌池里选择一个对子或顺子，剩余的牌就是一个状态。

为了方便标记状态，规定每次选择必须包含最大的数字。

另外，可以发现，对于顺子长度为 6 时与两个长度为 3 的顺子等价。
所以顺子我们只需要选择长度为 3、4、5 即可。

由此可以得出一个最重要的结论：选择一个含最大数字的顺子或对子时，可能影响的数字范围是 [n-4, n]。

我们最终可以写出一个最初级的状态：f(n, p1, p2, ..., p20)

没看错，状态有 21 个参数，是一个 21 维的数组。
如上图，假设处理到数字 11， 红框圈起来的 20 个数字都可能被影响，都是状态。
p1, p2 值的含义是当前这 20 个数字分别使用了多少个数字。

举一个例子，假设 p1,p2,p3 分别代表黑色数字 11、黑色数字 10、黑色数字 9 使用的个数。
如果这三个数字在牌池里的剩余个数都大于 1，我们就可以选择组成一个长度为 3 的顺子。
此时状态转化为：f(n, p1+1, p2+1, p3+1, ...)

由于这个算法每次选择的对子或顺子都包含最大数组 n，当所有颜色的数字 n 剩余个数都是 0 时，状态就可以转移到 n-1了。

21 维数组，想象都可怕，所以我们需要进行继续优化。

分析相同颜色的数字，可以发现相同颜色的数字只能选择顺子。

还是以 (p1,p2,p3,p4,p5) 为例，代表黑色数字 11 之前的 5 个数字。
当 p3 是 1 时，p2 和 p1 至少是 1，不可能为 0。 解释：p3 为 1，代表存在一个 11 到 p3 的顺子，这个顺子必然经过 p1、p2、p3。
这意味着 p1 到 p5 保持单调性。

由于每个数字最多是 2，所以 p1 到 p5 是从 2 到 0 的单调递减序列。
这个单调序列可以使用两个顺子的边界代表，即(l,r)。
[n, l) 代表这个区间的数字是 2。
[n, r)代表这个区间的数字是 1。

这样 21 维数组可以压缩为 9 维数组。

状态：f(n,l1,r1,l2,r2,l3,r3,l4,r4)
n 的取值范围是[0,13)
l 和 r 的取值范围是 [0, 6)
所以状态个数是 O(13 * 6^8)

对于最大数字，可以规定颜色也需要按顺序来选择。
则可以确定，每个颜色可以枚举的子状态最多不超过 7 个。

所以时间复杂度是：O(7 * 13 * 6^8)
当然，只有第一个颜色是 7 个子状态，第二个颜色是 4 个子状态，剩余的都是 3 个子状态。

这个算法上线后，任意输入的数据都可以计算出来了，耗时都是 3 秒多。
后来我发现，即使是最简单的输入，耗时也是 3 秒多。

三、内存优化

面对所有查询都是 3 秒这个问题，我分析之后判断是状态的内存初始化导致的。

于是内存做了标记，第一次申请之后，之后都复用内存。
由此，除了第一次查询，之后的查询都是 1 秒之内了。

第一次申请内存之所以慢，是因为申请的内存大。
所以我再次对状态进行有优化。

回头看下状态
状态：f(n,l1,r1,l2,r2,l3,r3,l4,r4)

l1 和 r1 其实也有大小关系的，即 l1<=r1。
对于这个关系，显然可以发现有一小半内存没有使用的。
四个数字就是有 15/16 的内存是没有使用的。

也就是这个做了优化，内存可以降低为原来的 1/16。

于是我就合并 (l1,r1) 为一个维度。
状态修改为f(n, lr1, lr2, lr3, lr4)
空间复杂度：f(13 * 21^4)

这样计算下来，内存降低了 1/8。

这个优化发布后，任何查询都可以瞬间计算出结果了。

四、最后

到目前位置，这个游戏在算法层面已经没有问题了。

接下来还需要增加两个“百搭”牌，周末有时间了再增加吧。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code