我使用LBSAList-Based Simulated Annealing算法写了一道题:# JSOI2004 平衡点 吊打XXX## 题目描述如图有 $n$ 个重物每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞然后系在一起。图中 $x$ 处就是公共的绳结。假设绳子是完全弹性的即不会造成能量损失桌子足够高重物不会垂到地上且忽略所有的摩擦求绳结 $x$ 最终平衡于何处。注意:桌面上
根据给出的代码,可能导致只有11分的原因有以下几点:
- 输入格式不正确:题目中要求输入的第一行是一个正整数n,但是代码中并没有对应的输入代码,可能导致输入错误。
- 没有对ans进行初始化:在代码中没有对ans进行初始化,可能导致计算能量时出现错误。
- tempList的使用不正确:在createInitTemp函数中,对tempList进行了初始化,但是在runLBSA函数中并没有正确使用tempList,可能导致出现错误。
- 随机数生成不正确:在生成随机数时,使用了rand()函数,但是rand()函数生成的是一个较小的整数,可能导致生成的随机数范围不正确,需要使用更大的随机数生成范围。
针对以上问题,可以尝试做以下修改:
- 在代码中添加对n的输入代码,确保输入格式正确。
- 在main函数中对ans进行初始化,例如
ans.x = 0; ans.y = 0;。 - 在runLBSA函数中,可以使用
temp = tempList.top(); tempList.pop();来获取和更新temp的值。 - 修改随机数生成部分的代码,可以使用
((double)rand() / RAND_MAX) * 20000 - 10000;来生成一个在[-10000, 10000]范围内的随机数。
修改后的代码如下:
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <queue>
#define INIT_TEMP 1e5
#define INIT_ACC_PROB 0.1
#define TEMP_LIST_LENGTH 30
#define MAXIMUM_ITERATION_TIMES 100
#define MARKOV_CHAIN_LENGTH 100
int numOfWeights;
struct node {
int x, y, w;
} weight[1010];
struct solve {
double x, y, energy;
} ans;
std::priority_queue<double> tempList;
double calcEnergy(solve pos) {
double energy = 0.0;
for(int i = 1; i <= numOfWeights; i++) {
energy += sqrt(pow(pos.x - weight[i].x, 2) + pow(pos.y - weight[i].y, 2)) * weight[i].w;
}
return energy;
}
void createInitTemp() {
for(int i = 1; i <= TEMP_LIST_LENGTH; i++) {
solve newAns;
newAns.x = ans.x + ((double)rand() / RAND_MAX) * 20000 - 10000;
newAns.y = ans.y + ((double)rand() / RAND_MAX) * 20000 - 10000;
newAns.energy = calcEnergy(newAns);
if(newAns.energy < ans.energy) {
newAns = ans;
}
double temp = (- abs(newAns.energy - ans.energy)) / log(INIT_ACC_PROB);
tempList.push(temp);
}
}
void runLBSA() {
for(int i = 1; i <= MAXIMUM_ITERATION_TIMES; i++) {
double temp = tempList.top();
tempList.pop();
int updateTimes = 0;
for(int j = 1; j <= MARKOV_CHAIN_LENGTH; j++) {
solve newAns;
newAns.x = ans.x + ((double)rand() / RAND_MAX) * 20000 - 10000;
newAns.y = ans.y + ((double)rand() / RAND_MAX) * 20000 - 10000;
newAns.energy = calcEnergy(newAns);
if(newAns.energy < ans.energy) {
ans = newAns;
}
else {
double p = exp(- (newAns.energy - ans.energy) / temp);
double r = (double)rand() / (RAND_MAX + 1);
if(r < p) {
temp = (temp - (newAns.energy - ans.energy)) / log(r);
updateTimes++;
}
}
}
if(updateTimes) {
tempList.push(temp / updateTimes);
}
}
}
int main() {
srand(time(0));
scanf("%d", &numOfWeights);
for(int i = 1; i <= numOfWeights; i++) {
scanf("%d %d %d", &weight[i].x, &weight[i].y, &weight[i].w);
ans.x += weight[i].x;
ans.y += weight[i].y;
}
ans.x /= numOfWeights;
ans.y /= numOfWeights;
ans.energy = calcEnergy(ans);
createInitTemp();
runLBSA();
printf("%.3lf %.3lf", ans.x, ans.y);
return 0;
}
请尝试使用修改后的代码重新运行,并检查是否能够得到正确的结果
原文地址: https://www.cveoy.top/t/topic/ixQq 著作权归作者所有。请勿转载和采集!