舍伍德演算法是的一種

『壹』 隨機性數學方法有哪些

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

4、舍伍德演算法 Sherwood

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

『貳』 (六) 概率演算法

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

概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下， 可將概率演算法大致分為四類：數值概率演算法、蒙特卡羅(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

數值概率演算法的應用

舍伍德演算法的應用

拉斯維加斯演算法的應用

蒙特卡羅演算法的應用

『叄』 舍伍德演算法的基本思想

設A是一個確定性演算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是演算法A的輸入規模為n的實例的全體，則當問題的輸入規模為n時，演算法A所需的平均時間為這顯然不能排除存在x∈Xn使得 tA(x)>>tA(n)的可能性。
希望獲得一個概率演算法B，使得對問題的輸入規模為n的每一個實例均有
這就是舍伍德演算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德演算法可獲得很好的平均性能。
舍伍德演算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定演算法中引入隨機性將它改造成一個舍伍德演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。

『肆』 演算法具有確定性,因此在寫演算法中一定不能包含隨機數調用的函數

錯的，這里舉個例子吧：隨機快速排序，每次隨機取一個值作為排序分類標准把當前區間拆成兩部分，但是最後它還是會排好序，是一個具有確定結果的演算法，只是得到結果的過程隨機。
希望能幫到你。

『伍』 舍伍德演算法的總結

採用數組模擬有序鏈表，它本質上是利用兩個數組，一個存儲數據，一個存儲其後繼在數組中的位置，對於查找指定元素，採用舍伍德演算法可在0(n)時間內完成，採用順序存儲結構時，若數組元素無序，則只能順序查找，需O(n)時間，若數組元素有序，可進行二分法查找，其時問復雜度雖然降為0(logn)，但卻在進行插入和刪除元素時，需要移動大量元素。與鏈式存儲相比，插入和刪除時雖然都不需要移動元素，但在查找上，其時間性能由0(n)降為O(n)，可見採用數組模擬有序鏈表，並採用舍伍德演算法進行查找刪除具有比較高的效率。它不失為一種高效韻數據結構。

『陸』 有哪些隨機數演算法呢

1、數值概率演算法：用於數值問題的求解。所得到的解幾乎都是近似解，近似解的精度
隨著計算時間的增加而不斷地提高。
2、拉斯維加斯演算法（LasVegas）：要麼給出問題的正確答案，要麼得不到答案。反復求解多次，可
使失效的概率任意小。
3、蒙特卡羅演算法（MonteCarlo）：總能得到問題的答案，偶然產生不正確的答案。重復運行，每一次
都進行隨機選擇，可使不正確答案的概率變得任意小。
4、舍伍德演算法（Sherwood）：很多具有很好的平均運行時間的確定性演算法，在最壞的情況下性能很
壞。引入隨機性加以改造，可以消除或減少一般情況和最壞情況的差別。

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

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