排多米诺骨牌的最佳策略

KeyTo9_Fans

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

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

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

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

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

#####

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

KeyTo9_Fans

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

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

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

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

1.    n  E(n)
   
2.    0  0.000000
   
3.    1  2.000000
   
4.    2  5.000000
   
5.    3  8.000000
   
6.    4  12.500000
   
7.    5  17.000000
   
8.    6  21.500000
   
9.    7  26.000000
   
10.    8  32.750000
    
11.    9  39.500000
    
12.   10  46.250000
    
13.   11  53.000000
    
14.   12  59.750000
    
15.   13  66.500000
    
16.   14  73.250000
    
17.   15  80.000000
    
18.   16  90.125000
    
19.   17  100.250000
    
20.   18  110.375000
    
21.   19  120.500000
    
22.   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$】的情况就解决了。

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

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