【概率问题】洗属性问题

哈耶克

BeerRabbit 发表于 2013-8-24 10:52
1、如果三个事件是互斥的，那么就是以前讨论过的单掉落套装收集问题，我记得你曾经也发过一个英文文档Cou ...

从楼主的问题来看，应该是独立的

它的难点在于，属性是从0增加到199（更一般的是n）。而套装收集类问题，不过是从0增加到1.因为这一点引入了额外的复杂度，处理起来才特别麻烦

BeerRabbit

我曾考虑过“套装中第i个单件的目标收集数目为n_i”的情况，有个文档你可以看看
【单掉落装备套装收集加强问题】.pdf (519.88 KB, 下载次数: 523)

2013-8-25 11:05 上传

点击文件名下载附件

LZ的意图如果是独立的，那么在仍旧可以沿用单掉落的思路，只不过需要稍作修改。

哈耶克

文档里的递推公式是个好方法。但问题在于，需要的储存空间是很大的，算法复杂度也低不了哪儿去。如果是楼主的问题，需要建立一个矩阵F(i,j,k)(0<i,j,k<=200)，元素个数为200^3=8,000,000.递归次数大约也是这个数字。可以试验一下，通常的机子恐怕内存都不够用。

daofeng

BeerRabbit 发表于 2013-8-25 11:05
我曾考虑过“套装中第i个单件的目标收集数目为n_i”的情况，有个文档你可以看看

你这个pdf里面的递归感觉有点问题。。。f(x,0,0)的时候如果简单的用x/px来算期望，那就是其他数量已经够的单件装备都不再掉落了，你的问题应该不是这样的吧。

daofeng

哈耶克 发表于 2013-8-25 23:17
文档里的递推公式是个好方法。但问题在于，需要的储存空间是很大的，算法复杂度也低不了哪儿去。如果是楼主 ...

他这个复杂度是o(n^4)，计算每一个的值还有层循环。。。百万量级的时间和空间都不是问题

BeerRabbit

daofeng 发表于 2013-8-26 13:20
你这个pdf里面的递归感觉有点问题。。。f(x,0,0)的时候如果简单的用x/px来算期望，那就是其他数量已经够 ...

目标集合只有一个元素，显然此元素出现n次，平均需要实验n/p次。其他事件是否发生已然不重要、没影响。

daofeng

BeerRabbit 发表于 2013-8-26 13:28
目标集合只有一个元素，显然此元素出现n次，平均需要实验n/p次。其他事件是否发生依然不重要、没影响。 ...

嗯，如果只剩一个，n/p应该ok的。。。f(x,y,0)呢？

BeerRabbit

daofeng 发表于 2013-8-26 13:34
嗯，如果只剩一个，n/p应该ok的。。。f(x,y,0)呢？

f(x,y,0)=f(x,y)
之所以把单个元素的情况拿出来，是因为他们是整个“超长方体”的“边”

daofeng

好吧，f(x,y,0)也没啥问题

pdf里面的公式没有覆盖代码的所有逻辑吧，比如f(x,y,0) 当成f(x,y)计算的时候，sigma(pi)就变化了，同时累加里面也不再加n3这层。其实还是pi变成0了，也就是当某个ni=0的时候，pi就变成了不掉落的概率的一部分。

BeerRabbit

daofeng 发表于 2013-8-26 16:27
好吧，f(x,y,0)也没啥问题

pdf里面的公式没有覆盖代码的所有逻辑吧，比如f(x,y,0) 当成f(x,y)计算的时候， ...

对，文字部分的确没有完全详细说明，窃以为能看懂代码的话，比看文字的效果更好。