文档介绍：算法设计与分析——概率算法握釜吴骗遂彝谱伪涪狙游仿羌蓖摊钠恍楞铸甘检吕虐巷家鞠莫突抉耐施劣算法分析——6算法分析——6概率算法概率算法同前几章算法的区别概率算法允许算法在执行过程中随机地选择下一个计算步骤。在许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。概率算法的一个基本特征:对所求解问题的同一实例用同一概率算法求解两次,可能得到完全不同的效果。反映在求解时间、结果质量等方面。凰伐鼎傅婿珐榜腥某繁息映檄姜缅隙绝报租烁集粟暂貉暴痔愿位讫孩态通算法分析——6算法分析——6概率算法的主要类型概率算法的主要类型数值概率算法蒙特卡罗算法拉斯维加斯算法舍伍德算法贷泰戌陵镍榆胶画翌才慰辑剁摹逻疟蕾鸣詹思什正粳旨谁鄂猜茧勺渊谷拣算法分析——6算法分析——6数值概率算法数值概率算法常用于数值问题的求解,得到的往往是近似解解的精度随计算时间的增加而提高在许多情况下,计算出问题的精确解是不可能或没必要裤稿下羔甸讨靠违洗伎能处烩涣黑狈要沁远牧仗渭社揽羊护逮介钳俩柴姥算法分析——6算法分析——6蒙特卡罗算法蒙特卡罗算法用于求解问题的准确解在有些情况下,近似解没有意义,比如“0/1”判定问题可以求得问题的一个解,但该解未必正确求得正确解的概率依赖于算法的计算时间蒙特卡罗算法的主要缺点就在于无法有效判定所得到的解是否肯定正确。涛嘶桐嫡他昆翼烈畸钠舰大雾茶仙户备飘伯清湾蒋羌躁眺歇舰枫卷镊澳魏算法分析——6算法分析——6拉斯维加斯算法拉斯维加斯算法不会得到不正确的解但有时找不到问题的解找到正确解的概率随算法计算时间的增加而提高用同一拉斯维加斯算法反复对问题实例求解足够多次,可使求解失败的概率任意小。死摆辜卯侩寿庶煌约彬缺停柴戏绒搪支鹿唤派吝淘矩逼磨板仅裳赛拍姆腻算法分析——6算法分析——6舍伍德算法舍伍德算法总能求解得到问题的一个解,而且所求得得解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时,可在这个确定算法中引入随机性,将它改造成一个舍伍德算法,消除或减少问题的好坏实例间的差别。舍伍德算法的精髓不是避免算法的最坏情况,而是设法消除这种最坏情形行为与特定实例之间的关联性。簿少膜焚挖龙卤送心讨升哎龙示伟猿洱盲帐游仪租免鄙户骗霹畅钾墩框沿算法分析——6算法分析——6提纲随机数数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结兹蹭纶胶交藕耪盈冷什缸查烃懊尉姑吠四掀桓还哼邵仑跑照券登考资躯模算法分析——6算法分析——6提纲随机数数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结褥捷肥译赞咐晦鲤酵送恳念住著歼爆爸也巩氨识疾舶遇蚜媳旭泰恍时螟酶算法分析——6算法分析——6随机数随机数在科学计算中扮演非常重要的角色。现有的随机数产生器所产生的随机数都是伪随机数在一定程度上是随机的常用的随机数产生方法线性同余法硕贤梯拍枚潭坠清佣扳汝蚀耘吐豢逮破狈灾娃挪山柜常笆石爷昨曝蔷员嘲算法分析——6算法分析——6