随机化算法

㈠ 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）中间点的枚举进行多次随机化后决定。
这样就基本上将快速排序的时间复杂度维持在最好状态。

㈧ 随机化算法的随机化算法概述

在我们的生活中，人们经常会去掷色子来看结果，投硬币来决定行动，这就牵涉到一个问题： 随机。
计算机为我们提供好了随机方法（部分计算器也提供了），那么对于有些具有瑕疵的算法，如果配上随机化算法的话，又是可以得到意想不到的结果。

㈨ 随机规划的随机规划的求解方法

随机规划的求解方法大致分两种。
第一种是转化法，即将随机规划转化成各自的确定性等价类，然后利用已有的确定性规划的求解方法解之；
另一种是逼近方法，利用随机模拟技术，通过一定的遗传算法程序，得到随机规划问题的近似最优解和目标函数的近似最优值。