随机抽样模型的两种算法设计与仿真(2)

人气指数:点发布时间:2014-04-21 21:22 来源：http://www.zgqkk.com 作者：姚佳

分享到：

　　3 筛除法随机抽样模型

　　约瑟夫问题（Issue of Joseph），有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。其通常算法模型为建立循环链表，称约瑟夫环（structure-Joseph），每间隔特定长度就将结点元素删除，直至剩下最后一个结点。以此为基础，形成筛除法随机抽样模型。

　　购买彩票已经成为人们生活当中一种娱乐性投资。10选3彩票系统，即在10个数字中，随机产生3个不同数字，单次中奖概率为[C310]。以此为模型，对筛除法随机抽样过程进行仿真。如图3所示，构造一个池，将所有数字标注于球上，放入池中，每次随机抽中一个，近似于“约瑟夫问题”，池中球逐次减少，算法执行过程中，不需要进行状态标记，且不会产生重复取样[[6-7]]。

　　图3 使用被抽取元素构造池

　　如图4所示，构造链表，每个节点存储一个不同数字的字符元素，头结点为空[[8][9]]。

　　图4 抽样元素链表

　　如图5所示，第一次执行r.nextInt（11）=3，（0为起始位，产生0-10的伪随机数，0位为链表头结点），抽中字符元素“03”，执行链表删除操作，并输出抽中元素，链表长度减少；

　　图5 第一次抽样操作

　　如图6所示，因链表长度减少，第二次执行r.nextInt（10）=6，（0为起始位，产生0-9的伪随机数，0位为链表头），抽中字符元素“07”，执行链表删除操作，同时输出抽中元素，链表长度继续减少；

　　图6 第二次抽样操作

　　如图7所示，因链表长度继续减少，第三次执行r.nextInt（9）=4，（0为起始位，产生0-8的伪随机数，0位为链表头），抽中字符元素“05”，执行链表删除操作，同时输出抽中元素，程序执行结束。

　　图7 第三次抽样操作

　　算法共执行三次操作，选出“03”、“07”、“05”三个元素。该算法的平均时间复杂度为[O（M）]，M为抽取样本数，在此仿真过程中M为3[[1，10]]。

　　4 算法特点与性能分析

　　如图8所示，为状态标记法和筛除法两种随机抽样方式的计算时间复杂度对照，状态标记法的平均时间复杂性与资源库元素数量有关，与被抽样元素规模无关。筛除法的平均复杂性与被抽样元素规模相关，与资源库中样本数无关。

　　利用筛除法进行随机抽样，算法执行简洁，易于理解，方便编程实现，且平均时间复杂度明显优于状态标记法，但是在执行过程中，由于资源库中抽样元素被提取，资源库的完整性和数据存储次序被破坏。

　　5 结束语

　　筛除法和状态标记法是利用计算机平台实现不重复抽样的有效方式，有广泛的实际应用价值。状态标记法抽样基于数组操作，能够在抽样过程中保持数据库的原始状态，适用于文献抽查、药品质量检验、工业产品质量抽检等多种领域。筛除法抽样基于链表实现，算法结构更紧凑，降低了计算时间复杂性，该算法执行中先建立数据资源库，数据提取完成后，资源库不再被重复使用，为一次性的操作，可应用于投资分析，风险评估，通信系统仿真中各种随机复杂噪声环境的构建等。

　　参考文献：

　　[1] 王军锋，贾建，申志伟.一种改进的随机抽样算法[J].电脑与信息技术，2006（2）：63.

　　[2] 杨刚.简单随机抽样中几个问题的探讨[J].许昌学院学报，2012（5）：22-23.

　　[3] 寿涌毅.并行工程项目调度的组合随机抽样算法[J].浙江大学学报，2006（2）：345.

　　[4] 寿涌毅.随机抽样算法在多项目调度中的应用[J].管理工程学报，2005（3）：32.

　　[5] 贺相春.基于WebService的学位论文抽检系统设计与实现[J].软件导刊， 2012（11）：46-49.

　　[6] 罗来鹏，刘二根.基于Apriori算法的彩票预测[J].决策参考，2007（3）：48-49.

　　[7] 洪晶，柳炳祥，程功勋.一种基于Apriori算法的彩票数字组合数据挖掘[J].福建电脑，2005（9）：92.

　　[8] 严蔚敏.数据结构（C语言版）[M]. 北京：清华大学出版社，2013

　　[9] 欧阳桂秀.Java语言程序设计[M].北京：高等教育出版社，2008

　　[10] 罗玉军.随机抽样改进算法及其实现[J].电脑与信息技术，2008（6）：27-28.

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。