排多米诺骨牌的最佳策略
我在排多米诺骨牌的时候，老是还没全部排完，就不小心把其中一块碰倒了。不巧的是，这一块倒的方向恰好朝向已经排好的那些骨牌，
所以一块倒了全都倒了，所有的骨牌都要重新排一遍。
所以要想把成千上万张骨牌全都排好，几乎不太可能。
后来想到了 分段排列+归并 的方法，才有较大的概率给它们全部排好。
#####
现在假设我有$n$块多米诺骨牌要排成一行，
一开始这$n$块骨牌都是以“倒下”的状态排成一行的，例如$n=7$的初始状态为：
【倒下】【倒下】【倒下】【倒下】【倒下】【倒下】【倒下】
我希望用最少的操作次数，把它们全都变成“立起”的状态，也就是这个状态：
【立起】【立起】【立起】【立起】【立起】【立起】【立起】
对于每一次操作，我都可以从中选择一块倒下的骨牌，把它立起。
但这个“立起”操作会有一定的概率失败，具体的概率大小如下：
立起成功的概率为$1/2$；
立起失败且向左倒下的概率为$1/4$；
立起失败且向右倒下的概率为$1/4$。
倒下的骨牌会引起连锁反应，把一段连续的骨牌碰倒，
直到遇到一块本来就是“倒下”的骨牌，这个连锁反应才会结束。
例如，当我们在这个状态：
【立起】【立起】【倒下】【立起】【立起】【倒下】【立起】
选择立起第3块骨牌，但是立起失败了，它向右倒下，
那么我们就会去到这个状态：
【立起】【立起】【倒下】【倒下】【倒下】【倒下】【立起】
也就是第3块骨牌如果向右倒下，就会碰倒第4块、第5块立起的骨牌，
直到遇到了第6块本来就已经是倒下的骨牌，这个连锁反应才会停止，使得第7块立起的骨牌幸免于难。
我希望用最佳的策略进行立起操作，使得这$n$块骨牌都立起来所需的操作次数的期望值最小。
问：我应该如何操作？这个最小的期望值$E(n)$是多少？ 用时间复杂度为$O(n^3*2^n)$、
空间复杂度为$O(2^n)$的算法，
暴力求解每一种状态的最佳策略，
可以得到$n=0$到$n=20$的结果如下：
nE(n)
00.000000
12.000000
25.000000
38.000000
412.500000
517.000000
621.500000
726.000000
832.750000
939.500000
1046.250000
1153.000000
1259.750000
1366.500000
1473.250000
1580.000000
1690.125000
17100.250000
18110.375000
19120.500000
20130.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$】的情况就解决了。
接下来好像就可以把【成功概率，左倒概率，右倒概率】这三个参数值改一改，
看看会出现什么有趣的数列了。
页:
[1]