《统计问题的概率算法研究》由会员分享，可在线阅读，更多相关《统计问题的概率算法研究（33页珍藏版）》请在金锄头文库上搜索。
1、 1 本课题所涉及的问题在国内(外)的研究、应用现状综述1976 年雷兵提出了概率算法，它不同于一般算法，其新颖之处是把随机性注入到算法中，使得算法设计与分析的灵活性及解决问题的能力大为改观，这种算法曾一度运用在密码学，数字信号，数字简化信号和大系统的安全及故障容差中得到应用。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。在科学和工程实践中, 很多优化问题需要同时满足几个不同的目标, 而这些目标之间往往是相互约束、相互冲突的, 这类问题被统称为多目标优化问题(简称 MOP) 。在现实生活中, 很多重要的决策同样面临着多目标
2、优化的难题, 如城市运输、水库管理、城市规划、能源分配等。所以在对许多应用领域，特别是音频或视频处理等领域，最后的结果是有多个满足条件的数，即没必要追求最高精度，只要误差很小，因此其影响也就小了。所以多选择问题的概率算法研究很有意义。目前的拉斯维加斯算法的一个显著特征是他所作的随机性决策，虽然这有可能导致算法找不到所需的解，但用一个 bool 型函数表示拉斯维加斯型算法。当算法找到一个解时返回 ture，否则返回 false，拉斯维加斯算法的典型调用形式为 bool success=LV（x，y）；其中 x 是输入参数；当 success 的值为true 时，y 返回问题的解，当 succes
3、s 为 false 时，算法未能找到问题的一个解，此时可对同一实例再次独立地调用相同的算法；n 后问题是一个古老而著名的问题，该问题为我们提供了设计高效的拉斯维加斯算法的很好的例子，对于n 后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此容易想到拉斯维加斯算法，我们在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至 n 个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。我们可用回溯法解这个问题。此外从蚁群算法中专家得到启示：将信息素的观点引入到求解组合优化问题的演化算法之中,提出了一种基因优化算法.
4、该算能学习劣解的基因,并用信息熵作为结束条件的判据.最后解决了两个典型的组合优化问题,也取得了较好的结果。型的组合优化问题,也取得了较好的结果。2 本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析。关键问题：首先生成一定量的随机数，用经典多选择算法对多个数值进行选择，挑选出满足条件的数；其次用概率统计知识改进经典多选择算法，提高速度及降低复杂度，使之更快更准确的选择出满足条件的数；最后两种算法对比，分别进行仿真实验并对比，研究分析，并对实验结果进行分析。 解决思路：首先要对概率算法的知识有所了解，熟练 C 的程序设计的操作，其次，根据多选择经典概率算法、随机概率算法借助仿真软
5、件和计算机编写相应的仿真程序，运用概率知识及密码学相关知识改进经典算法。最后，运行程序，对效果进行分析和评估，得到最后的结论。算法可行性分析、算法的优劣： （1）对经典多选择算法的仿真及改进的首要任务是对经典多选择算法有所了解，在其基础上进一步分析其策略，分析其可行性并对经典算法进行改进；生成随机数，提出多选择的随机算法，并运用概率统计知识改进算法，降低程序运行时间，提高正确率；最后分别对两种算法进行仿真，对实验结果进行分析。 （）在参考专家的技术方法的基础上，利用知识和数据结构知识分析算法的安全性，鲁棒性，尽力修改得到最优的算法，相信应该是可行的。完成该课题有以下几步：1 查阅资料，寻找经典
6、多选择算法，对其进行仿真仔细分析；2 运用概率知识及程序设计知识给出改进方案，提出多选择问题的随机算法，进行仿真实验。3 分析两种算法的实验结果，完成总结报告。3、 完成本课题的工作方案2009 年 3 月 9 日2009 年 4 月 10 日 查阅相关论文资料，熟悉相关内容。 2009 年 4 月 10 日2009 年 4 月 30 日 对已有的多选择算法进行研究分析，进行仿真。 2009 年 4 月 30 日2009 年 5 月 20 日 给出多选择随机化算法，对其进行仿真实验，并对实验结果进行分析。 2009 年 5 月 20 日2009 年 6 月 5 日 完成毕业论文。2009 年
7、6 月 5 日2009 年 6 月 10 日 准备答辩。主要参考书目（资料）1.Randomized Algorithms. Rajeev Motwani, Prabhakar Raghavan. Cambridge University Press, 1995. 2.Towards Optimal Multiple Selection. Kurt Mehlhorn et. al. ICALP.4指导教师审阅意见指导教师指导教师(签字)： 年 月 日说明： 本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计) 正 式开始的第 1 周周五之前独立撰写完成，并交指导教师审阅。目录摘要.
8、IAbstract.II1 引言.12 多选择问题的随机算法的简介.22.1 多选择问题的简介.22.2 随机算法的简介.23 三个经典多选择算法的程序设计思想及仿真.33.1 基于快速排序的经典算法的程序设计思想.33.1.1 基于快速排序的经典算法的程序设计.3 3.1.2 基于快速排序的经典算法仿真.53.2 基于冒泡排序的经典算法的程序设计思想.53.1.1 基于冒泡排序的经典算法的程序设计.6 3.2.2 基于冒泡排序的经典算法仿真.73.3 基于堆排序的经典算法的程序设计思想.73.3.1 基于堆排序的经典算法的程序设计.8 3.3.2 基于堆排序的经典算法仿真.94 三个经典多选
9、择算法的分析.114.1 基于快速排序的经典算法分析.114.1.1 效率分析.11 4.1.2 时间复杂度分析.114.2 基于冒泡排序的经典算法分析.124.2.1 效率分析.12 4.2.2 时间复杂度分析.124.3 基于堆排序的经典算法分析.124.3.1 效率分析.12 4.3.2 时间复杂度分析.125 多选择问题的随机算法的实现.135.1 多选择问题的随机算法的程序设计思想.135.2 多选择问题的随机算法的仿真.215.3 多选择问题的随机算法与经典算法的比较.226.结论.23致谢.24参考文献.25I摘要目前在科学和工程实践中, 很多优化问题需要同时满足几个不同的目标,
10、 这类问题被统称为多目标优化问题。在现实生活中, 很多重要的决策同样面临着多目标优化的难题, 如城市运输、水库管理、城市规划、能源分配等。所以在许多应用领域，特别是音频或视频处理等领域，最后的结果是有多个满足条件的数，所以多选择问题的概率算法研究很有意义。本文所讨论的多选择问题的算法是一个比较具体的算法：就是要从一堆随机数中挑选出多个满足条件的数。本文中先用几种我们熟悉的经典算法来实现这个目标，然后进一步对经典算法进行改进，进而提出随机算法。由于随机算法允许算法在执行过程中随机地选择下一个计算步骤，这就使得程序运行情况会取得中间值，即是平均情况。随机算法与经典算法相比，要求效率更高，时间复杂度大大下降。关键词:多选择；随机算法；时间复杂度 IIAbstractAt the present，in science and
