陕西省两学一做网站,产品推广方案,seo关键词工具,想要做网站模拟退火学习 作业部落网上讲的不错的(他好像还有一些其他的东西、、、) 引入 对于一些题目#xff0c;无法直接算出答案或者想不到正解#xff0c;想到随机找答案#xff0c;那么模拟退火就是一种有系统方法的随机算法 没用的不需要了解的来源 百度百科...... 模拟退火算法…模拟退火学习 作业部落网上讲的不错的(他好像还有一些其他的东西、、、) 引入 对于一些题目无法直接算出答案或者想不到正解想到随机找答案那么模拟退火就是一种有系统方法的随机算法 没用的不需要了解的来源 百度百科...... 模拟退火算法来源于固体退火原理是一种基于概率的算法将固体加温至充分高再让其徐徐冷却加温时固体内部粒子随温升变为无序状内能增大而徐徐冷却时粒子渐趋有序在每个温度都达到平衡态最后在常温时达到基态内能减为最小。 几个要记下来的东西 温度大概理解为答案的波动范围看是否会接受不那么好的解爬山算法找很多个答案起点遇到峰值就记录答案最后找最大(小)答案 用途 数据范围不大但爆搜显然过不了的题目有一定的求解规律但又不完全符合规律的题目多峰函数题或者算数几何之类的题目题目想不出退火总比爆0好的题目 主要思想 把当前答案看成一只退火兔一开始很急躁(温度很高)所以答案到处乱跑(这中间会记录最优解)最后兔子慢慢冷静下来(温度逐渐降低)就找到答案利用rand来寻找答案接受劣解的波动范围(当然T也是一个决定性参数)退火找答案之后可能会有更优答案在自己周围很近的地方所以rand去周围看一看是否更优一开始根据自己的猜测来找一个答案“开始”点可以降低一定时间复杂度...... 板子 我只讲大致的思想具体实现根据模板题及luogu的题解讲述来学习吧主要是懒 first luogu板子题平衡点/吊打xxx 然后我的优美代码...... #includeiostream
#includecstdlib
#includecstdio
#includecmath
#includecstring
#includeiomanip
#includealgorithm
#includectime
#includequeue
#includestack
#includevector
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define cold 0.99
#define N 1050
#define RD T*((rand()1)-RAND_MAX)//rand一个-T到T的数,随机跳多远
#define Time() (ldb)clock()/(ldb)CLOCKS_PER_SEC
using namespace std;
const int Inf1e9;int n;
ldb ansx,ansy,ans;
ldb etlx,etly,etl;
struct WEI{ldb x,y,m;
}ljl[N];il int read()
{rg int s0,m0;rg char chgetchar();while(ch0||ch9){if(ch-)m1;chgetchar();}while(ch0ch9)s(s3)(s1)(ch^48),chgetchar();return m?-s:s;
}il ldb f(rg ldb xx,rg ldb yy)
{rg ldb res0;for(rg int i1;in;i){rg ldb dxxx-ljl[i].x,dyyy-ljl[i].y;ressqrt(dx*dxdy*dy)*ljl[i].m;}return res;
}int main()
{srand(time(NULL));nread();for(rg int i1;in;i){scanf(%Lf%Lf%Lf,ljl[i].x,ljl[i].y,ljl[i].m);ansxljl[i].x,ansyljl[i].y;}etlxansxansx/n,etlyansyansy/n;etlansf(ansx,ansy);while(Time()0.3){rg ldb nansetl,nxetlx,nyetly;for(rg ldb T1000;T1e-16;T*cold){rg ldb xxnxRD,yynyRD;//模拟退火答案的波动范围rg ldb resf(xx,yy);//找答案的ansif(ansres)ansres,ansxxx,ansyyy;//更新答案if(nansres||exp((res-nans)/T)*RAND_MAXrand())nansres,nxxx,nyyy;}}printf(%.3Lf %.3Lf\n,ansx,ansy);return 0;
} second 有难度luogu均分数据 #includeiostream
#includecstdlib
#includecstdio
#includecmath
#includecstring
#includeiomanip
#includealgorithm
#includectime
#includequeue
#includestack
#includevector
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 25
#define M 10
#define Time() (ldb)clock()/(ldb)CLOCKS_PER_SEC
using namespace std;
const int Inf1e5;int n,m;
ldb tot,ansInf;
ldb v[N],sum[N];
ldb dp[N][N];il int read()
{rg int s0,m0;rg char chgetchar();while(ch0||ch9){if(ch-)m1;chgetchar();}while(ch0ch9)s(s3)(s1)(ch^48),chgetchar();return m?-s:s;
}il ldb PF(rg ldb x){return x*x;}
il ldb sol()
{for(rg int i1;in;i)sum[i]sum[i-1]v[i];for(rg int i0;in;i)for(rg int j0;jm;j)dp[i][j]Inf;dp[0][0]0;for(rg int i1;in;i)for(rg int j1;jm;j)for(rg int k0;ki;k)dp[i][j]min(dp[i][j],dp[k][j-1]PF(sum[i]-sum[k]-tot));ansmin(ans,dp[n][m]);return dp[n][m];
}il void SA(rg ldb T)
{rg ldb nansans;for(;T1e-3;T*0.98){rg int xx1rand()%n,yy1rand()%n;if(xxyy)continue;swap(v[xx],v[yy]);rg ldb ressol();if(resnans||exp((res-nans)/T)*rand()-RAND_MAX0)nansres;else swap(v[xx],v[yy]);}
}int main()
{nread(),mread();for(rg int i1;in;i)v[i]read(),totv[i];tot/m,sol();while(Time()0.3)SA(1000);printf(%.2Lf\n,sqrt(ans/m));return 0;
} 转载于:https://www.cnblogs.com/cjoierljl/p/9394519.html
