隨機化演算法

㈠ 12是不是一個隨機數（隨機化演算法里的題目）

是

㈡ 這題的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;
}

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

參見博文：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次的隨機在計算機程序中僅僅是一眨眼的功夫。可以看出，隨機化演算法有著廣闊的前景。只是由於隨機化演算法比較難於掌控，所以並不是很多人都接觸過他，但肯定有很多人都聽說過。

㈤ 隨機化的介紹

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

㈥ 隨機化的演算法

在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題：隨機。
計算機為我們提供好了隨機方法（部分計算器也提供了），那麼對於有些具有瑕疵的演算法，如果配上隨機化演算法的話，又是可以得到一樣不到的結果。
這種演算法看上去是憑著運氣做事，其實，隨機化演算法是有一定的理論基礎的，我們可以想像，在[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)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。

㈦ 隨機化演算法的舉例

下面，我們就隨機化問題，舉一個例子：
一個長度在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）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間復雜度維持在最好狀態。

㈧ 隨機化演算法的隨機化演算法概述

在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題： 隨機。
計算機為我們提供好了隨機方法（部分計算器也提供了），那麼對於有些具有瑕疵的演算法，如果配上隨機化演算法的話，又是可以得到意想不到的結果。

㈨ 隨機規劃的隨機規劃的求解方法

隨機規劃的求解方法大致分兩種。
第一種是轉化法，即將隨機規劃轉化成各自的確定性等價類，然後利用已有的確定性規劃的求解方法解之；
另一種是逼近方法，利用隨機模擬技術，通過一定的遺傳演算法程序，得到隨機規劃問題的近似最優解和目標函數的近似最優值。