排多米诺骨牌的最佳策略

KeyTo9_Fans · 发表于 2021-8-25 11:17:12

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

我在排多米诺骨牌的时候，老是还没全部排完，就不小心把其中一块碰倒了。

不巧的是，这一块倒的方向恰好朝向已经排好的那些骨牌，

所以一块倒了全都倒了，所有的骨牌都要重新排一遍。

所以要想把成千上万张骨牌全都排好，几乎不太可能。

后来想到了分段排列+归并的方法，才有较大的概率给它们全部排好。

#####

现在假设我有$n$块多米诺骨牌要排成一行，

一开始这$n$块骨牌都是以“倒下”的状态排成一行的，例如$n=7$的初始状态为：

【倒下】【倒下】【倒下】【倒下】【倒下】【倒下】【倒下】

我希望用最少的操作次数，把它们全都变成“立起”的状态，也就是这个状态：

【立起】【立起】【立起】【立起】【立起】【立起】【立起】

对于每一次操作，我都可以从中选择一块倒下的骨牌，把它立起。

但这个“立起”操作会有一定的概率失败，具体的概率大小如下：

立起成功的概率为$1/2$；

立起失败且向左倒下的概率为$1/4$；

立起失败且向右倒下的概率为$1/4$。

倒下的骨牌会引起连锁反应，把一段连续的骨牌碰倒，

直到遇到一块本来就是“倒下”的骨牌，这个连锁反应才会结束。

例如，当我们在这个状态：

【立起】【立起】【倒下】【立起】【立起】【倒下】【立起】

选择立起第3块骨牌，但是立起失败了，它向右倒下，

那么我们就会去到这个状态：

【立起】【立起】【倒下】【倒下】【倒下】【倒下】【立起】

也就是第3块骨牌如果向右倒下，就会碰倒第4块、第5块立起的骨牌，

直到遇到了第6块本来就已经是倒下的骨牌，这个连锁反应才会停止，使得第7块立起的骨牌幸免于难。

我希望用最佳的策略进行立起操作，使得这$n$块骨牌都立起来所需的操作次数的期望值最小。

问：我应该如何操作？这个最小的期望值$E(n)$是多少？

KeyTo9_Fans · 发表于 2021-8-25 15:53:10

用时间复杂度为$O(n^3*2^n)$、

空间复杂度为$O(2^n)$的算法，

暴力求解每一种状态的最佳策略，

可以得到$n=0$到$n=20$的结果如下：

n E(n)
0 0.000000
1 2.000000
2 5.000000
3 8.000000
4 12.500000
5 17.000000
6 21.500000
7 26.000000
8 32.750000
9 39.500000
10 46.250000
11 53.000000
12 59.750000
13 66.500000
14 73.250000
15 80.000000
16 90.125000
17 100.250000
18 110.375000
19 120.500000
20 130.625000

复制代码

然后将$n=0,1,3,7,15$的结果单独拿出来看，

对应的$E(n)$的值分别是：$0,2,8,26,80$

这个数列是 http://oeis.org/A024023

由此可以猜出，将$n$个多米诺骨牌排好，需要$O(n^1.585)$次操作，

里面的指数$1.585=ln(3)/ln(2)$。

具体的操作方法如下：

最中间的骨牌先不立，按照$\lfloor n/2\rfloor$的解法操作两次，把左右两边的$\lfloor n/2\rfloor$块骨牌立好：

【立起】……【立起】【倒下】【立起】……【立起】

然后再成功立起中间的骨牌即可，若不幸失败，则重新把倒下的那边的$\lfloor n/2\rfloor$块骨牌立好，即可再次尝试立起中间的骨牌。

所以立起$n$块骨牌所需的操作次数为

$E(n)=2*E(\lfloor n/2\rfloor)+1+1/2(E(\lfloor n/2\rfloor)+1+1/2(E(\lfloor n/2\rfloor)+1+1/2(E(\lfloor n/2\rfloor)+1+......)))$

$=3*E(\lfloor n/2\rfloor)+2$

$=3^{log_2(n)}-1$

$=n^{ln(3)/ln(2)}-1$

于是【成功概率，左倒概率，右倒概率】=【$1/2$，$1/4$，$1/4$】的情况就解决了。

接下来好像就可以把【成功概率，左倒概率，右倒概率】这三个参数值改一改，

看看会出现什么有趣的数列了。

账号		自动登录	找回密码
密码			欢迎注册

[原创] 排多米诺骨牌的最佳策略

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。