我们平时用到的程序几乎都是一个步骤紧跟着另一个具体的步骤,它们是绝对客观和条理清晰的,展现着算法创作者的理性之美。但在现实生活中,我们也能遇到一些看似不能优化的,找不到潜在规律的复杂问题,这类问题的解法规模还非常大,直接计算的话甚至让计算机吃不消。

聪明的计算机科学家另辟蹊径,完全放弃理性思维,这也可以被视为最后一招,搏杀战术 —— 随机算法。因为人们发现,随机算法的效果有时比确定性算法效率更高,因为计算机可以在瞬间生成大量的模拟数据。



在核反应的过程中,原子核,质子,高能电子,中子相互作用,产生更多的不稳定原子核。我们简单地认为,一个粒子分裂成两份不同的新粒子,这两个新的粒子带着巨大的能量去轰击周围其他的粒子,但是具体轰击的是哪一个粒子因为粒子状态的不同是不确定的,这类现象变成连锁反应,粒子规模迅速变大。想要推测出某一温度,某一时刻的核反应状态几乎是无法完成的。上个世纪,科学全才冯·诺依曼和乌拉姆,尼古拉斯共同提出了蒙特卡洛(罗)算法,专门用于解决这类极度复杂,规模巨大的问题。它的名字由摩纳哥举世闻名的赌城 —— 蒙特卡洛而来,正好暗示了方法中的随机性。

今天,蒙特卡洛算法已经成为了科学计算的基石之一。下面例子中的算法均由C++实现。

随机算法

构造形如

a a a a b
a a a a b
...
a a a a b
c c c c d

的矩阵,使得每一行,每一列的平方和都是某个数字的平方。

思路:用计算机生成随机数去尝试匹配条件。

问题来源:codeforces 418 C Square Table (随机算法)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

bool IsSquare( int a) 
{
    int k = (int)sqrt(a);
    if( k*k == a )  return 1;
    return 0;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int a,b,c,d;
        while( 2 > 1 ) {
            a = rand()%100 + 1;
            b = rand()%100 + 1;
            c = rand()%100 + 1;
            d = rand()%100 + 1;
            int s1 = (m-1)*a*a + b*b;
            int s2 = (n-1)*a*a + c*c;
            int s3 = (m-1)*c*c + d*d;
            int s4 = (n-1)*b*b + d*d;
            if( IsSquare( s1 ) && IsSquare( s2 ) && 
                IsSquare( s3 ) && IsSquare( s4 ) )
            {
                break;
            }
        }

        for(int i=0;i<n-1;i++){
            for(int j=0;j<m-1;j++) printf("%d ",a);
            printf("%d\n",b);
        }
        for(int j=0;j<m-1;j++) printf("%d ",c);
        printf("%d\n",d);
    }
    return 0;
}



模拟退火算法

最小圆覆盖,大意:给出一些点,求出能覆盖他们的最小的圆。输出圆心和半径。

思路:不断变化圆心,计算出点到圆心的距离更新半径。经过一系列迭代,找到答案。

问题来源:hdu 3007 Buried memory

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps=1e-7,INF=1e99;  // T: 初始温度  delta:下降速率
const double T=10,delta=0.88;    //一般地,T=100, delta=0.98
const int N=5e2+10;

struct point{
    double x,y;
}p[N],s;

double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double solve(int n){
    s=p[0];
    double t=T;
    double r=INF;
    while(t>eps){
        int k=0;
        double d=0;
        for(int i=0;i<n;i++){
            double f=dis(s,p[i]);
            if(f>d){
                d=f;
                k=i;
            }
        }
        s.x+=(p[k].x-s.x)/d*t;
        s.y+=(p[k].y-s.y)/d*t;
        r=min(r,d);
        t*=delta;
    }
    return r;
}

int main()
{
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++){
            scanf("%lf %lf",&p[i].x,&p[i].y);
        }
        double r=solve(n);
        printf("%.2lf %.2lf %.2lf\n",s.x,s.y,r);
    }
    return 0;
}

更多有关冯·诺依曼的文章:冯·诺依曼: 用分治算法打破平方时间的诅咒


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

You cannot copy content of this page