蒙特卡羅算法之主元素問題

1、蒙特卡羅算法

 基本概述

       蒙特卡羅（Monte Carlo）方法，又稱随機抽樣或統計試驗方法。傳統的經驗方法由于不能逼近真實的實體過程，很難得到滿意的結果，而蒙特卡羅方法由于能夠真實地模拟實際實體過程，故解決問題與實際非常符合，可以得到很圓滿的結果。

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

     設p是一個實數，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一執行個體得到正确解的機率不小于p，則稱該蒙特卡羅算法是p正确的，且稱p-1/2是該算法的優勢。

     如果對于同一執行個體，蒙特卡羅算法不會給出2個不同的正确解答，則稱該蒙特卡羅算法是一緻的。

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

    對于一個一緻的P正确蒙特卡羅算法，要提高獲得正确率的機率，隻要執行該算法若幹次，并選擇出現頻次最高的解即可。

原理思想

      當所要求解的問題是某種事件出現的機率，或者是某個随機變量的期望值時，它們可以通過某種“試驗”的方法，得到這種事件出現的頻率，或者這個随機變數的平均值，并用它們作為問題的解。這就是蒙特卡羅方法的基本思想。蒙特卡羅方法通過抓住事物運動的幾何數量和幾何特征，利用數學方法來加以模拟，即進行一種數字模拟實驗。它是以一個機率模型為基礎，按照這個模型所描繪的過程，通過模拟實驗的結果，作為問題的近似解。

 主要步驟

     蒙特卡羅解題歸結為三個主要步驟：構造或描述機率過程；實作從已知機率分布抽樣；建立各種估計量。

     1)構造或描述機率過程： 對于本身就具有随機性質的問題，如粒子輸運問題，主要是正确描述和模拟這個機率過程，對于本來不是随機性質的确定性問題，比如計算定積分，就必須事先構造一個人為的機率過程，它的某些參量正好是所要求問題的解。即要将不具有随機性質的問題轉化為随機性質的問題。

     2)實作從已知機率分布抽樣： 構造了機率模型以後，由于各種機率模型都可以看作是由各種各樣的機率分布構成的，是以産生已知機率分布的随機變量（或随機向量），就成為實作蒙特卡羅方法模拟實驗的基本手段，這也是蒙特卡羅方法被稱為随機抽樣的原因。最簡單、最基本、最重要的一個機率分布是(0,1)上的均勻分布（或稱矩形分布）。随機數就是具有這種均勻分布的随機變量。随機數序列就是具有這種分布的總體的一個簡單子樣，也就是一個具有這種分布的互相獨立的随機變數序列。産生随機數的問題，就是從這個分布的抽樣問題。在計算機上，可以用實體方法産生随機數，但價格昂貴，不能重複，使用不便。另一種方法是用數學遞推公式産生。這樣産生的序列，與真正的随機數序列不同，是以稱為僞随機數，或僞随機數序列。不過，經過多種統計檢驗表明，它與真正的随機數，或随機數序列具有相近的性質，是以可把它作為真正的随機數來使用。由已知分布随機抽樣有各種方法，與從(0,1)上均勻分布抽樣不同，這些方法都是借助于随機序列來實作的，也就是說，都是以産生随機數為前提的。由此可見，随機數是我們實作蒙特卡羅模拟的基本工具。 建立各種估計量： 一般說來，構造了機率模型并能從中抽樣後，即實作模拟實驗後，我們就要确定一個随機變量，作為所要求的問題的解，我們稱它為無偏估計。  

     3)建立各種估計量：相當于對模拟實驗的結果進行考察和登記，從中得到問題的解。 

 2、主元素問題

  問題描述

     設T[1:n]是一個含有n個元素的數組。當|{i|T[i]=x}|>n/2時，稱元素x是數組T的主元素。 例如：數組T[]={5,5,5,5,5,5,1,3,4,6}中，元素T[0:5]為數組T[]的主元素。

  問題求解

      算法随機選擇數組元素x,由于數組T的非主元素個數小于n/2，是以，x不為主元素的機率小于1/2。是以判定數組T的主元素存在性的算法是一個偏真1/2正确的算法。50%的錯誤機率是不可容忍的，利用重複調用技術将錯誤機率降低到任何可接受的範圍内。對于任何給定的

>0，算法majorityMC重複調用

次算法majority。它是一個偏真蒙特卡羅算法，且其錯誤機率小于

。算法majorityMC所需的計算時間顯然是

。

代碼實作：

//随機化算法 蒙特卡羅算法 主元素問題
//#include "stdafx.h"
#include "RandomNumber.h"
#include 
#include 
using namespace std;
 
//判定主元素的蒙特卡羅算法
template
bool Majority(Type *T,int n)
{
    RandomNumber rnd;
    int i = rnd.Random(n);
 
    Type x = T[i];    //随機選擇數組元素
    int k = 0;
 
    for(int j=0; j    {
        if(T[j] == x)
        {
            k++;
        }
    }
 
    return (k>n/2);    //k>n/2時，T含有主元素
}
 
//重複k次調用算法Majority
template
bool MajorityMC(Type *T,int n,double e)
{
    int k = ceil(log(1/e)/log((float)2));
    for(int i=1; i<=k; i++)
    {
        if(Majority(T,n))
        {
            return true;
        }
    }
    return false;
}
 
int main()
{
    int n = 10;
    float e = 0.001;
    int a[] = {5,5,5,5,5,5,1,3,4,6};
    cout<<"數組a的元素如下："<    for(int i=0; i<10; i++)
    {
        cout<    }
    cout<    cout<<"調用MajorityMC判斷數組是否含有主元素結果是："<}      

View Code

#include"time.h"
//随機數類
const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
 
class RandomNumber
{
    private:
        //目前種子
        unsigned long randSeed;
    public:
        RandomNumber(unsigned long s = 0);//構造函數，預設值0表示由系統自動産生種子
        unsigned short Random(unsigned long n);//産生0：n-1之間的随機整數
        double fRandom(void);//産生[0,1)之間的随機實數
};
 
RandomNumber::RandomNumber(unsigned long s)//産生種子
{
    if(s == 0)
    {
        randSeed = time(0);//用系統時間産生種子
    }
    else
    {
        randSeed = s;//由使用者提供種子
    }
}
 
unsigned short RandomNumber::Random(unsigned long n)//産生0：n-1之間的随機整數
{
    randSeed = multiplier * randSeed + adder;//線性同餘式
    return (unsigned short)((randSeed>>16)%n);
}
 
double RandomNumber::fRandom(void)//産生[0,1)之間的随機實數
{
    return Random(maxshort)/double(maxshort);
}      

View Code

實作結果：