1、什么是概率算法？

概率算法依照概率統計的思想來求解問題，其往往不能得到問題的精確解，但是在數值計算領域得到了廣泛的應用。因為很多數學問題，往往沒有或者很難計算解析，此時便需要通過數值計算來求解近似值。概率算法執行的基本過程如下：

? (1). 將問題轉化為相應的幾何圖形S，S的面積容易計算，問題的結果往往對應幾何圖形中某一部分S1的面積。

? (2). 然后，向幾何圖形中隨機撒點。

? (3). 統計幾何圖形S和S1中的點數。根據S和S1面積的關系及各圖形中的點數來計算得到結果。

? (4). 判斷上述結果是否在需要的精度之內，如果未達到精度則執行步驟(2)。如果達到精度，則輸出近似結果。

概率算法大致分為如下4種形式：數值概率算法；蒙特卡羅（Monte Carlo）算法；拉斯維加斯（Las Vegas）算法；舍伍德（Sherwood）算法；

2、概率算法的應用

計算π的近似值

圓周率π是一個非常重要的常數，無論在數學還是在物理學上都有很廣泛的用途。π的值直接關系到計算圓周長、圓面積、球體積等。π一般定義為圓周長與圓直徑之比。在數學分析學中，圓周率π被嚴格定義為滿足如下等式的最小正實數：，圓周率 π=3.141592653589793…… ，其是一個無限不循環實數，即所謂的無理數。圓周率π的精確計算，從古至今都非常重要。

蒙特卡羅（Monte Carlo）算法是一種以概率為基礎的、非常重要的數值計算方法，在工程、金融、計算物理學等領域都有著重要的應用。蒙特卡羅算法是如何計算圓周率π的呢？我們先畫一個半徑為1的圓，如圖所示：

先來推算圖中陰影部分的面積，陰影部分是一個圓的1/4，因此有如下計算公式：S陰影 = S圓 /4 = (1/4)π*r^2 = π/4 ，而圖中正方形的面積則為：S正 = r^2 = 1，這樣，按照圖示建立一個坐標系。如果均勻地向正方形內撒點，那么落入陰影部分的點數與全部的點數之比就是S陰影/S正方形=π/4。根據概率統計的規律，只要撒的點足夠多，就會得到近似的結果。通過這個原理便可以計算圓周率π的近似值，這就是蒙特卡羅算法。

蒙特卡羅算法有幾個關鍵點：

• 均勻撒點：使用隨機方法來實現，產生[0，1]之間隨機的坐標值[x，y]。
• 區域判斷：圖中陰影部分的特點是距離坐標原點的距離小于等于1，這樣，可以通過計算判斷x^2+y^2≤1來實現。

通過蒙特卡羅算法計算π的近似值，Java實現demo演示如下：

public class Test {/*** 打印結果：* n = 6000 ------> π = 3.1466666666666665* n = 600000 ------> π = 3.1464866666666667* n = 60000000 ------> π = 3.1413683333333333* n = 600000000 ------> π = 3.1415774266666667**/public static void main(String[] args) {int n = 6000;System.out.println("n = " + n + " ------> π = " + getMontePI(n));}public static double getMontePI(int amount) { // amount為陰影區域的撒點數int cnt = 0; // 統計落在陰影區域的點Random random = new Random();for (int i = 1; i < amount; i++) {// 陰影區域范圍：x^2+y^2≤1if (Math.pow(random.nextDouble(), 2) + Math.pow(random.nextDouble(), 2) <= 1)cnt++;}return 4.0 * cnt / amount; // π概率計算公式} }

從測試結果可知：撒點數n越多，概率統計得到π的值越精確。同時，由于概率算法的隨機性，在不同的運行時間，即使輸入同樣的撒點數，得到的結果也是不相同的。

參考書籍：《Java常用算法手冊（第3版）》

總結

以上是生活随笔為你收集整理的【基本算法】概率算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。