统计问题的概率法研究.doc

本课题所涉及的问题在国内(外)的研究、应用现状综述 1976年雷兵提出了概率算法新颖之处是把随机性注入到算法中，使得算法设计与分析的灵活性及解决问题的能力大为改观，这种算法曾一度运用在密码学，数字信号，数字简化信号和大系统的安全及故障容差中得到应用。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度, 很多优化问题需要同时满足几个不同的目标, 而这些目标之间往往是相互约束、相互冲突的, 这类问题被统称为多目标优化问题(简称MOP) 。在现实生活中, 很多重要的决策同样面临着多目标优化的难题, 如城市运输、水库管理、城市规划、能源分配等。所以在对许多应用领域，特别是音频或视频处理等领域，最后的结果即没必要追求最高精度误差很小，因此其影响也小拉斯维加斯算法的一个显著特征是他所作的随机性决策有可能导致算法找不到所需的解用一个bool型函数表示拉斯维加斯型算法。当算法找到一个解时返回ture，否则返回false拉斯维加斯算法的典型调用形式为bool success=LV（x，y）；其中x是输入参数；当success的值为true时，y返回问题的解当success为false时，算法未能找到问题的一个解此时可对同一实例再次独立地调用相同的算法n后问题是一个古老而著名的问题，问题为我们提供了设计高效的拉斯维加斯算法的很好的例子，对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的由此容易想到拉斯维加斯算法我们在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。我们用回溯法解这个问题。从蚁群算法中得到启示将信息素的观点引入到求解组合优化问题的演化算法之中,提出了一种基因优化算法.该算能学习劣解的基因,并用信息熵作为结束条件的判据.最后解决了两个典型的组合优化问题,取得了较好的结果。型的组合优化问题,取得了较好的结果。Randomized Algorithms. Rajeev Motwani, Prabhakar Raghavan. Cambridge University Press, 1995. Towards Optimal Multiple Selection. Kurt Mehlhorn et. al. ICALP. 4．指导教师审阅意见 指导教师(签字)：　　　　　　 年 月 日 说明： 本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计) 正式开始的第1周周五之前独立撰写完成，并交指导教师审阅。 目录 摘要 I Abstract II 1 引言 1 2多选择问题的随机算法的简介 2 2.1多选择问题的简介 2 2.2随机算法的简介 2 3 三个经典多选择算法的程序设计思想及仿真 3 3.1基于快速排序的经典算法的程序设计思想 3 3.1.1基于快速排序的经典算法的程序设计 3 3.1.2基于快速排序的经典算法仿真 5 3.2基于冒泡排序的经典算法的程序设计思想 5 3.1.1基于冒泡排序的经典算法的程序设计 6 3.2.2基于冒泡排序的经典算法仿真 7 3.3基于堆排序的经典算法的程序设计思想 7 3.3.1基于堆排序的经典算法的程序设计 8 3.3.2基于堆排序的经典算法仿真 9 4 三个经典多选择算法的分析 11 4.1 基于快速排序的经典算法分析 11 4.1.1 效率分析 11 4.1.2 时间复杂度分析 11 4.2 基于冒泡排序的经典算法分析 12 4.2.1 效率分析 12 4.2.2 时间复杂度分析 12 4.3 基于堆排序的经典算法分析 12 4.3.1 效率分析 12 4.3.2 时间复杂度分析 12 5 多选择问题的随机算法的实现 13 5.1 多选择问题的随机算法的程序设计思想 13 5.2 多选择问题的随机算法的仿真 21 5.3 多选择问题的随机算法与经典算法的比较 22 6.结论 23 致谢 24 参考文献 25 摘要 目前在科学和工程实践中, 很多优化问题需要同时满足几个不同的目标, 这类问题被统称为多目标优化问题。在现实生活中, 很多重要的决策同样面临着多目标优化的难题, 如城市运输、水库管理、城市规划、能源分配等。所以在许多应用领域，特别是音频或视频处理等领域，最后的结果随机算法允许算法在执行过程中随机地选择下一个计算步骤 Abstract At the present，in science and engineeri