知识卡片
蓄水池一次均匀选节点
未知总长度时,保留一个候选:第1项直接入选,第k项以1/k概率替换。遍历N项后,任一项最终保留概率都是1/N,无需先计数。替换判断要实现离散概率;原书random_uniform后等于0的写法不能按连续分布照搬。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 遗传编程 4.1.9 蓄水池采样 · 查看原书依据
蓄水池采样提供了一个很好的解决方案。你从拜访每个人开始,然后在拜访每个人时保留一个候选人。你拜访的第一个人成为第一位候选人。当你拜访第二个人时,你会生成1~2的一个随机数。如果该数字为1,则第二个人将成为新的候选人,第二
参考来源
- 位置:《人工智能算法(卷2):受大自然启发的算法》第4章《遗传编程》,原书小节“4.1.9 蓄水池采样”(来源项目a19c7933-4eda-4176-aebd-30fe7e1ad292;源文件:extracted/人工智能算法(卷2):受大自然启发的算法/_epub-src/OEBPS/Text/chapter004.html#nav_point_73)
- 结论依据:原文逐人举例1/2、1/3替换并给出树遍历实现;均匀性来自该替换规则,未写成实验频率。
- 原始内容:蓄水池采样提供了一个很好的解决方案。你从拜访每个人开始,然后在拜访每个人时保留一个候选人。你拜访的第一个人成为第一位候选人。当你拜访第二个人时,你会生成1~2的一个随机数。如果该数字为1,则第二个人将成为新的候选人,第二