不屬於隨機演算法的是

A. 概率搜索演算法有哪些，除了遺傳演算法和蟻群

遺傳演算法(Genetic Algorithm，GA)是由Holland J．H．於20世紀70年代提出的一種優化方法，其最優解的搜索過程模擬達爾文的進化論和「適者生存」的思想。

蟻群演算法(Ant Colony Optimization, ACO)，是一種用來在圖中尋找優化路徑的機率型演算法。

兩種演算法從概念上都屬於隨機優化演算法，遺傳演算法是進化演算法，主要通過選擇、變異和交叉運算元，其中每個基因是由二進制串組成；蟻群演算法是基於圖論的演算法，通過信息素選擇交換信息。

B. 隨機演算法的基本概念

隨機演算法是演算法本身包含了隨機數生成器的演算法。根據《演算法導論（中文第二版）》描述，在進行演算法分析的時，有時可以在獲得了一定輸入分布信息之後對輸入的分布進行一定的假定，在此基礎上進行平均情況分析得到演算法的時間復雜度。然而有時候無法獲得輸入分布的信息，這時可以在演算法本身增加一定的隨機性，繼而實現對演算法進行平均情況分析。通過設計隨機演算法有效地避免較多的較壞情況輸入的出現，從而提高演算法的平均情況下的性能。

C. 蒙特卡洛演算法和拉斯維加斯演算法

一、定義：

特卡羅是一類隨機方法的統稱。這類方法的特點是，可以在隨機采樣上計算得到近似結果，隨著采樣的增多，得到的結果是正確結果的概率逐漸加大，但在（放棄隨機采樣，而採用類似全采樣這樣的確定性方法）獲得真正的結果之前，無法知道目前得到的結果是不是真正的結果。​

拉斯維加斯方法是另一類隨機方法的統稱。這類方法的特點是，隨著采樣次數的增多，得到的正確結果的概率逐漸加大，如果隨機采樣過程中已經找到了正確結果，該方法可以判別並報告，但在但在放棄隨機采樣，而採用渣豎類似全采樣這樣的確定性方法之前，不保證能找到任何結果（包括近似結果）​

二、場景舉例​

假如筐里有100個蘋果，讓我每次閉備梁銀眼拿1個，挑出最大的。於是我隨機拿1個，再隨機拿1個跟它比仿宴，留下大的，再隨機拿1個……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數越多，挑出的蘋果就越大，但我除非拿100次，否則無法肯定挑出了最大的。這個挑蘋果的演算法，就屬於蒙特卡羅演算法——盡量找好的，但不保證是最好的。

而拉斯維加斯演算法，則是另一種情況。假如有一把鎖，給我100把鑰匙，只有1把是對的。於是我每次隨機拿1把鑰匙去試，打不開就再換1把。我試的次數越多，打開（最優解）的機會就越大，但在打開之前，那些錯的鑰匙都是沒有用的。這個試鑰匙的演算法，就是拉斯維加斯的——盡量找最好的，但不保證能找到。​

三、結論​

•蒙特卡羅演算法   

：采樣越多，越近似最優解；

•拉斯維加斯演算法：采樣越多，越有機會找到最優解；​

這兩類隨機演算法之間的選擇，往往受到問題的局限。如果問題要求在有限采樣內，必須給出一個解，但不要求是最優解，那就要用蒙特卡羅演算法。反之，如果問題要求必須給出最優解，但對采樣沒有限制，那就要用拉斯維加斯演算法。​

D. 遺傳演算法、粒子群、模擬退火相比於普通的蒙特卡洛演算法有什麼優勢他們相互的優缺點都是什麼

他們有類似之處，但差別也不小。
蒙特卡洛演算法是數值計算方法，原理是利用隨機數來解決計算問題。與它對應的是確定性演算法。也就是說該種演算法屬於隨機演算法，得到的解是近似解。
而遺傳演算法、粒子群、模擬退火雖然也是隨機近似演算法，但這三種都是仿生智能演算法，且比蒙特卡洛演算法要復雜，應用的領域也不太相同。
顯然，蒙特卡洛演算法很輕巧，求解問題更快速。

E. 隨機性數學方法有哪些

隨機數學是研究隨機現象統計規律性的一個數學分支，涉及四個主要部分：概率論、隨機過程、數理統計、隨機運籌。概率論是後三者的基礎。則睜廳

4、舍伍德演算法 Sherwood

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

F. 隨機演算法

相關總結參見 http://www.jianshu.com/p/60ea83ea17cc

一個隨機演算法的最壞運行時間幾乎總是和非隨機化演算法的最壞情形運行時間相同。重要的區別在於，好的隨機化演算法沒有不好的輸入，而只有壞的隨機數（相對於特定的輸入）。
比如說：對於快速排序，方法A用第一個元素作為樞紐元，方法B使用隨機選出的元素作為樞紐元。

通過隨機化演算法，特定的輸入不再重要。重要的是隨機數，我們可以山敗前得到一個期望的運行時間，此時我們是對所有可能的隨機數取平均而不是對所有可能的輸入求平均。

隨機數有許多已知的統計性質；逗清偽隨機數滿足這些性質的大枯蔽部分。
真正需要的是隨機數的序列。這些數應該獨立地出現。

線性同餘數發生器
產生隨機數的最簡單的方法是線性同餘數發生器，由Lehmer於1951年提出：

例如：M = 11，x0 = 1
A = 7： 7， 5， 2， 3， 10， 4， 6， 9， 8， 1， 7 ，5 ，2... （周期為10 = M-1）
A = 5： 5， 3， 4， 9， 1， 5， 3， 4...（周期為5 < M -1）

一個有問題的隨機數發生器（返回(0,1)開區間值）：乘法溢出

工作在32位機器上的隨機數發生器

證明：為什麼δ(xi)或者是0，或者是1
為什麼僅當余項的值小於0時，δ(xi)=1
說明：因為這里是對M取余，所以是M的倍數則自然消掉；並且δ(xi)兩項都是取整函數，因此肯定為整數，另外xi+1總是介於1~M-1之間，因此當余項小於0，則取1

隨機化的第一個用途是以O(lgn)期望時間支持查找和插入的數據結構。
每個2^i 結點就有一個指針指向下一個2^i結點，總的指針個數僅僅是加倍，但現在在一次查找中最多考察floor(lgn)個結點。因此總的時間消耗為O(lgn)。
本質上是二分查找：

放鬆上面數據結構的結構條件，就構成了跳躍表：

如果我們想查找19是否存在？如何查找呢？我們從頭結點開始，首先和9進行判斷，此時大於9，然後和21進行判斷，小於21，此時這個值肯定在9結點和21結點之間，此時，我們和17進行判斷，大於17，然後和21進行判斷，小於21，此時肯定在17結點和21結點之間，此時和19進行判斷，找到了。

1）實現

2）空間大小耗費

3）查找
1-2-3跳躍表的實現特點：
在同一層級的鏈表（不超過3個結點）中找到首個大於item的結點，然後向下移一層。

4）插入
必須保證當一個高度為h的新結點加入進來時不會產生具有四個高度為h的結點的間隙。
插入採用2-3-4樹的自頂向下的方法（保證當前結點不是4-結點）：（參考 http://www.jianshu.com/p/8258ed821859 ）
設在第L層，並要降到下一層。如果下一層的間隙容量是3，則提高該間隙的中間項使其高度為L，從而形成兩個容量為1的間隙。由於這使得朝下刪除的道路上消除了容量為3的間隙，因此插入式安全的。

5）刪除
刪除採用2-3-4樹的自頂向下的方法（保證當前結點不是2-結點）：（參考 http://www.jianshu.com/p/8258ed821859 ）

確定一個大數是否是素數的問題。

結點包括：

具有最低優先順序的結點必然是根。樹是根據優先順序的N!種可能的排列而不是根據項的N!中排列形成的。

1）插入

插入之後，通過左旋和右旋恢復堆序性質：

2）刪除
這個刪除方法也可以採用紅黑樹的刪除方法，將刪除歸結為葉子節點的刪除。（使用後繼，這樣可以節省很多旋轉）