隨機化演算法

Ⅰ 隨機化演算法的介紹

隨機化演算法是這樣一種演算法，在演算法中使用了隨機函數，且隨機函數的返回值直接或者間接的影響了演算法的執行流程或執行結果。隨機化演算法基於隨機方法，依賴於概率大小。

Ⅱ 常見的隨機化方法包括

隨機抽樣：按照隨機的原則，即保證總體中每個單位都有同等機會被抽中的原則抽取樣本的方法。隨機抽樣又分為純隨機抽樣、分層抽樣、系統抽樣、整群抽樣、多階段抽樣等。
簡單隨機分組（simple randomization）：可將研究對象以個人為單位用擲硬幣（正、反兩面分別指定為實驗組和對照組）、抽簽、使用隨機數字表，也可採用系統隨機化法，即用現成的數據（如研究對象順序號、身份證號、病歷卡號、工號、學號等）交替隨機分配到實驗組和對照組中去。隨機分組後，當樣本量較大時，每組不完全相等，一般可進行實驗研究，當樣本量較小時，每組內個體數量相差較大，則需要再重新隨機分組，直至達到預定的均衡要求。

Ⅲ 隨機化的演算法

在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題：隨機。
計算機為我們提供好了隨機方法（部分計算器也提供了），那麼對於有些具有瑕疵的演算法，如果配上隨機化演算法的話，又是可以得到一樣不到的結果。
這種演算法看上去是憑著運氣做事，其實，隨機化演算法是有一定的理論基礎的，我們可以想像，在[1,10000]這個閉區間里，隨機1000次，隨機到2這個數的幾率是多大，何況1000次的隨機在計算機程序中僅僅是一眨眼的功夫。可以看出，隨機化演算法有著廣闊的前景。只是由於隨機化演算法比較難於掌控，所以並不是很多人都接觸過他，但肯定有很多人都聽說過。
下面，我們就隨機化問題，舉一個例子：
一個長度在4..10的字元串中，需要判定是否可以在字元串中刪去若干字元，使得改變後字元串符合以下條件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：長度為6字元串「POPKDK」，若刪除其中的「O」，「D」兩個字母，則原串變為：「PPKK」，符合條件（2）AABB。
分析：
這道題很容易想到一種演算法：運用排列組合：枚舉每4個字母，然後逐一判斷。演算法是可行的，但是如果需要題目中加上一句話：需要判斷n個字元串，且n<=100000，那麼這樣的耗時是不能讓人忍受①的，因為在枚舉的過程中，是非常浪費時間的。
(①：這里是指信息學中要求演算法的普遍運算時間為：1000ms）
所以這道題有可能可以藉助於隨機化演算法，下面我們來算一下在10個組符中取4個字元一共有多少種取法：C(4,10)=210。那麼很容易得知，隨機化演算法如果隨機100次，能都到的結果基本上就正確了，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重復即可，判重的時間復雜度也為O(1)，並且最多隨機100次，這樣就可以有效地得到答案，最大運算次數為：O(100n)，這是在計算機的承受范圍內（1000ms）的。
從這里就能看出，隨機化演算法是一個很好的概率演算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的演算法：例如貪心、搜索等配合起來運用。
再舉一個例子：
排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間復雜度為O(n㏒n)，這里的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。

Ⅳ 簡述常用的隨機化方法

隨機模擬：蒙特卡羅法蒙特卡羅(MonteCarlo)法也稱為隨機模擬方法.它的基本思想是,為了求解數學、物理、工程技術以及生產管理等方面的問題,首先建立一個概率模型或隨機過程,使它的參數等於問題的解。蒙特卡洛(Monte Carlo)模擬是一種通過設定隨機過程，反復生成時間序列，計算參數估計量和統計量，進而研究其分布特徵的方法。具體的，當系統中各個單元的可靠性特徵量已知，但系統的可靠性過於復雜，難以建立可靠性預計的精確數學模型或模型太復雜而不便應用時，可用隨機模擬法近似計算出系統可靠性的預計值；隨著模擬次數的增多，其預計精度也逐漸增高。由於涉及到時間序列的反復生成，蒙特卡洛模擬法是以高容量和高速度的計算機為前提條件的，因此只是在近些年才得到廣泛推廣。

Ⅳ 隨機化演算法 隨機數的概念是什麼

顧名思義.隨機數就是隨機生成的一個數字.不是人為生成的.這個隨機數在產生之前.是不為人知的.

隨機化演算法是這樣一種演算法，在演算法中使用了隨機函數，且隨機函數的返回值直接或者間接的影響了演算法的執行流程或執行結果。隨機化演算法基於隨機方法，依賴於概率大小。

Ⅵ 隨機化演算法的舉例

下面，我們就隨機化問題，舉一個例子：
一個長度在4..10的字元串中，需要判定是否可以在字元串中刪去若干字元，使得改變後字元串符合以下條件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：長度為6字元串「POPKDK」，若刪除其中的「O」，「D」兩個字母，則原串變為：「PPKK」，符合條件（2）AABB。
分析：
這道題很容易想到一種演算法：運用排列組合：枚舉每4個字母，然後逐一判斷。演算法是可行的，但是如果需要題目中加上一句話：需要判斷n個字元串，且n<=100000，那麼這樣的耗時是不能讓人忍受①的，因為在枚舉的過程中，是非常浪費時間的。
（①：這里是指信息學中要求演算法的普遍運算時間為：1000ms）
所以這道題有可能可以藉助於隨機化演算法，下面我們來算一下在10個字元中取4個字元一共有多少種取法：C(4,10)=210。那麼很容易得知，隨機化演算法如果隨機300次，能得到的結果基本上就正確了(概率為1-(209/210)^300，約為0.76)，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重復即可，判重的時間復雜度也為O(1)，並且最多隨機300次，這樣就可以有效地得到答案，最大運算次數為：O(300n)，這是在計算機的承受范圍內（1000ms）的。
從這里就能看出，隨機化演算法是一個很好的概率演算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的演算法：例如貪心、搜索等配合起來運用。 排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間復雜度為O(n㏒n)，這里的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。
運用在：
（1）數據讀入時，隨機排放數據位置。
（2）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間復雜度維持在最好狀態。

Ⅶ 數值隨機化演算法求非線性方程組

參見博文：http://blog.csdn.net/liufeng_king/article/details/9029091
//隨機化演算法 解線性方程組
#include "stdafx.h"
#include "RandomNumber.h"
#include <iostream>
using namespace std;

bool NonLinear(double *x0,double *dx0,double *x,double a0,
double epsilon,double k,int n,int Steps,int M);
double f(double *x,int n);

int main()
{
double *x0, //根初值
*x, //根
*dx0, //增量初值
a0 = 0.0001, //步長
epsilon = 0.01, //精度
k = 1.1; //步長變參
int n = 2, //方程個數
Steps = 10000, //執行次數
M = 1000; //失敗次數

x0 = new double[n+1];
dx0 = new double[n+1];
x = new double[n+1];

//根初值
x0[1] = 0.0;
x0[2] = 0.0;

//增量初值
dx0[1] = 0.01;
dx0[2] = 0.01;

cout<<"原方程組為："<<endl;
cout<<"x1-x2=1"<<endl;
cout<<"x1+x2=3"<<endl;

cout<<"此方程租的根為："<<endl;

bool flag = NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);
while(!flag)
{
flag = NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);
}
for(int i=1; i<=n; i++)
{
cout<<"x"<<i<<"="<<x[i]<<" ";
}
cout<<endl;

return 0;
}

//解非線性方程組的隨機化演算法
bool NonLinear(double *x0,double *dx0,double *x,double a0,
double epsilon,double k,int n,int Steps,int M)
{
static RandomNumber rnd;
bool success; //搜索成功標志
double *dx,*r;

dx = new double[n+1]; //步進增量向量
r = new double[n+1]; //搜索方向向量
int mm = 0; //當前搜索失敗次數
int j = 0; //迭代次數
double a = a0; //步長因子

for(int i=1; i<=n; i++)
{
x[i] = x0[i];
dx[i] = dx0[i];
}

double fx = f(x,n); //計算目標函數值
double min = fx; //當前最優值

while(j<Steps)
{
//(1)計算隨機搜索步長
if(fx<min)//搜索成功
{
min = fx;
a *= k;
success = true;
}
else//搜索失敗
{
mm++;
if(mm>M)
{
a /= k;
}
success = false;
}

if(min<epsilon)
{
break;
}

//(2)計算隨機搜索方向和增量
for(int i=1; i<=n; i++)
{
r[i] = 2.0 * rnd.fRandom()-1;
}

if(success)
{
for(int i=1; i<=n; i++)
{
dx[i] = a * r[i];
}
}
else
{
for(int i=1; i<=n; i++)
{
dx[i] = a * r[i] - dx[i];
}
}

//(3)計算隨機搜索點
for(int i=1; i<=n; i++)
{
x[i] += dx[i];
}

//(4)計算目標函數值
fx = f(x,n);
j++;
}

if(fx<=epsilon)
{
return true;
}
else
{
return false;
}
}

double f(double *x,int n)
{
return (x[1]-x[2]-1)*(x[1]-x[2]-1)
+(x[1]+x[2]-3)*(x[1]+x[2]-3);
}

Ⅷ 隨機化演算法的定義：

這種演算法看上去是憑著運氣做事，其實，隨機化演算法是有一定的理論基礎的，我們可以想像，在[1,10000]這個閉區間里，隨機1000次，隨機到2這個數的幾率是多大(約為0.001)，何況1000次的隨機在計算機程序中僅僅是一眨眼的功夫。可以看出，隨機化演算法有著廣闊的前景。只是由於隨機化演算法比較難於掌控，所以並不是很多人都接觸過他，但肯定有很多人都聽說過。

Ⅸ 這題的c語言源代碼，還有解題思想，隨機化演算法，麻煩手打，謝謝

//隨機化演算法用隨機投點法計算定積分

#include<stdio.h>
#include<math.h>
#include<time.h>//使用當前時鍾做種子

doubleDarts(intn,doublea,doubleb);
doublef(doublex);//積分函數

main(){
	inti,n[5]={100,1000,1000,10000,10000000};//隨機投點個數,個數越多結果越精確
	doublea=1.0,b=2.0;//積分上下界
	srand((unsigned)time(NULL));//初始化隨機數
	for(i=0;i<5;i++)
		printf("%d:	n=%d	r=%lf
",i+1,n[i],Darts(n[i],a,b));
}

/*基本思想是在矩形區域內隨機均勻投點，求出由這些點
*產生的函數值的算術平均值，再乘以區間寬度，即可得
*出定積分的近似解
*/
doubleDarts(intn,doublea,doubleb)
{
	inti;
	doublesum=0.0;
	for(i=0;i<n;i++){
		doublex=(b-a)*rand()+a;//產生[a,b)之間的隨機數
		sum=sum+f(x);
	}
	return(b-a)*sum/n;
}

doublef(doublex){
	returnsin(x)/x;
}