娱乐 每 周 概 率 挑 战 【第一期】

[可洛]

概率全还给老师了www，干脆粗暴点跑个Monte Carlo拉倒了

以下：

剧透

没往多了跑，matlab模拟了十万次爬到顶。

根据上图：

题1：6 （之前手滑了打成5www）

题2：肯定有6www，再蒙个5吧

题3好像前面有人蒙出来了

题4比较麻烦不想做了，但思路基本上一致，比如题4，建立一个二维矩阵P_2(i,j)，P_2(i,j)是踩到i后又踩到j的概率（matlab里面我保留了原始跑台阶的数据，所以这个很容易做出来），然后P(i)从上图可得，解出P(i)*P(i,j)就好

题5和上题一致，建立一个二维矩阵后再建一个三维矩阵就好，一样的

五月 5, 2020，由可洛修改

[可洛]

1 小时前, yhz012 说道:

如果能跑蒙特卡洛的话，稍微调整一下就可以做成particle filter 粒子滤波，因为状态转移方式很简单。然后在这个基础上再调整一下其实就可以求精确解了，要来试试吗？

前面的思路是对的，不过这样求出来的是仅挖2个坑的结果，要怎么继续求出来另外3个坑挖在哪呢？

PF没学过www，就学过卡尔曼www

三个坑其实和两个坑是一样的，不过运算量会大很多。

我现有的矩阵是100,000*100的，以防万一扔出100个1....可以把出现过1的行集中一下，然后是出现2的...以此类推到100

重新整理出的矩阵会是100*100。这个是两个坑的矩阵

三个坑的情况需要整理原始矩阵两次。第一次先做出两个坑的矩阵，第二次的话，比如说一个踩了1阶又踩了2阶和3阶的情况：逐行扫，出现了1，出现了2，又出现3的情况就记录一下，以此类推....是个非常非常粗暴的方法...做出来会是一个100*100*100的矩阵。不过算这个的话跑10w次的sample好像不太够www

[可洛]

17 分钟前, yhz012 说道:

PF其实想法就是先抽样，比如说100,000个样本，然后转移一次。转移后根据限制条件砍掉不符合要求的样本。比如条件是走到了第i个台阶，那么把所有已经超过了i但是没踩过i上的样本直接删掉，再根据比例扩充样本。比如删完之后只剩下50,000个样本，那就把剩下的每个样本复制一个进来，从而恢复到100,000样本。然后继续做下一次转移

实际上可以理解为是带条件概率的蒙特卡洛

 

思路是对的，然后计算量嘛……会真的很大……至少我在服务器上如果跑100个台阶的情况跑20分钟没跑完……

 

稍微有一点问题的是，比如说题4的情况，参拜客有2条命，但是我有5个坑。对100*100的二维矩阵找最大值可以得到最佳的2个坑的位置，但是一共可以挖5个坑，还有3个坑应该挖在哪？

emmmm这个我还真不知道该怎么做了，理论上用一个5维的矩阵是可以的，但是计算量不是家用电脑可以考虑的。

或者在找到最佳两个坑之后模拟剩余情况？但坑的位置对结果会造成影响....可以试试对加入两坑之后的情况进行模拟，然后取概率最高的台阶加坑，再次模拟，再加坑，模拟，再加，看看如果后加的坑在先加的坑后面就没有影响，反之....那就重来吧

PF的部分我好像懂了...好麻烦QwQ

五月 6, 2020，由可洛修改

[可洛]

1 小时前, yhz012 说道:

在PF的基础上再调整调整，就可以避免抽样的情况，从而直接求概率值

用这个方式来建立5维矩阵是可以做的，不过，首先要猜一个上限，前面有人提40台阶作为上限，实际上其实可以比40台阶还能再少一些。（←但是这里我只是从实验结果来看的，没有证明）

先算了一次二维矩阵，现在来看两命挖两坑是6和12最优。接下来要细解的话可以考虑继续用蒙特卡洛。做法就是把踩到两坑（6和12）的人摘出去，根据接下来的结果加第三坑....

还有一个有趣的小结果，对于命多的人，最好的办法是每隔六个台阶加一坑...

五月 6, 2020，由可洛修改

[可洛]

7 小时前, yhz012 说道:

这个结果我在第五问似乎复现出来了，很有趣的现象，但是我不知道为什么会这样

标记一下等我糖重置之后补糖

其实是可以理解的，从起点开始，踩到6的概率最高，那接下来的任何一个被踩到的台阶都可以当做一个新的“起点”。基本上我是这么理解的