原理
模拟退火：是一种随机算法，用于解决最优化问题。要求求解的问题对应的函数要有连续性。
模拟退火算法是模拟物理过程，有如下参数：
（1）温度t：即步长。分为初始温度和终止温度，对应代码中就是初始搜索范围和终止搜索的范围。
（2）衰减系数：每次搜索范围减小的比例，是(0, 1)中的一个数，可以取0.999，需要手动调节。
在每次迭代的过程中，我们在给定步长区间内随机一个新点，令dt = f(新点)-f(当前点)，如果求函数极小值的话，分为两种情况：
（1）dt<0，则跳到新点；
（2）dt>0，则以一定该概率跳到该点，且dt越大，跳过去的概率越低。
跳过去的概率值可以取为 e − d t / t e^{-dt/t} e−dt/t。
模拟退火的过程可能会收敛到局部最优解，但是这个过程我们可以做多次，这样收敛到局部最优解的概率就很小了。比如达到局部最优解的概率是0.99，则我们做1000次，达到局部最优解的概率是： 0.9 9 1000 ≈ 4.3 × 1 0 − 5 0.99^{1000} \approx 4.3 \times 10^{-5} 0.991000≈4.3×10−5。
2. AcWing上的模拟退火题目
AcWing 3167. 星星还是树
问题描述
问题链接：AcWing 3167. 星星还是树
分析
本题求解的这个点是费马点，即到所有点距离和最小的点。如果是一维的，排个序找中位数即可。
可以证明，这个函数是个凸函数，具有连续性。使用模拟退火求解即可。
代码
C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#define x first
#define y second
using namespace std
typedef pair<double, double>PDD
const int N = 110
int n
PDD q[N]
double ans = 1e8
// 返回[l, r]之间的随机小数
double rand(double l, double r) {
return (double)rand() / RAND_MAX * (r - l) + l
}
double get_dist(PDD a, PDD b) {
double dx = a.x - b.x, dy = a.y - b.y
return sqrt(dx * dx + dy * dy)
}
// 计算p到给定点的距离和
double calc(PDD p) {
double res = 0
for (int i = 0i <ni++)
res += get_dist(p, q[i])
ans = min(ans, res)
return res
}
void simulate_anneal() {
PDD cur(rand(0, 10000), rand(0, 10000))
for (double t = 1e4t >1e-4t *= 0.9) {
PDD np(rand(cur.x - t, cur.x + t), rand(cur.y - t, cur.y + t))
double dt = calc(np) - calc(cur)
if (exp(-dt / t) >rand(0, 1)) cur = np
}
}
int main() {
scanf("%d", &n)
for (int i = 0i <ni++) scanf("%lf%lf", &q[i].x, &q[i].y)
for (int i = 0i <100i++) simulate_anneal()
printf("%.0lf\n", ans)
return 0
}
登录后复制
AcWing 2424. 保龄球
问题描述
问题链接：AcWing 2424. 保龄球
分析
本题需要求解最大值，相当于求全排列中的最大值。
每次我们可以随机交换两个轮次，计算交换前后的差距，更新答案。
代码
C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#define x first
#define y second
using namespace std
typedef pair<int, int>PII
const int N = 55
int n, m // n: 规定的轮次 m: 实际的轮次
PII q[N]
int ans
int calc() {
int res = 0
for (int i = 0i <mi++) {
res += q[i].x + q[i].y
if (i <n) {
if (q[i].x == 10) res += q[i + 1].x + q[i + 1].y
else if (q[i].x + q[i].y == 10)
res += q[i + 1].x
}
}
ans = max(ans, res)
return res
}
void simulate_anneal() {
for (double t = 1e4t >1e-4t *= 0.99) {
auto a = rand() % m, b = rand() % m
int x = calc()
swap(q[a], q[b])
// 交换后进行的轮次 n + (q[n - 1].x == 10) 等于 实际轮次m
if (n + (q[n - 1].x == 10) == m) {
int y = calc()
int dt = y - x
// 如果dt>0, 则不用恢复原状
if (exp(dt / t) <(double)rand() / RAND_MAX)
swap(q[a], q[b])
} else swap(q[a], q[b])
}
}
int main() {
cin >>n
for (int i = 0i <ni++) cin >>q[i].x >>q[i].y
if (q[n - 1].x == 10) m = n + 1, cin >>q[n].x >>q[n].y
else m = n
// for (int i = 0i <100i++) simulate_anneal()
// 卡时写法: 卡0.1秒
while ((double)clock() / CLOCKS_PER_SEC <0.1) simulate_anneal()
cout <<ans <<endl
return 0
}
登录后复制
AcWing 2680. 均分数据
问题描述
问题链接：AcWing 2680. 均分数据
分析
这里可以随机将这些数据放置到某个组中，为了使得收敛的速度更快，可以采用贪心的策略将n个数据放置到m个组中。
每次找到和最小的组，将该数据放到该组中。
代码
C++
我有 simulated annealing with metropolies(Monte Carlo)做的一个项目的代码，你要看看么？void anneal(int nparam, int nstep, int nstep_per_block, double t0,
const double * param_in,
double cost_in, double * params_out, double * cost_out) {
int nblock
int step
int block
int nactive
int rank
int n_accepted = 0
int i, j, n
double cost_current, cost_trial
int* param_index
double * param_current
double * param_trial
double * Q
double * S
double * u
double * dp
double * A
FILE * fp_log_file
char fname[FILENAME_MAX]
double temp = t0
double tempmax = temp
double ebar, evar, emin, eta, specific_heat
double delta
double chi = 0.8 // Annealing schedule
double chi_s = 3.0 // Vanderbilt/Louie 'growth factor'
double rm
double root3 = sqrt(3.0)
double p = 0.02/sqrt(3.0) //max size of annealing step
param_current = new double[nparam]
param_trial = new double[nparam]
cost_current = cost_in
MPI_Comm_rank(MPI_COMM_WORLD, &rank)
sprintf(fname, "a_%4.4d.log", rank)
fp_log_file = fopen(fname, "a")
if (fp_log_file == (FILE *) NULL) errorMessage("fopen(log) failed\n")
// Work out the number of active parameters, and set up the
// index table of the active parameters.
// Note that the complete array of parameters (param_trial) must
// be used to evaluate the cost function.
nactive = 0
for (n = 0n <nparamn++) {
param_current[n] = param_in[n]
param_trial[n] = param_in[n]
if (P.is_active[n]) nactive++
}
param_index = new int[nactive]
i = 0
for (n = 0n <nparamn++) {
if (P.is_active[n]) param_index[i++] = n
}
// Initialise the step distribution matrix Q_ij
Q = new double[nactive*nactive]
S = new double[nactive*nactive]
u = new double[nactive]
dp = new double[nactive]
A = new double[nactive]
double * Qtmp
Qtmp = new double[nactive*nactive]
for (i = 0i <nactivei++) {
for (j = 0j <nactivej++) {
delta = (i == j)
Q[i*nactive + j] = p*delta*param_current[param_index[j]]
}
}
// carry out annealing points
nblock = nstep/nstep_per_block
rm = 1.0/(double) nstep_per_block
for (block = 0block <nblockblock++) {
// Set the schedule for this block, and initialise blockwise quantities.
// We also ensure the step distribution matrix is diagonal.
temp = chi*temp
for (i = 0i <nactivei++) {
A[i] = 0.0
for (j = 0j <nactivej++) {
S[i*nactive + j] = 0.0
delta = (i == j)
Q[i*nactive + j] *= delta
}
}
ebar = 0.0
evar = 0.0
emin = cost_current
for (i = 0i <nactivei++) {
printf("Step: %d %g\n", i, Q[i*nactive + i])
}
for (step = 0step <nstep_per_blockstep++) {
// Set the random vector u, and compute the step size dp
for (i = 0i <nactivei++) {
u[i] = root3*(r_uniform()*2.0 - 1.0)
}
for (i = 0i <nactivei++) {
dp[i] = 0.0
for (j = 0j <nactivej++) {
dp[i] += Q[i*nactive + j]*u[j]
}
}
for (i = 0i <nactivei++) {
n = param_index[i]
param_trial[n] = param_current[n] + dp[i]
if (param_trial[n] <P.min[n]) param_trial[n] = P.min[n]
if (param_trial[n] >P.max[n]) param_trial[n] = P.max[n]
}
// calculate new cost function score
p_model->setParameters(param_trial)
cost_trial = p_costWild->getCost()
cost_trial += p_costLHY->getCost()
cost_trial += p_costTOC1->getCost()
cost_trial += p_costAPRR->getCost()
// Metropolis
delta = cost_trial - cost_current
if (delta <0.0 || r_uniform() <exp(-delta/temp)) {
for (n = 0n <nparamn++) {
param_current[n] = param_trial[n]
}
cost_current = cost_trial
++n_accepted
}
// 'Energy' statistics
ebar += cost_current
evar += cost_current*cost_current
if (cost_current <emin) emin = cost_current
// Per time step log
fprintf(fp_log_file, "%6d %6d %10.4f %10.4f %10.4f %10.4f\n",
block, step, temp,
cost_current, cost_trial,
(float) n_accepted / (float) (block*nstep_per_block + step))
// Accumulate average, measured covariance
for (i = 0i <nactivei++) {
A[i] += param_current[param_index[i]]
for (j = 0j <nactivej++) {
S[i*nactive + j]
+= param_current[param_index[i]]*param_current[param_index[j]]
}
}
/* Next step*/
}
// Set the previous block average and measured covariance
for (i = 0i <nactivei++) {
A[i] = rm*A[i]
}
for (i = 0i <nactivei++) {
for (j = 0j <nactivej++) {
S[i*nactive + j] = rm*S[i*nactive + j] - A[i]*A[j]
if (i == j) printf("Average: %d %g %g\n", i, A[i], S[i*nactive+j])
// Set the convarience for the next iteration s = 6 chi_s S / M
S[i*nactive + j] = 6.0*chi_s*rm*S[i*nactive + j]
}
}
// Reset the step distribution matrix for the next block
i = do_cholesky(nactive, S, Q)
j = test_cholesky(nactive, S, Q)
printf("Cholesky %d %d\n", i, j)
// Block statistics
ebar = rm*ebar
evar = rm*evar
specific_heat = (evar - ebar*ebar) / temp*temp
eta = (ebar - emin)/ebar
fprintf(fp_log_file, "%d %d %f %f %f %f %f %f\n",
block, nstep_per_block, temp, ebar, evar, emin,
specific_heat, eta)
/* Next block */
}
*cost_out = cost_current
for (n = 0n <nparamn++) {
params_out[n] = param_current[n]
}
fclose(fp_log_file)
delete param_index
delete param_current
delete param_trial
delete Q
delete u
delete dp
delete S
delete A
return
}
R语言常用函数整理本篇是基础篇，即R语言自带的函数。
vector：向量
numeric：数值型向量
logical：逻辑型向量
character；字符型向量
list：列表
data.frame：数据框
c：连接为向量或列表
length：求长度
subset：求子集
seq，from:to，sequence：等差序列
rep：重复
NA：缺失值
NULL：空对象
sort，order，unique，rev：排序
unlist：展平列表
attr，attributes：对象属性
mode，class，typeof：对象存储模式与类型
names：对象的名字属性
字符型向量 nchar：字符数
substr：取子串 format，formatC：把对象用格式转换为字符串
paste()、paste0()不仅可以连接多个字符串，还可以将对象自动转换为字符串再相连，另外还能处理向量。
strsplit：连接或拆分
charmatch，pmatch：字符串匹配
grep，sub，gsub：模式匹配与替换
complex，Re，Im，Mod，Arg，Conj：复数函数
factor：因子 codes：因子的编码 levels：因子的各水平的名字 nlevels：因子的水平个数 cut：把数值型对象分区间转换为因子
table：交叉频数表 split：按因子分组 aggregate：计算各数据子集的概括统计量 tapply：对“不规则”数组应用函数
dev.new() 新建画板
plot()绘制点线图,条形图,散点图.
barplot( ) 绘制条形图
dotchart( ) 绘制点图
pie( )绘制饼图.
pair( )绘制散点图阵
boxplot( )绘制箱线图
hist( )绘制直方图
scatterplot3D( )绘制3D散点图.
par()可以添加很多参数来修改图形
title( ) 添加标题
axis( ) 调整刻度
rug( ) 添加轴密度
grid( ) 添加网格线
abline( ) 添加直线
lines( ) 添加曲线
text( ) 添加标签
legend(） 添加图例
+, -, *, /, ^, %%, %/%：四则运算 ceiling，floor，round，signif
1、round() #四舍五入
例：x <- c(3.1416, 15.377, 269.7)
round(x, 0) #保留整数位
round(x, 2) #保留两位小数
round(x, -1) #保留到十位
2、signif() #取有效数字(跟学过的有效数字不是一个意思)
例：略
3、trunc() #取整
floor() #向下取整
ceiling() #向上取整
例：xx <- c(3.60, 12.47, -3.60, -12.47)
trunc(xx)
floor(xx)
ceiling(xx)
max，min，pmax，pmin：最大最小值
range：最大值和最小值 sum，prod：向量元素和，积 cumsum，cumprod，cummax，cummin：累加、累乘 sort：排序 approx和approx fun：插值 diff：差分 sign：符号函数
abs，sqrt：绝对值，平方根
log, exp, log10, log2：对数与指数函数
sin，cos，tan，asin，acos，atan，atan2：三角函数
sinh，cosh，tanh，asinh，acosh，atanh：双曲函数
beta，lbeta，gamma，lgamma，digamma，trigamma，tetragamma，pentagamma，choose ，lchoose：与贝塔函数、伽玛函数、组合数有关的特殊函数
fft，mvfft，convolve：富利叶变换及卷积
polyroot：多项式求根
poly：正交多项式
spline，splinefun：样条差值
besselI，besselK，besselJ，besselY，gammaCody：Bessel函数
deriv：简单表达式的符号微分或算法微分
array：建立数组
matrix：生成矩阵
data.matrix：把数据框转换为数值型矩阵
lower.tri：矩阵的下三角部分
mat.or.vec：生成矩阵或向量
t：矩阵转置
cbind：把列合并为矩阵
rbind：把行合并为矩阵
diag：矩阵对角元素向量或生成对角矩阵
aperm：数组转置
nrow, ncol：计算数组的行数和列数
dim：对象的维向量
dimnames：对象的维名
rownames，colnames：行名或列名
%*%：矩阵乘法
crossprod：矩阵交叉乘积（内积）
outer：数组外积
kronecker：数组的Kronecker积
apply：对数组的某些维应用函数
tapply：对“不规则”数组应用函数
sweep：计算数组的概括统计量
aggregate：计算数据子集的概括统计量
scale：矩阵标准化
matplot：对矩阵各列绘图
cor：相关阵或协差阵
Contrast：对照矩阵
row：矩阵的行下标集
col：求列下标集
solve：解线性方程组或求逆
eigen：矩阵的特征值分解
svd：矩阵的奇异值分解
backsolve：解上三角或下三角方程组
chol：Choleski分解
qr：矩阵的QR分解
chol2inv：由Choleski分解求逆
><，>，<=，>=，==，!=：比较运算符 !，&，&&，|，||，xor()：
逻辑运算符 logical：
生成逻辑向量 all，
any：逻辑向量都为真或存在真
ifelse()：二者择一 match，
%in%：查找
unique：找出互不相同的元素
which：找到真值下标集合
duplicated：找到重复元素
optimize，uniroot，polyroot：一维优化与求根
if，else，
ifelse，
switch：
分支 for，while，repeat，break，next：
循环 apply，lapply，sapply，tapply，sweep：替代循环的函数。
function：函数定义
source：调用文件 ’
call：函数调用 .
C，.Fortran：调用C或者Fortran子程序的动态链接库。
Recall：递归调用
browser，debug，trace，traceback：程序调试
options：指定系统参数
missing：判断虚参是否有对应实参
nargs：参数个数 stop：终止函数执行
on.exit：指定退出时执行 eval，expression：表达式计算
system.time：表达式计算计时
invisible：使变量不显示
menu：选择菜单（字符列表菜单）
其它与函数有关的还有：
delay，
delete.response，
deparse，
do.call，
dput，
environment ，
formals，
format.info，
interactive，
is.finite，
is.function，
is.language，
is.recursive ，
match.arg，
match.call，
match.fun，
model.extract，
name，
parse 函数能将字符串转换为表达式expression
deparse 将表达式expression转换为字符串
eval 函数能对表达式求解
substitute，
sys.parent ，
warning，
machine
cat，print：显示对象
sink：输出转向到指定文件
dump，save，dput，write：输出对象
scan，read.table，readlines, load，dget：读入
ls，objects：显示对象列表
rm, remove：删除对象
q，quit：退出系统
.First，.Last：初始运行函数与退出运行函数。
options：系统选项
?，help，help.start，apropos：帮助功能
data：列出数据集
head()查看数据的头几行
tail()查看数据的最后几行
每一种分布有四个函数：
d―density（密度函数），p―分布函数，q―分位数函数，r―随机数函数。
比如，正态分布的这四个函数为dnorm，pnorm，qnorm，rnorm。下面我们列出各分布后缀，前面加前缀d、p、q或r就构成函数名：
norm：正态，
t：t分布，
f：F分布，
chisq：卡方（包括非中心）
unif：均匀，
exp：指数，
weibull：威布尔，
gamma：伽玛，
beta：贝塔
lnorm：对数正态，
logis：逻辑分布，
cauchy：柯西，
binom：二项分布，
geom：几何分布，
hyper：超几何，
nbinom：负二项，
pois：泊松
signrank：符号秩，
wilcox：秩和，
tukey：学生化极差
sum, mean, var, sd, min, max, range, median, IQR（四分位间距）等为统计量，
sort，order，rank与排序有关，
其它还有ave，fivenum，mad，quantile，stem等。
R中已实现的有chisq.test，prop.test，t.test。
cor，cov.wt，var：协方差阵及相关阵计算
biplot，biplot.princomp：多元数据biplot图
cancor：典则相关
princomp：主成分分析
hclust：谱系聚类
kmeans：k-均值聚类
cmdscale：经典多维标度
其它有dist，mahalanobis，cov.rob。
ts：时间序列对象
diff：计算差分
time：时间序列的采样时间
window：时间窗
lm，glm，aov：线性模型、广义线性模型、方差分析
quo()等价于quote()
enquo()等价于substitute(）
