Hdu5017模拟退火

=。= 之前做过有关果蝇算法的东西,然后发现这俩个其实就是一个东西。。。当时都没想啊,其实想到都不一定能撸对。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include<math.h>
using namespace std;
#define eps 1e-9
double a, b, c, d, e, f, z1, z2;
const int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
const int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int solvez(double x,double y)
{
    double A = c ,
    B = e * x + d * y,
    C = a * x * x + b * y * y + f * x * y - 1;
    double dlt = B * B - 4 * A * C;
    if (dlt < 0) return 0;
    z1 = (-B + sqrt(dlt)) / 2 / A,
    z2 = (-B - sqrt(dlt)) / 2 / A;
    if(z1 * z1 > z2 * z2) swap(z1, z2);
    return 1;
}

double dist(double x, double y, double z)
{
    return sqrt(x * x + y * y + z * z) ;
}
void gao(double x,double y)
{
    double Rand = 1.0;
    int flag = solvez(x , y);
    double Min = z1;
    while(Rand > eps) {
        double x1 = x ; double y1 = y;
        for(int i = 0; i < 8; i++) {
            double xx = x1 + dx[i] * Rand; double yy = y1 + dy[i] * Rand;
            if(!solvez(xx , yy)) continue;
            double dis = dist(xx, yy, z1);
            if(dis < Min) Min = dis, x = xx, y = yy;
        }
        Rand *= 0.99;
    }
    printf("%f\n",Min);
}

int main()
{
    while(cin >> a >> b >> c >> d >> e >> f){
        gao(0, 0);
    }
    return 0;
}
时间: 09-14

Hdu5017模拟退火的相关文章

poj-2420 A Star not a Tree?(模拟退火算法)

题目链接: A Star not a Tree? Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5219   Accepted: 2491 Description Luke wants to upgrade his home computer network from 10mbs to 100mbs. His existing network uses 10base2 (coaxial) cables that allo

POJ 3087 Shuffle&#39;m Up(模拟退火)

Description A common pastime for poker players at a poker table is to shuffle stacks of chips. Shuffling chips is performed by starting with two stacks of poker chips, S1 and S2, each stack containing C chips. Each stack may contain chips of several

PKU 1379 Run Away(模拟退火算法)

题目大意:原题链接 给出指定的区域,以及平面内的点集,求出一个该区域内一个点的坐标到点集中所有点的最小距离最大. 解题思路:一开始想到用随机化算法解决,但是不知道如何实现.最后看了题解才知道原来是要用模拟退火算法解决. 不过个人感觉这个算法的实现过程中仍然采用了随机化算法.二者均属于概率算法.  参考链接 Point Goto_Rand_Dir(double key,Point temp)函数中,Point temp必须得定义在参数中,不能定义在函数内部, 否则temp没有初始值,无法进行后面的

[POJ2069]Super Star(模拟退火)

题目链接:http://poj.org/problem?id=2069 题意:求一个半径最小的球,使得它可以包围住所有点. 模拟退火,圆心每次都去找最远那个点,这样两点之间的距离就是半径,那么接下来移动的方向肯定就是朝着这个最远点移动,保证比例相同且在球内的情况下移动. 不看题解想不到,这个东西有点难啊... 1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <

两种改进的模拟退火算法求解大值域约束满足问题1.0

0引言 约束满足问题(Constraint Satisfaction Problem,CSP)是人工智能研究领域中一个非常重要的分支,现已成为理论计算机科学.数学和统计物理学等交叉学科研究中的热点问题.人工智能.计算机科学和自动控制等领域中的许多问题都可以归结为约束满足问题.同时,约束满足问题在实际问题如模式识别.决策支持.物流调度及资源分配等领域也有着非常广泛的应用. CSP由一个变量集合和一个约束集合组成.每个变量都有一个非空的可能值域,每个约束描述了一个变量子集与子集内各变量的相容赋值,所

模拟退火算法

一.导读 1.基本思想 模拟热力学当中的退火过程 退火过程: 物体:高温   缓慢下降  低温 高能状态            低能状态 淬火:快速冷却,使金属处于高能状态,较硬易断 退火:缓慢冷却,使金属处于低能状态,较为柔韧 2.模拟退火在SA中的应用 在SA中将目标函数作为能量函数 模拟: 初始高温---->温度缓慢下降---->终止在低温 这时能量函数达到极小,目标函数最小 二.退火过程和Bolzman方程 1.热力学中的退火过程 变温物体缓慢降温从而达到分子之间能量最低的状态 设热力

Matlab随笔之模拟退火算法

问题描述: 我方有一个基地,经度和纬度为( 70,40).假设我方飞机的速度为 1000 公里/小时. 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地.在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长). 这是一个旅行商问题.我们依次给基地编号为 1,敌方目标依次编号为 2, 3,…, 101, 最后我方基地再重复编号为 102(这样便于程序中计算). 距离矩阵 D = ( dij )102×102 , 其中 dij 表示表示 i, j 两

模拟退火求解TSP问题&lt;2变换法产生路径&gt;

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">模拟退火解TSP</span> <span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"></span&g

hdu5017 Ellipsoid(旋转)

比赛的时候跳进这个大坑里,最后代码是写出来了.看到好像很多都是模拟退火做的,下面提供一个奇怪的思路吧. ax^2+by^2+cz^2+dyz+exz+fxy=1(*) 通过一些奇特的YY我们可以知道这是由一个标准的椭球ax^2+by^2+cz^2=1旋转得到的,之所以有交叉项是因为绕了X,Y,Z轴旋转,所以我们的想法是要是能将这个椭球旋回去那么就可以知道最短的距离了. 首先我们是旋转z轴,希望使得xy项消掉,这个时候令z=0可以得到  ax^2+by^2+fxy=1 通过一些椭圆的旋转知识我们可