poj 2069 Super Star 模拟退火

缘起

继续退火~ 咳咳咳，最近上火严重~ 太肝了 poj 2069 Super Star

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
题意：给定三维空间的n个点，找出一个半径最小的球把这些点全部包围住。输出球的半径
 
【输入】
多样例. 每个样例形如 
n
x1 y1 z1
x2 y2 z2
. . .
xn yn zn
4 <= n <= 30.
xi, yi, zi 在[0,100]内, 点与点之间最少间隔 0.01
输入最后一行是一个0, 你不需要处理它

【输出】
每个样例输出最小半径（5位小数）
 
【样例输入】
4
10.00000 10.00000 10.00000
20.00000 10.00000 10.00000
20.00000 20.00000 10.00000
10.00000 20.00000 10.00000
4
10.00000 10.00000 10.00000
10.00000 50.00000 50.00000
50.00000 10.00000 50.00000
50.00000 50.00000 10.00000
0
 
【样例输出】
7.07107
34.64102
 
【限制】
 1s

模拟退火裸题. 状态函数是最短距离. 直接撸代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define SQUARE(x) ((x)*(x))
using namespace std;
//#define LOCAL

const int maxn = 35;
int n,dir[26][3]={{-1,0,0},{1,0,0},{0,0,1},{0,0, -1}, {0,1,0}, {0,-1,0},
{1,1,0},{1,-1,0},{-1,1,0},{-1,-1,0},   {1,0,1},{1,0,-1},{-1,0,1},{-1,0,-1}, {0,1,1},{0,1,-1},{0,-1,1},{0,-1,-1},
{1,1,1},{-1,-1,-1},{1,1,-1},{-1,-1,1},{1,-1,1},{-1,1,-1},{-1,1,1},{1,-1,-1}};
struct Point
{
	double x,y,z;
}ps[maxn], cur, nxt;
double ans, step, eps = 1e-15;

double dis(Point &a, Point &b)
{
	return sqrt(SQUARE(a.x-b.x) + SQUARE(a.y-b.y)+SQUARE(a.z-b.z));
}

double e(Point &p)
{
	double ret = 0;
	for (int i =0; i<n; i++)
	{
		ret = max(ret, dis(ps[i], p));
	}
	return ret;
}

void init()
{
	step = 100;
	cur = ps[0];	
	ans = e(cur);
}

void transform(int i)
{
	nxt.x = cur.x+dir[i][0]*step;
	nxt.y = cur.y+dir[i][1]*step;
	nxt.z = cur.z+dir[i][2]*step;
}

void sa()
{
	init();
	while(step>eps)
	{
		bool ok  = true;
		while (ok)
		{
			ok = false;
			for (int i = 0; i<26; i++)
			{
				transform(i);
				double nxte = e(nxt);
				if (ans>nxte)
				{
					ans = nxte;
					cur = nxt;
					ok = true;
				}
			}
		}
		step/=2;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d", &n), n)
	{
		for (int i = 0; i<n; i++)
		{
			scanf("%lf%lf%lf", &ps[i].x, &ps[i].y, &ps[i].z);
		}
		sa();
		printf("%.6lf\n", ans);
	}
	return 0;
}

好吧, 我承认， 上面的退火板子过不了这道题.

Status Wrong Answer
Length 1467
Lang C++
Submitted 2019-09-28 10:15:51
Shared
RemoteRunId 20906206

而且和ac代码对拍过, 的确比最小半径大了一丢丢. 为什么会这样呢? 我个人认为是因为上述退火板子搜索的比较盲目导致的. 更加聪明的搜索应该是这样的:

从cur出发. 每次计算e(cur)即状态的能量值. 而本题的状态能量值是cur到n个点的最大距离. 所以这个最大距离就是把e(cur)搞大的罪魁祸首（假设是P和cur的距离达到了这个最大距离）. 所以我们应该尽可能的减少它. 怎么减少它呢? 当然是将cur朝着P移动啊~ 所以我们的搜索不应该像【1】那样上下左右几个方向进行搜索. 而应该每次朝着P去移动, 这样更具有启发式. 也就能更快的找到最优的解.

显然, 这里的优化想法只是针对本题（因为用到了本题的状态函数的特殊性），而并不是针对所有模拟退火问题的优化, 不然的话, 模拟退火就不会在OI圈被叫做随机化递减步长贪心了.

遂写下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define SQUARE(x) ((x)*(x))
using namespace std;
//#define LOCAL

const int maxn = 35;
int n, target; // target是每次计算e(cur)达到最大距离的那个点的索引
struct Point
{
	double x,y,z;
}ps[maxn], cur;
double ans, step, eps = 1e-8;

double dis(Point &a, Point &b)
{
	return sqrt(SQUARE(a.x-b.x) + SQUARE(a.y-b.y)+SQUARE(a.z-b.z));
}

double e(Point &p)
{
	double ans = 0;
	for (int i =0; i<n; i++)
	{
		double t = dis(ps[i], p);
		if (ans+eps<t)
		{
			ans = t;
			target = i;
		}
	}
	return ans;
}

void init()
{
	step = 100;
	cur = ps[0];	
	ans = 0x3f3f3f3f;
}

void transform(double t) // cur朝着ps[target]走step步长, 注意这种单位向量的写法
{
	cur.x += (ps[target].x-cur.x)/t*step;
	cur.y += (ps[target].y-cur.y)/t*step;
	cur.z += (ps[target].z-cur.z)/t*step;
}

void sa()
{
	init();
	while(step>eps)
	{
		double t = e(cur); // 计算当前节点的能量值和target
		transform(t); // cur朝着ps[target]运动
		ans = min(ans, t); // 优化ans
		step*=0.99; // 注意, 不能用/2,那样步长的太快,会T的
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d", &n), n)
	{
		for (int i = 0; i<n; i++)
		{
			scanf("%lf%lf%lf", &ps[i].x, &ps[i].y, &ps[i].z);
		}
		sa();
		printf("%.5lf\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 148kB
Length 1257
Lang C++
Submitted 2019-09-28 11:28:04
RemoteRunId 20906548

参考

【1】https://yfsyfs.github.io/2019/09/27/poj-2420-A-Star-not-a-Tree-%E8%B4%B9%E9%A9%AC%E7%82%B9%E7%9A%84%E6%B1%82%E8%A7%A3-%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB/

后记

本题模拟退火的板子和【1】中用的不一样. 这是因为本题可以根据每次求状态函数的结果而有方向性的优化ans的. 所以不会像【1】中那么随机. 所以以后做模拟退火的时候要想一下会不会求状态函数之后能有方向性的优化答案. 如果是的话, 考虑本题的做法.