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

[yhz012]

17 分钟前, 可洛 说道:

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

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

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

 

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

 

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

[可洛]

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，由可洛修改

[yhz012]

21 分钟前, 可洛 说道:

理论上用一个5维的矩阵是可以的，但是计算量不是家用电脑可以考虑的。

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

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

 

  

21 分钟前, 可洛 说道:

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

实际上坑在后面我觉得大概也会有影响？

比如现在挖了坑在5和6，然后求到新的坑在7。之前是只有踩了5和6才会死，但是现在变成了可以56、57、67三种情况了。仅仅第一个踩5，也多了一个情况要考虑了

五月 6, 2020，由yhz012修改

[applebird]

11 小时前, yhz012 说道:

精确解时间复杂度至少我现在手里能用的是O(n^5)级别。当然从结果反推，如果有一些证明，似乎可以压到O(1)不过常数项很大的级别

这个方法有一点问题

举例来说第一问答案是6，按照这个方法似乎只能找6之后的坑？但是实际上第二问答案是5、6

不是呀，是说去掉6之后6之前的概率不会变，6之后的发生了变化，因此重新求一下，最后选出最大的会发现是5

[yhz012]

2 分钟前, applebird 说道:

不是呀，是说去掉6之后6之前的概率不会变，6之后的发生了变化，因此重新求一下，最后选出最大的会发现是5

但是这样的话，最开始选6似乎就有问题了？

因为之所以最开始选6是因为6是没有坑的时候概率最大的

但是现在6前面有坑，所以6的概率也会变化？

 

数学一点的说法是最后答案是5和6，那么被坑的概率是P(5) + P(6 | not 5)，但是这里我们求的概率是P(5 | not 6) + P(6)，这两个是不等的

[applebird]

41 分钟前, yhz012 说道:

但是这样的话，最开始选6似乎就有问题了？

因为之所以最开始选6是因为6是没有坑的时候概率最大的

但是现在6前面有坑，所以6的概率也会变化？

 

数学一点的说法是最后答案是5和6，那么被坑的概率是P(5) + P(6 | not 5)，但是这里我们求的概率是P(5 | not 6) + P(6)，这两个是不等的

确实，但是这样应该可以在O（n）里面求出一个较为优的解？

[可洛]

1 小时前, yhz012 说道:

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

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

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

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

五月 6, 2020，由可洛修改

[yhz012]

58 分钟前, 可洛 说道:

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

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

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

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

[yhz012]

1 小时前, applebird 说道:

确实，但是这样应该可以在O（n）里面求出一个较为优的解？

我不太确定这个解的次优程度是否有界，如果证明有界的话，我觉得确实是不错的算法？

毕竟这个问题可以扩展成每次丢个n+1面骰子，然后挖n个坑，一共m个台阶，可以把复杂度从O(m^n)拉到O(m)，算是非常大的提升了

五月 6, 2020，由yhz012修改

[可洛]

7 小时前, yhz012 说道:

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

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

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

[yhz012]

11 小时前, 可洛 说道:

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

有道理！极端例子就是n个坑n条命，那么意味着每个坑都必须要踩，于是条件概率下新起点就和之前的起点是等价的了

[PhoeniXLL]

于 2020/5/5 于 PM8点11分, Mr.K 018 说道:

看大佬讨论问题，流下了不懂数学的泪水……

前三问都可以直接计算的，大不了O(n^5)嘛，有些情况下多项式时间已经不错了，参考我上午的回答和其他人的讨论

后面两问暂时没想出来有效的算法，因此考虑走个邪道：GA

先随机初始化n个解当作初始种群，然后迭代执行以下操作：

1. 对种群中的每个解打分

2. 按一定比例去掉打分最低的解。设去掉了n个解

3. 进行n次繁殖，补回去掉的解。繁殖方法可以是随机抽取两个解（解的评分越高，被抽中的概率也应越高），两个解的编码做适当的交叉互换，并按一定概率突变以后作为新的解加入到种群中。

重复以上迭代操作直至收敛或执行完了指定的轮数或时间为止。

要解决以下几个问题：

1)评分算法。考虑进行若干次模拟，统计因中陷阱而GG的情况的占比，作为评分。考虑到计算代价，模拟次数似乎不必做特别多，几十次就行？

2)解的编码。假设要挖出k个坑，考虑将每个坑的位置用一个整数表示。不必从小到大排列。

3)交叉互换和突变。考虑将交叉互换算法设置为：对每一个子代基因编码中的整数，均随机地从两个亲本的对应数字中抽出一个。如果出现重复数字，则将其中一个赋随机值。突变可考虑设置为将某一个数字赋上随机值。

---

这个算法不知道行不行得通，但是调参多半是没跑了

后两问和前三问没有本质区别，只不过是必须要踩的坑变多了而已吧

[PhoeniXLL]

49 分钟前, yhz012 说道:

有道理！极端例子就是n个坑n条命，那么意味着每个坑都必须要踩，于是条件概率下新起点就和之前的起点是等价的了

但是好像不太满足贪心，我记得我前天跑的2条命3个坑和2条命4个坑的时候不满足

五月 7, 2020，由PhoeniXLL修改

[yhz012]

1 小时前, PhoeniXLL 说道:

但是好像不太满足贪心，我记得我前天跑的2条命3个坑和2条命4个坑的时候不满足

2命5坑也不满足，不过3命5坑看起来比较容易出现这个效果

 

[yhz012]

15 小时前, 莫得姓名 说道:

莫非你就是魔鬼二号吗，隔壁一个算法挑战，现在又多一个概率挑战

我这边的问题还能挣扎一下的吧？隔壁算法挑战看着就超痛苦的啊（笑）