娱乐 不妙的数学算法挑战

[mamamama]

题面背景虚构仅供娱乐

mama 最近在凹一个无良制作人做出来的奇怪游戏。其中有一个地城的地图如图所示，

有一座起始之岛和一座结束之岛以及十二座浮岛，岛屿间通过浮桥连接（包括连向起始之岛和结束之岛的桥）

mama 只要成功从起始之岛走到结束之岛就可以胜利通关

每次进入地城的时候，就会重新生成一次地图，岛屿都在原本的位置，但每座浮桥只有50%的概率存在（彼此独立判定）

为啥说制作人无良呢，因为制作人就是粗暴地设置了一个出现概率，而没有保证一定能通关

那么 mama 好奇一个问题，对于这样一个随机生成的地城，可以通关的概率是多少？

我知道写个程序一瞬间就可以暴力枚举完，但是我画个更大的地图会快乐吗

第一次发帖发点红包（这……这还是第一次啊

十二月 15, 2021，由mamamama修改

[苍云静岳]

...你这画有问题吧，这不管是算节点还是算地块都是12个浮岛，不是九个啊~

[mamamama]

28 分钟前, 苍云静岳 说道:

...你这画有问题吧，这不管是算节点还是算地块都是12个浮岛，不是九个啊~

不小心打错了

[抹消思绪]

比起这个我好奇另一个问题，已知某个浮桥状况时如何快速确定是否连通，包括数据表示和算法。

[mamamama]

2 分钟前, 抹消思绪 说道:

比起这个我好奇另一个问题，已知某个浮桥状况时如何快速确定是否连通，包括数据表示和算法。

直接维护所有的连通集合，初始时每个岛对应一个集合，依次把存在的边两侧的集合合并就行（如果是同一个集合就不用处理了）

最后会得到若干个集合，在同一个集合里的点就是互相连通的

[苍云静岳]

56 分钟前, mamamama 说道:

不小心打错了

因为量级比较小，建议考虑以下解法：

求和：缺12块的概率（1/2^12）*已知缺12块基础上可通关的条件概率（0）+缺11块的概率*缺11块可通关的概率+...+缺0块的概率*缺0块可通关的概率（1）

缺12/11/10/9块通关条件概率为0，缺0/1/2块通关条件概率为1。剩下345678的摆摆基本都有规律的。

具体的懒得算了。

另一个思路是从3*1到3*2一直到3*4考虑这个问题（3*n）的通解，具体的也懒得算了。

[MIKO]

作为外行就不班门弄斧了

不知道有没有大佬能搞出来非蒙特卡洛的纯概率解法

[Ayachi Ning]

25个浮桥，至少要4个浮桥升起才能连通

说实话我也只会暴力枚举

[抹消思绪]

1 小时前, mamamama 说道:

直接维护所有的连通集合，初始时每个岛对应一个集合，依次把存在的边两侧的集合合并就行（如果是同一个集合就不用处理了）

最后会得到若干个集合，在同一个集合里的点就是互相连通的

学到了。

[mamamama]

1 小时前, 苍云静岳 说道:

因为量级比较小，建议考虑以下解法：

求和：缺12块的概率（1/2^12）*已知缺12块基础上可通关的条件概率（0）+缺11块的概率*缺11块可通关的概率+...+缺0块的概率*缺0块可通关的概率（1）

缺12/11/10/9块通关条件概率为0，缺0/1/2块通关条件概率为1。剩下345678的摆摆基本都有规律的。

具体的懒得算了。

另一个思路是从3*1到3*2一直到3*4考虑这个问题（3*n）的通解，具体的也懒得算了。

分类讨论或者容斥确实是个不错的思路

不过……

3 小时前, mamamama 说道:

我画个更大的地图会快乐吗

 

[苍云静岳]

56 分钟前, mamamama 说道:

我画个更大的地图会快乐吗

那就是另一个思路咯。

考虑m*1的地图，通关概率是1-1/2^m

考虑m*2的地图，若m*1的地图不通关，则必不能通关；若m*1的地图能通关，那么【这块计算有点麻烦跳过】，总之在此条件下通关概率为p。那么m*2的地图通关概率为(1-1/2^m)*p

考虑m*n的地图，若m*(n-1)的地图不通关，则必不能通关；若m*(n-1)的地图能通关，我猜再次条件下通关概率也是p，因为感觉这是不失一般性的，那应该用归纳法能给出一个通项公式吧。

[mamamama]

2 小时前, 苍云静岳 说道:

那么m*2的地图通关概率为(1-1/2^m)*p

这个好像不太对呢，浮岛间的竖边也是会影响连通性的，如果硬要算的话要对 m 也递推会好点

首先把概率转成计数问题，最后除掉一个 2^边数 变回概率

假设 f(m) 是有 条竖边的时候没有连通的方案数，那么枚举最后有连续有 k 条竖边，这些浮岛要么全部向左连边要么全部向右连边

大概就是 2*2^(k+1)-1 这么多的方案数，因此应该是 f(m)=sum( f(m-k-1) * (2*2^(k+1)-1) )

可能有点细节或者边界错误之类的

如果再加一列的话只会变得更复杂，我感觉这样不太可做

 

另外

7 小时前, mamamama 说道:

画个更大的地图

这句话并不代表地图具有“一般性”哦，它依然是具有很强的特殊性的，所以建议还是从原图出发呢

我过几天如果没人解出来并且我还记得会再给点提示

[Muriya Tensei]

13 小时前, 抹消思绪 说道:

比起这个我好奇另一个问题，已知某个浮桥状况时如何快速确定是否连通，包括数据表示和算法。

算法的话，就是并查集了，把所有岛看做点，桥看做边，遍历所有的桥在并查集中合并其两侧的点，用并查集检查两端的节点是否属于同一个集合就行了

[fangaa]

我个人见到概率就头疼，所以想了个不需要算概率的取巧方法：
先定义f(x,y)是这个问题x行y列时的答案，那么楼主想要的答案就是f(4,4)。
然后假设有一艘体积极大的船自上而下想要通过，若两岛之间有桥则不能通过。那么人能通过和船能通过刚好互斥，正巧桥存在的概率都是50%，也就是说f(x,y)+f(y,x)=1。
那对于这个例子f(4,4)=0.5。

 

[mamamama]

31 分钟前, fangaa 说道:

我个人见到概率就头疼，所以想了个不需要算概率的取巧方法：
先定义f(x,y)是这个问题x行y列时的答案，那么楼主想要的答案就是f(4,4)。
然后假设有一艘体积极大的船自上而下想要通过，若两岛之间有桥则不能通过。那么人能通过和船能通过刚好互斥，正巧桥存在的概率都是50%，也就是说f(x,y)+f(y,x)=1。
那对于这个例子f(4,4)=0.5。

 

正解

[Muriya Tensei]

现在明白为什么数地块和数岛都是12了（左右黑色连通是与上下白色连通是互斥的）

 

所以对于任何x层浮岛，每层x+1座的情况下，黑白两种情况是等价等概率的

十二月 16, 2021，由Muriya Tensei修改

[fangaa]

3 小时前, mamamama 说道:

正解

那么长宽不等时怎么算呢。

[mamamama]

51 分钟前, fangaa 说道:

那么长宽不等时怎么算呢。

这个我也不会呢，这道题就是巧妙地使用对偶图与原图连通性互补性质

如果没有这个性质，计算的复杂度在我和站长的讨论中也提到了，是我不会的问题

[fangaa]

51 分钟前, mamamama 说道:

这个我也不会呢，这道题就是巧妙地使用对偶图与原图连通性互补性质

如果没有这个性质，计算的复杂度在我和站长的讨论中也提到了，是我不会的问题

啊，只能老老实实算了~

[aoisaki_ichika]

于 2021/12/16 于 AM10点00分, fangaa 说道:

我个人见到概率就头疼，所以想了个不需要算概率的取巧方法：
先定义f(x,y)是这个问题x行y列时的答案，那么楼主想要的答案就是f(4,4)。
然后假设有一艘体积极大的船自上而下想要通过，若两岛之间有桥则不能通过。那么人能通过和船能通过刚好互斥，正巧桥存在的概率都是50%，也就是说f(x,y)+f(y,x)=1。
那对于这个例子f(4,4)=0.5。

 

这么一想确实简单了好多……