- 1、本文档共22页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Monte-Carlo算法.doc
引言
????? 最近在和同学讨论研究Six Sigma(六西格玛)软件开发方法及CMMI相关问题时,遇到了需要使用Monte-Carlo算法模拟分布未知的多元一次概率密度分布问题。于是花了几天时间,通过查询相关文献资料,深入研究了一下Monte-Carlo算法,并以实际应用为背景进行了一些实验。????? 在研究和实验过程中,发现Monte-Carlo算法是一个非常有用的算法,在许多实际问题中,都有用武之地。目前,这个算法已经在金融学、经济学、工程学、物理学、计算科学及计算机科学等多个领域广泛应用。而且这个算法本身并不复杂,只要掌握概率论及数理统计的基本知识,就可以学会并加以应用。由于这种算法与传统的确定性算法在解决问题的思路方面截然不同,作为计算机科学与技术相关人员以及程序员,掌握此算法,可以开阔思维,为解决问题增加一条新的思路。????? 基于以上原因,我有了写这篇文章的打算,一是回顾总结这几天的研究和实验,加深印象,二是和朋友们分享此算法以及我的一些经验。????? 这篇文章将首先从直观的角度,介绍Monte-Carlo算法,然后介绍算法基本原理及数理基础,最后将会和大家分享几个基于Monte-Carlo方法的有意思的实验。所以程序将使用C#实现。????? 阅读本文需要有一些概率论、数理统计、微积分和计算复杂性的基本知识,不过不用太担心,我将尽量避免过多的数学描述,并在适当的地方对于用到的数学知识进行简要的说明。
Monte-Carlo算法引导
????? 首先,我们来看一个有意思的问题:在一个1平方米的正方形木板上,随意画一个圈,求这个圈的面积。????? 我们知道,如果圆圈是标准的,我们可以通过测量半径r,然后用 S = pi * r^2 来求出面积。可是,我们画的圈一般是不标准的,有时还特别不规则,如下图是我画的巨难看的圆圈。
图1、不规则圆圈
????? 显然,这个图形不太可能有面积公式可以套用,也不太可能用解析的方法给出准确解。不过,我们可以用如下方法求这个图形的面积:????? 假设我手里有一支飞镖,我将飞镖掷向木板。并且,我们假定每一次都能掷在木板上,不会偏出木板,但每一次掷在木板的什么地方,是完全随机的。即,每一次掷飞镖,飞镖扎进木板的任何一点的概率的相等的。这样,我们投掷多次,例如100次,然后我们统计这100次中,扎入不规则图形内部的次数,假设为k,那么,我们就可以用 k/100 * 1 近似估计不规则图形的面积,例如100次有32次掷入图形内,我们就可以估计图形的面积为0.32平方米。
????? 以上这个过程,就是Monte-Carlo算法直观应用例子。????? 非形式化地说,Monte-Carlo算法泛指一类算法。在这些算法中,要求解的问题是某随机事件的概率或某随机变量的期望。这时,通过“实验”方法,用频率代替概率或得到随机变量的某些数字特征,以此作为问题的解。????? 上述问题中,如果将“投掷一次飞镖并掷入不规则图形内部”作为事件,那么图形的面积在数学上等价于这个事件发生的概率(稍后证明),为了估计这个概率,我们用多次重复实验的方法,得到事件发生的频率 k/100 ,以此频率估计概率,从而得到问题的解。
????? 从上述可以看出,Monte-Carlo算法区别于确定性算法,它的解不一定是准确或正确的,其准确或正确性依赖于概率和统计,但在某些问题上,当重复实验次数足够大时,可以从很大概率上(这个概率是可以在数学上证明的,但依赖于具体问题)确保解的准确或正确性,所以,我们可以根据具体的概率分析,设定实验的次数,从而将误差或错误率降到一个可容忍的程度。????? 上述问题中,设总面积为S,不规则图形面积为s,共投掷n次,其中掷在不规则图形内部的次数为k。根据伯努利大数定理,当试验次数增多时,k/n依概率收敛于事件的概率s/S。下面给出严格证明:
????? 上述证明从数学上说明用频率估计不规则图形面积的合理性,进一步可以给出误差分析,从而选择合适的实验次数n,以将误差控制在可以容忍的范围内,此处从略。
????? 从上面的分析可以看出,Monte-Carlo算法虽然不能保证解一定是准确和正确,但并不是“撞大运”,其正确性和准确性依赖概率论,有严格的数学基础,并且通过数学分析手段对实验加以控制,可以将误差和错误率降至可容忍范围。
Monte-Carlo算法的数理基础
????? 这一节讨论Monte-Carlo算法的数理基础。????? 首先给出三个定义:优势,一致,偏真。这三个定义在后面会经常用到。
????? 1) 设p为一个实数,且0.5p1。如果一个Monte-Carlo方法对问题任一实例的得到正确解的概率不小于p,则该算法是p正确的,且p-0.5叫做此算法的优势
您可能关注的文档
- Dnnwspu婴幼儿营养与保育平时作业.doc
- dxcnjdq雅思_写作高频词汇分类汇总.doc
- D触发器电路设计.ppt
- envelop writing.ppt
- Excel查询函数中.doc
- FVS336G有线 VPN 防火墙.doc
- GRE2006年6月填空、词汇真题解析.doc
- GRPI 模型.doc
- H3C MSR 5600路由器CLI基础配置指.doc
- hg冉平牌RLC—8、8QYG.doc
- 某某单位2024年党建工作总结及2025年工作计划.doc
- 某某市发改委关于2024年度落实党风廉政建设工作责任制情况的报告.doc
- 某某局2024年全面从严治党和党风廉政建设工作总结.doc
- 某某区财政局2024年法治政府建设总结及2025年工作谋划.doc
- 2024年党管武装工作述职报告2篇.doc
- 2024年度国企党委书记抓基层党建工作述职报告3篇.doc
- 公司党委书记2024年述职述廉报告.docx
- 2024年度乡镇党委领导班子民主生活会(四个带头)对照检查材料.doc
- 市医疗保障局关于2024年法治政府建设工作情况的报告.docx
- 市民政局党组2024年巡察整改工作情况报告.docx
文档评论(0)