统计问题的概率算法研究

《统计问题的概率算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1本课题所涉及的问题在国内(外)的研究、应用现状综述1976年雷兵提出了概率算法，它不同于一般算法，其新颖之处是把随机性注入到算法中，使得算法设计与分析的灵活性及解决问题的能力大为改观，这种算法曾一度运用在密码学，数字信号，数字简化信号和大系统的安全及故障容差中得到应用。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。在科学和工程实践中,很多优化问题需要同时满足几个不同的目标,而这些目标之间往往是相互约束、相互冲突的,这类问题被统称为多目标优化问题(简称MOP)

2、。在现实生活中,很多重要的决策同样面临着多目标优化的难题,如城市运输、水库管理、城市规划、能源分配等。所以在对许多应用领域，特别是音频或视频处理等领域，最后的结果是有多个满足条件的数，即没必要追求最高精度，只要误差很小，因此其影响也就小了。所以多选择问题的概率算法研究很有意义。目前的拉斯维加斯算法的一个显著特征是他所作的随机性决策，虽然这有可能导致算法找不到所需的解，但用一个bool型函数表示拉斯维加斯型算法。当算法找到一个解时返回ture，否则返回false，拉斯维加斯算法的典型调用形式为boolsuccess=LV（x，y）；

3、其中x是输入参数；当success的值为true时，y返回问题的解，当success为false时，算法未能找到问题的一个解，此时可对同一实例再次独立地调用相同的算法；n后问题是一个古老而著名的问题，该问题为我们提供了设计高效的拉斯维加斯算法的很好的例子，对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此容易想到拉斯维加斯算法，我们在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。

4、我们可用回溯法解这个问题。此外从蚁群算法中专家得到启示：将信息素的观点引入到求解组合优化问题的演化算法之中,提出了一种基因优化算法.该算能学习劣解的基因,并用信息熵作为结束条件的判据.最后解决了两个典型的组合优化问题,也取得了较好的结果。型的组合优化问题,也取得了较好的结果。1本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析。关键问题：首先生成一定量的随机数，用经典多选择算法对多个数值进行选择，挑选出满足条件的数；其次用概率统计知识改进经典多选择算法，提高速度及降低复杂度，使之更快更准确的选择出满足条件的数；最后

5、两种算法对比，分别进行仿真实验并对比，研究分析，并对实验结果进行分析。　　　　　解决思路：首先要对概率算法的知识有所了解，熟练C的程序设计的操作，其次，根据多选择经典概率算法、随机概率算法借助仿真软件和计算机编写相应的仿真程序，运用概率知识及密码学相关知识改进经典算法。最后，运行程序，对效果进行分析和评估，得到最后的结论。算法可行性分析、算法的优劣：（1）对经典多选择算法的仿真及改进的首要任务是对经典多选择算法有所了解，在其基础上进一步分析其策略，分析其可行性并对经典算法进行改进；生成随机数，提出多选择的随机算法，并运用概率统计知

6、识改进算法，降低程序运行时间，提高正确率；最后分别对两种算法进行仿真，对实验结果进行分析。（２）在参考专家的技术方法的基础上，利用Ｃ知识和数据结构知识分析算法的安全性，鲁棒性，尽力修改得到最优的算法，相信应该是可行的。完成该课题有以下几步：1查阅资料，寻找经典多选择算法，对其进行仿真仔细分析；2运用概率知识及程序设计知识给出改进方案，提出多选择问题的随机算法，进行仿真实验。3分析两种算法的实验结果，完成总结报告。3、完成本课题的工作方案2009年3月9日——2009年4月10日查阅相关论文资料，熟悉相关内容。2009年4月10日—

7、—2009年4月30日对已有的多选择算法进行研究分析，进行仿真。2009年4月30日——2009年5月20日给出多选择随机化算法，对其进行仿真实验，并对实验结果进行分析。2009年5月20日——2009年6月5日完成毕业论文。2009年6月5日——2009年6月10日准备答辩。主要参考书目（资料）1.RandomizedAlgorithms.RajeevMotwani,PrabhakarRaghavan.CambridgeUniversityPress,1995.2.TowardsOptimalMultipleSelection.

8、KurtMehlhornet.al.ICALP.4．指导教师审阅意见指导教师(签字)：　　　　　　年月日说明：本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计)正式开始的第1周周五之前独立撰写完成，并交指导教师审阅。目录摘要IAbst