c概率演算法

A. 如何有效提高概率演算法獲得正確解的概率或提高演算法的求解精度

1）數值概率演算法：常用於數值問題的求解，得到的往往是近似解
（1）解的精度隨計算時間的增加而提高
（2）在許多情況下，計算出問題的精確解是不可能或沒必要
2）蒙特卡羅演算法：用於求解問題的准確解，可以求得問題的一個解，但該解未必正確
（1）求得正確解的概率依賴於演算法的計算時間
多次執行蒙特卡羅演算法，可以提高獲得正確解的概率
（2）無法有效判定所得到的解是否肯定正確。
3）拉斯維加斯演算法：不會得到不正確的解
（1）有時找不到問題的解
（2）找到正確解的概率隨演算法計算時間的增加而提高
（3）用同一拉斯維加斯演算法反復對問題實例求解足夠多次，可使求解失敗的概率任意小。
4）舍伍德演算法：總能求解得到問題的一個解，而且所求得得解總是正確的。
將確定性演算法引入隨機性改造成舍伍德演算法，可消除或減少問題對於好壞實例間的差別。

B. 怎麼計算概率

概率是對事件發生可能性大小的度量。不會發生的概率為0，一定會發生的概率是100%，也可以說是1.例如拋硬幣，正面和反面出現的可能性都是50%，篩子每面出現的可能性都是六分之一，這些概率值通過直覺和經驗就能想出來。雖然我們知道實驗幾次不一定是這個結果，但試驗次數很多時，出現的頻率就會接近概率值，無窮次時，頻率就會等於概率。

通過直觀和經驗就能知道概率的幾個基本命題，也可以說是公理，蘇聯的數學家柯爾莫哥洛夫總結了3條概率公理。

1. 事件發生的概率不小於0

2. 集合中的事件必有一件發生，則發生的概率之和等於1

3. 集合中事件互相不容，沒有交集，則發生至少一個的概率等於每個事件概率之和

這3個公理不需記憶，應用時也不需刻意用，用直覺和經驗靠算術思維就能想出概率計算方法。

通過這3個公理也可以推導出6個定理，也不需記憶，甚至不需要知道。

概率計算不像方程應用，簡單地分別考慮每個數值含義列出等式，然後變換方程就能求解。列概率算式無法這樣做，那些概率定理和概率公式以及寫法，如:貝葉斯公式 P(A|B)=P(B|A)*P(A)/P(B) ，對列出概率算式幫助不大，也無法降低分析和推理難度，也就是說概率知識的公理化意義不大。概率計算時，只需按算術思維，按直覺和經驗直接列出算式，然後進行四則運算即可。簡單的場合，可以直接列出一個算式就可以算出概率值，在稍微復雜的場合需要分別列出幾個算式，然後再去轉換，這些復雜場合的概率演算法常見的有頻次演算法，集合對應演算法，和反向演算法。

C. 概率計算公式是什麼

條件概率：

條件概率：已知事件B出現的條件下A出現的概率，稱為條件概率，記作：P(A|B)

條件概率計算公式：

當P(A)>0，P(B|A)=P(AB)/P(A)

當P(B)>0，P(A|B)=P(AB)/P(B)

乘法公式：

P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

推廣：P(ABC)=P(A)P(B|A)P(C|AB)

全概率公式：

設：若事件A1，A2，…，An互不相容，且A1+A2+…+An=Ω，則稱A1，A2，…，An構成一個完備事件組。

概率演算法：概率演算法的一個基本特徵是，對所求問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。

隨機數在概率演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。

D. (六) 概率演算法

前面所討論演算法的每一計算步驟都是確定的，而本次所討論的概率演算法允許演算法在執行過程中隨機地選擇下一個計算步驟。在許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的復雜度。

概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下， 可將概率演算法大致分為四類：數值概率演算法、蒙特卡羅(MonteCarlo) 演算法、拉斯羨孝陵維加斯(Las Vegas) 演算法和舍伍德(Sherwood) 演算法。

隨機數在隨機化演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在隨機化演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。
線性同餘法 是產生偽隨機數的最常用的方法。由線性同餘法產生的隨機序列 滿足

其中 。d稱為該隨機序列的種子。如何選取該方法中的常數b、c和m直接關繫到所產生的隨機序列的隨機性能。這是隨機性理論研究的內容，已超出本書討論的范圍。從直觀上看，m應取得充分大，因此可取m為機器大數，另外應取 ，因此可取b為一素數。

為了在設計概率演算法時便於產生所需的隨機數，建立一個隨機數類RandomNumber：該類包含一個需由用戶初始化的種子randSeed。給定初始種子後，即可產生與之相應的隨機序列。種子randSeed是一個無符號長整型數， 可由用戶選定也可用系統時間自動產生。函數Random的輸入參數 是一個無符號長整型數，它返回 范圍內的一個隨機整數。函數fRandom返回[0，1) 內的一個隨機實數。

數值概率演算法常用於數值問題的求解。這類演算法所得到的往往是近似解。且近似解的精度隨計算時間的增加而不斷提高。在許多情況下，要計算出問題的精確解是不可能的或沒有必要的，因此用數值概率演算法可得到相當滿意的解。

當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時

舍伍德演算法就是一種利用隨機演算法改造確定性演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞情形行為與特定實例之間的關聯性。

思想：利用隨機演算法改造已有演算法，使得演算法的性能盡量與輸入數據無關，即平滑演算法的性能。它總能求得問兄戚題的一個解，且求得的解總是正確的。

演算法的性能 =平均性能 + 一個很小的隨機值。 舍伍德演算法是為了得到好的平均性能。

一個演算法，對於不同的輸入數據，其演算法的性能是不一樣的。比如快排演算法，每次選擇第一個元素作為基準，慎帶對序列從小到大排序：

拉斯維加斯演算法不會得到不正確的解。一旦用拉斯維加斯演算法找到一個解，這個解就一定是正確解。但有時用拉斯維加斯演算法會找不到解。

與蒙特卡羅演算法類似，拉斯維加斯演算法找到正確解的概率隨著它所用的計算時間的增加而提高。對於所求解問題的任一實例，用同一拉斯維加斯演算法反復對該實例求解足夠多次，可使求解失效的概率任意小。

蒙特卡羅演算法用於求問題的准確解。對於許多問題來說，近似解毫無意義。例如，一個判定問題其解為「是」或「否」，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是准確的，一個整數的近似因子沒有任何意義。

用蒙特卡羅演算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴於演算法所用的時間。演算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅演算法的主要缺點也在於此。一般情況下，無法有效地判定所得到的解是否肯定正確。

在實際應用中常會遇到一些問題，不論採用確定性演算法或隨機化演算法都無法保證每次都能得到正確的解答。蒙特卡羅演算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。

有些蒙特卡羅演算法除了具有描述問題實例的輸入參數外，還具有描述錯誤解可接受概率的參數。這類演算法的計算時間復雜性通常由問題的實例規模以及錯誤解可接受概率的函數來描述。

參考鏈接： http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html

數值概率演算法的應用

舍伍德演算法的應用

拉斯維加斯演算法的應用

蒙特卡羅演算法的應用

E. 概率演算法

最近做了一個活動抽獎需求，項目需要控制預算，概率需要分布均勻，這樣才能獲得所需要的概率結果。
例如抽獎得到紅包獎金，而每個獎金的分布都有一定概率：

現在的問題就是如何根據概率分配給用戶一定數量的紅包。

演算法思路 ：生成一個列表，分成幾個區間，例如列表長度100，1-40是0.01-1元的區間，41-65是1-2元的區間等，然後隨機從100取出一個數，看落在哪個區間，獲得紅包區間，最後用隨機函數在這個紅包區間內獲得對應紅包數。

時間復雜度 ：預處理O(MN)，隨機數生成O(1)，空間復雜度O(MN)，其中N代表紅包種類，M則由最低概率決定。

優缺點 ：該方法優點是實現簡單，構造完成之後生成隨機類型的時間復雜度就是O(1)，缺點是精度不夠高，佔用空間大，尤其是在類型很多的時候。

演算法思路 ：離散演算法通過概率分布構造幾個點[40, 65, 85, 95,100]，構造的數組的值就是前面概率依次累加的概率之和。在生成1~100的隨機數，看它落在哪個區間，比如50在[40,65]之間，就是類型2。在查找時，可以採用線性查找，或效率更高的二分查找。

演算法復雜度 ：比一般演算法減少佔用空間，還可以採用二分法找出R，這樣，預處理O(N)，隨機數生成O(logN)，空間復雜度O(N)。

優缺點 ：比一般演算法佔用空間減少，空間復雜度O(N)。

演算法思路 ：Alias Method將每種概率當做一列，該演算法最終的結果是要構造拼裝出一個每一列合都為1的矩形，若每一列最後都要為1，那麼要將所有元素都乘以5（概率類型的數量）。

此時會有概率大於1的和小於1的，接下來就是構造出某種演算法用大於1的補足小於1的，使每種概率最後都為1，注意，這里要遵循一個限制：每列至多是兩種概率的組合。

最終，我們得到了兩個數組，一個是在下面原始的prob數組[0.75,0.25,0.5,0.25,1]，另外就是在上面補充的Alias數組，其值代表填充的那一列的序號索引，（如果這一列上不需填充，那麼就是NULL），[4,4,0,1,NULL]。當然，最終的結果可能不止一種，你也可能得到其他結果。

舉例驗證下，比如取第二列，讓prob[1]的值與一個隨機小數f比較，如果f小於prob[1]，那麼結果就是2-3元，否則就是Alias[1]，即4。

我們可以來簡單驗證一下，比如隨機到第二列的概率是0.2，得到第三列下半部分的概率為0.2 * 0.25，記得在第四列還有它的一部分，那裡的概率為0.2 * (1-0.25)，兩者相加最終的結果還是0.2 * 0.25 + 0.2 * (1-0.25) = 0.2，符合原來第二列的概率per[1]。

演算法復雜度 ：預處理O(NlogN)，隨機數生成O(1)，空間復雜度O(2N)。

優缺點 ：這種演算法初始化較復雜，但生成隨機結果的時間復雜度為O(1)，是一種性能非常好的演算法。