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

[Mr.K 018]

第一问跟楼上说的一样，设p[k]表示踏上第k个台阶的概率，dp一下取出最大的那个就行。

第二问我觉得可以把第一问的算法做修改，设p‘[k][j]表示在已知第k个台阶没有被踏上的情况下，第j个台阶被踏上的概率。这样，假设要在k,j位置挖坑，那么访客掉坑里的概率就是p[k]+(1-p[k])p'[k][j]。O(n^2)搞定

我觉得推广到埋n个坑的情况应该也差不多

如果在上文看到了i，请把它理解成k（

是否可以尝试证明用这种方法连续挖六个坑肯定能行呢？正在尝试，感觉能行

五月 5, 2020，由Mr.K 018修改

[Mr.K 018]

4 分钟前, yhz012 说道:

那么p'[k][j]要怎么求呢？

p'[k][j]求法跟p[k]差不多，唯一的区别是到p'[k][k]的值强行设为0，跟其他地方的运算规则不一样

同样的道理适用于p⁽ⁿ⁾[k]₁[k]₂⋯[k]_n

五月 5, 2020，由Mr.K 018修改

[Mr.K 018]

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

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

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

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

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

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

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

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

要解决以下几个问题：

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

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

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

---

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

五月 5, 2020，由Mr.K 018修改