Nickyhw

Danny Dolev等在1982年提及了一種未改進的extreme-find算法，該算法過程簡要描述如下：

算法中使用的消息類型有兩種：

M1：形式為<1，i>；

M2：形式為<2，i>。

其中，i表示存儲在進程中的一個數字。每個進程v都含有一個變量max(v)，當該進程是激活（active）狀態(tài)時，該變量可以用來存儲位于當前進程左邊的另一個激活的進程的變量。

被動的（passive）進程僅僅是簡單的傳遞它們接收到的消息。對于算法的描述，我們可以僅僅對其中一個進程的行為進行描述就可以了。

算法     A0. 發(fā)送消息<1，max(v)>.

A1. 如果接收到一條消息<1，i>，則執(zhí)行以下操作：

1. 如果i≠max(v)則發(fā)送消息<2，i>，并且將i復制給left(v)。

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

A2. 如果接受到一條消息<2，i>，則執(zhí)行以下操作：

1. 如果left(v)大于j和max(v)則將left(v)賦值給max(v)，然后發(fā)送消息<1，    max(v)>

2. 否則，變?yōu)楸粍舆M程。

    基于以上的算法描述，我們可以利用Spin建模語言Promela對其進行建模如下：

    1946年，美國拉斯阿莫斯國家實驗室的三位科學家John von Neumann,Stan Ulam 和 Nick Metropolis共同發(fā)明，被稱為蒙特卡洛方法。

    它的具體定義是：

    在廣場上畫一個邊長一米的正方形，在正方形內部隨意用粉筆畫一個不規(guī)則的形狀，現在要計算這個不規(guī)則圖形的面積，怎么計算列?蒙特卡洛(Monte Carlo)方法告訴我們，均勻的向該正方形內撒N（N 是一個很大的自然數）個黃豆，隨后數數有多少個黃豆在這個不規(guī)則幾何形狀內部，比如說有M個，那么，這個奇怪形狀的面積便近似于M/N，N越大，算出來的 值便越精確。在這里我們要假定豆子都在一個平面上，相互之間沒有重疊。

    蒙特卡洛方法可用于近似計算圓周率：讓計算機每次隨機生成兩 個0到1之間的數，看這兩個實數是否在單位圓內。生成一系列隨機點，統計單位圓內的點數與總點數，（圓面積和正方形面積之比為PI:1，PI為圓周率）， 當隨機點取得越多（但即使取10的9次方個隨機點時，其結果也僅在前4位與圓周率吻合）時，其結果越接近于圓周率。

    （以上摘自《20世紀最偉大的10個算法》）

    讓我們來看一下這個圖：

    圖中黃色區(qū)域為一單位圓，半徑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年提出來的，當時沒有運行速度如此快的現代計算機。不過由于現代計算機的運算速度不斷提高，借助于其強大的計算能力，我們可以將蒙特卡洛運用在工程中的很多需要近似求解的地方。