Nickyhw

Danny Dolev等在1982年提及了一种未改进的extreme-find算法，该算法过程简要描述如下：

算法中使用的消息类型有两种：

M1：形式为<1，i>；

M2：形式为<2，i>。

其中，i表示存储在进程中的一个数字。每个进程v都含有一个变量max(v)，当该进程是激活（active）状态时，该变量可以用来存储位于当前进程左边的另一个激活的进程的变量。

被动的（passive）进程仅仅是简单的传递它们接收到的消息。对于算法的描述，我们可以仅仅对其中一个进程的行为进行描述就可以了。

算法     A0. 发送消息<1，max(v)>.

A1. 如果接收到一条消息<1，i>，则执行以下操作：

1. 如果i≠max(v)则发送消息<2，i>，并且将i复制给left(v)。

2. 否则，终止——max(v)是全局最大值。

A2. 如果接受到一条消息<2，i>，则执行以下操作：

1. 如果left(v)大于j和max(v)则将left(v)赋值给max(v)，然后发送消息<1，    max(v)>

2. 否则，变为被动进程。

    基于以上的算法描述，我们可以利用Spin建模语言Promela对其进行建模如下：

    1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为蒙特卡洛方法。

    它的具体定义是：

    在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算列?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的 值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。

    蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两 个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率）， 当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。

    （以上摘自《20世纪最伟大的10个算法》）

    让我们来看一下这个图：

    图中黄色区域为一单位圆，半径r=1。其外接正方形边长为2。我们可以看到，外接正方形与坐标轴将该单位圆切成四等分，而每个小正方形的面积为1*1=1。这样，为了求出小正方形里的扇形面积，我们利用计算机强大的计算能力，往小正方形里投入无数个随机点。假设投进扇形里的点总数为c_sum，投进小正方形里的点（包含投进扇形的点）总数为sum，那么根据公式c_sum / sum = area / 1，即可计算出该扇形的面积 = c_sum / sum。由此可得到圆的面积area = c_sum / sum * 4。
    我们知道，单位圆的半径r=1，所以实际上求单位圆的面积就是求出PI的数值。随机点数量取值越大，那么PI值就越精确。

 1 /**
 2  * 利用蒙特卡洛算法（Mente Carlo Method）计算单位圆面积
 3  *
 4  */
 5 
 6 import java.util.Random;
 7 
 8 public class MonteCarloMethodTest
 9 {
10     public static void main(String[] args)
11     {
12         int sum = 0;                    
13         int c_sum = 0;                    
14         double x;                        
15         double y;                        
16         Random ra = new Random();        
17         
18         int i = 0;
19         while (i != 100000000)            
20         {
21             x = ra.nextDouble();
22             y = ra.nextDouble();
23             
24             if (x * x + y * y <= 1)    
25                 ++c_sum;
26             ++sum;
27             ++i;
28         }
29         
30         double area = (double)c_sum / sum * 4;    
31         System.out.println("area = " + area);
32     }
33 }

    在这个程序中，总共在小正方形里生成了100000000个随机点。通过判断生成的随机点距离圆心点的距离来判断生成的点是否在单位圆内。
    运行10次，结果如下：

    area = 3.14172004

    area = 3.14182308

    area = 3.14190064

    area = 3.14139992

    area = 3.14176768

    area = 3.14177084

    area = 3.14142864

    area = 3.14176596

    area = 3.14191927

    area = 3.14172096
    我们知道，较为精确的PI数值为3.14159265……
    所以即使计算机已经模拟到100000000个随机点，也只能大致精确到小数点后3位，而为了模拟这100000000个点，我的Y560笔记本也平均要花费5秒的时间来进行运算，如果再增加几个0……

    蒙特卡洛算法是1946年提出来的，当时没有运行速度如此快的现代计算机。不过由于现代计算机的运算速度不断提高，借助于其强大的计算能力，我们可以将蒙特卡洛运用在工程中的很多需要近似求解的地方。