【系统方法】Monte-Carlo算法,RP类问题

一朵祥云

OI界传说有这么种说法:每个人出生时都有一个相同属性叫RP值,记作A[0].然后根据你的所作所为所说所想,你的RP值会增加或减少(严密地说是遵循RP守恒定理的转移).如果你的RP好，大于A[0]，那就不是本段所讨论的范围.如果小于A[1](A[1]<A[0]),你的Monte-Carlo算法就没有通过的可能了(这玩意叫RP类问题).如果A[2]<A[1],你在生活中就会有RP爆发的现象,所以我们都力求A递增最长数列,尽量避免A递减数列达到更长.
       我们接下来讲的问题和RP无关...(上面的供娱乐),我们这里要讲的是Monte-Carlo算法(蒙特卡罗算法),又称随机模拟法,还被称为统计实验方法,另外还称统计模拟法,还有就是随机抽样技术.简称就是MC方法.
       如果一个问题存在一个随机算法,使得它有50%以上的概率得到期望的结果,那么这个问题属于RP类问题.该算法称为Monte-Carlo算法.
       如果一个问题是RP类问题,可以通过多次运行它的一个Monte-Carlo算法而得到"几乎每次都是正确"的算法.

      Monte-Carlo算法对于现阶段(指学历)的我们来说,是一种比较火星的算法.为什么说是火星?举个例子:

       比如,已知直径,要求一个圆的面积.蒙特卡罗算法可以这样做:   
     在这个圆外面做个外接正方形,然后在正方形这个区域内产生大量的随机点,对每个点判断是否落在圆内.最后,统计落在圆内的概率,乘以正方形的面积,就可以得到圆的大致面积.只要统计数据足够多,精度就会满足要求.   
       对于圆面积,自然没必要这么麻烦.所以可见其火星.但是,对于无法使用公式法求出面积的区域,比如不能表达为2次、1次曲线的情况,这种方法就很有用.

类似地,如果已知平面上的一个边长为1的正方形及其内部的一个不规则图形,如何求出这个“图形”的面积呢?运用MC方法来解的话(当然,这可当作是定积分的一种应用):向该正方形"随机地"投掷N个点落于"图形"内，则该"图形"的面积近似为M/N.当N足够大时,面积就接近精确值.

MC方法还可运用于求圆周率.设园的半径是r,圆心位于xOy平面的(r,r)处,且内切于边长为2r的正方形中,那么显然正方形的面积是S1＝4r×r,用MC方法计算出圆的面积(假设共画了N个点,落在圆内部的有M个点,当N足够大的时,圆的面积S=M/N*S1),这里产生随机数x和y的值域为[0,2r],然后判断(x,y)是否落在圆内
(x-r)^2+(y-r)^2<r^2
记录下总的点数N和落在圆中的点数M，则圆的面积为S＝4r2M/N，从而得pi＝4×M/N.

由此可得知蒙特卡罗算法的概念如下:MC方法是以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解。

蒙特卡罗是一座赌城的名称,形象地表明了改算法的特点.S.M.乌拉姆和J.冯·诺伊曼在20世纪40年代为研制核武器而首先提出.它的基本思想是:为了求解数学、物理、工程技术以及管理等方面的问题，首先建立一个概率模型或随机过程，使它们的参数，如概率分布或数学期望等问题的解；然后通过对模型或过程的观察或抽样试验来计算所求参数的统计特征，并用算术平均值作为所求解的近似值。对于随机性问题，有时还可以根据实际物理背景的概率法则，用电子计算机直接进行抽样试验，从而求得问题的解答。这也就是MC算法的基本运用路线.

运用MC方法,借助量子力学可以进行电子云模拟,yuhc不搞物理,所以不懂这个,呵呵..

       蒙特卡罗算法是非完美算法的依据.非完美算法是什么?它包括抽样测试法(初中数学有类似方法),随机化贪心(随机与贪心结合),部分忽略法等,非完美算法复杂度低,空间和时间效率高,但准确性低一些.这些算法黑书上都有,在次不赘述了.

       要特别注意的是,MC方法必须使用真随机数来进行统计,而假随机数会影响计数结果.真随机数就和掷骰子一样,产生的随机数除了统计规律外无其它规律可循.

       以后做选择题的时候,我们是否可以画4个不规则等面积图像,往上面扔石子,来判断选ABC还是D?这样比点子点母的办法好吧..按yuhc的想法做而做错的朋友,不要往这扔鸡蛋阿......yuhc无罪..罪在你的假随机数上..