시뮬레이티드 어닐링
개념
- 온도(단계 크기):
- 초기 온도 \(T\)
- 종료 온도
- 감쇠 계수 \(0 \sim 1\)
- 임의의 점 선택:
\(f(새로운점) - f(현재점) = \Delta E\)
- \(\Delta E < 0\)이면 새로운 점으로 이동
- \(\Delta E > 0\)이면 \(e^{-\frac{\Delta E}{T}}\) 확률로 이동
어닐링(온도 낮추기) 방법
시뮬레이티드 어닐링에는 세 가지 파라미터가 있습니다: 초기 온도 \(T_0\), 감쇠 계수 \(d\), 종료 온도 \(T_k\). 여기서 \(T_0\)는 비교적 큰 값이고, \(d\)는 1에 매우 가깝지만 1보다 작은 값이며, \(T_k\)는 0에 가까운 양수입니다.
먼저 온도 \(T = T_0\)로 설정하고, 위의 단계를 따라 이동을 시도한 다음 \(T = d \cdot T\)로 업데이트합니다. \(T < T_k\)가 되면 시뮬레이션 종료이며, 현재 최적 해가 최종 해가 됩니다.
해의 정확도를 높이기 위해, 보통 현재 해를 바로 답으로 사용하지 않고 어닐링 과정에서 발견한 모든 해 중 최적값을 유지합니다.
기법
시간 제한 관리: `while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME) simulateAnneal();`
여기서 `MAX_TIME`은 시간 제한보다 약간 작은 사용자 정의 값(단위: 초)입니다.
문제 유형
1. A Star not a Tree?
시뮬레이티드 어닐링 기본 문제로, 삼분 탐색 중첩으로도 해결 가능합니다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#define x first
#define y second
using namespace std;
typedef pair PDD;
const int N = 110;
int n;
PDD points[N];
double best_result = 1e8;
double random_range(double l, double r)
{
return (double)rand() / RAND_MAX * (r - l) + l;
}
double calculate_distance(PDD a, PDD b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
double evaluate_point(PDD p)
{
double total = 0;
for (int i = 0; i < n; i++)
total += calculate_distance(p, points[i]);
best_result = min(best_result, total);
return total;
}
void simulated_annealing()
{
PDD current(random_range(0, 10000), random_range(0, 10000));
for (double temp = 1e4; temp > 1e-4; temp *= 0.9)
{
PDD next(random_range(current.x - temp, current.x + temp),
random_range(current.y - temp, current.y + temp));
double difference = evaluate_point(next) - evaluate_point(current);
if (exp(-difference / temp) > random_range(0, 1))
current = next;
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%lf%lf", &points[i].x, &points[i].y);
for (int i = 0; i < 100; i++)
simulated_annealing();
printf("%.0lf\n", best_result);
return 0;
}
2. P4044 [AHOI2014/JSOI2014] 보링볼
각 프레임에는 세 가지 경우가 있습니다: 스트라이크, 스페어, 미스. 모든 프레임의 순서를 재배열하여 점수를 최대화해야 합니다.
스페어는 다음 프레임의 첫 번째 시도 점수가 두 배로 계산됩니다. 미스는 일반적인 경우로 특별한 처리가 필요 없습니다. 가장 중요한 것은 스트라이크입니다. 스트라이크는 다음 프레임 점수가 2배로 계산됩니다. 마지막 프레임이 스트라이크인 경우 재배열 시에도 마지막 프레임이 스트라이크여야 보너스 프레임이 있으며, 이는 원래 진행한 프레임 수와 일치해야 합니다.
이 문제에서 온도 \(T\)는 답변 업데이트 범위를 나타냅니다. \(T \rightarrow 0\)일 때, 즉 종료 온도 \(T_E\)에 도달하면 답을 얻게 됩니다.
시퀀스를 무작위로 생성하려면 두 개의 숫자를 교환하기만 하면 됩니다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 55;
int frame_count, total_frames;
PII frames[N];
int best_score;
int calculate_score()
{
int total = 0;
for (int i = 0; i < total_frames; i++)
{
total += frames[i].x + frames[i].y;
if (i < frame_count)
{
if (frames[i].x == 10)
total += frames[i + 1].x + frames[i + 1].y;
else if (frames[i].x + frames[i].y == 10)
total += frames[i + 1].x;
}
}
best_score = max(best_score, total);
return total;
}
void simulated_annealing()
{
for (double temp = 1e4; temp > 1e-4; temp *= 0.99)
{
int a = rand() % total_frames, b = rand() % total_frames;
int original_score = calculate_score();
swap(frames[a], frames[b]);
if (frame_count + (frames[frame_count - 1].x == 10) == total_frames)
{
int new_score = calculate_score();
int delta = new_score - original_score;
if (exp(delta / temp) < (double)rand() / RAND_MAX)
swap(frames[a], frames[b]);
}
else
swap(frames[a], frames[b]);
}
}
int main()
{
cin >> frame_count;
for (int i = 0; i < frame_count; i++)
cin >> frames[i].x >> frames[i].y;
if (frames[frame_count - 1].x == 10)
{
total_frames = frame_count + 1;
cin >> frames[frame_count].x >> frames[frame_count].y;
}
else
total_frames = frame_count;
for (int i = 0; i < 100; i++)
simulated_annealing();
cout << best_score << endl;
return 0;
}
3. P2503 [HAOI2006] 데이터 균등 분할
\(n\)개의 양의 정수 \(a_1, a_2, \ldots, a_n\)이 주어집니다. 이들을 \(m\)개의 그룹으로 나누어 분산을 최소화해야 합니다.
\[\sigma = \sqrt{\frac{1}{m} \sum_{i=1}^{m}(\overline{x} - x_i)^2}, \overline{x} = \frac{1}{m} \sum_{i=1}^{m} x_i\]
여기서 \(\sigma\)는 표준편차이고, \(\bar{x}\)는 각 그룹 합의 평균입니다.
원식:
\[\sigma=\sqrt{\frac{\sum_{i=1}^{n}(x_i-\overline{x})^2}{n}}, \overline{x}=\frac{\sum_{i=1}^{n}x_i}{n}\]
변형:
\[n\sigma^2=\sum_{i=1}^{n}(x_i-\overline{x})^2\]
전개:
\[n\sigma^2=\sum_{i=1}^{n}x_i^2-2\overline{x}\sum_{i=1}^{n}x_i + \sum_{i=1}^{n}\overline{x}^2\]
\(-2\overline{x}\sum_{i=1}^{n}x_i + \sum_{i=1}^{n}\overline{x}^2\)는 상수값입니다.
\(\sum_{i=1}^{n}x_i\)가 일정할 때, 각 \(x\)가 가능한 한 가까울 때 \(\sum_{i=1}^{n}x_i^2\)가 최대가 됩니다.
따라서 배열을 여러 번 무작위로 섞고, 각 경우 새로운 값을 추가할 때 최소 \(x\)에 추가하여 각 \(x\)가 가능한 한 동일하도록 탐욕적으로 값을 선택하면 됩니다. 최대값을 취하면 됩니다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 25, M = 10;
int n, m;
int values[N], group_sums[M];
double best_variance = 1e8;
double calculate_variance()
{
memset(group_sums, 0, sizeof group_sums);
for (int i = 0; i < n; i++)
{
int group_index = 0;
for (int j = 0; j < m; j++)
if (group_sums[j] < group_sums[group_index])
group_index = j;
group_sums[group_index] += values[i];
}
double average = 0;
for (int i = 0; i < m; i++)
average += (double)group_sums[i] / m;
double variance = 0;
for (int i = 0; i < m; i++)
variance += (group_sums[i] - average) * (group_sums[i] - average);
variance = sqrt(variance / m);
best_variance = min(best_variance, variance);
return variance;
}
void simulated_annealing()
{
random_shuffle(values, values + n);
for (double temp = 1e6; temp > 1e-6; temp *= 0.95)
{
int a = rand() % n, b = rand() % n;
double original_variance = calculate_variance();
swap(values[a], values[b]);
double new_variance = calculate_variance();
double delta = new_variance - original_variance;
if (exp(-delta / temp) < (double)rand() / RAND_MAX)
swap(values[a], values[b]);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> values[i];
for (int i = 0; i < 100; i++)
simulated_annealing();
printf("%.2lf\n", best_variance);
return 0;
}
힐 클라이밍
힐 클라이밍 알고리즘은 현재 찾은 최적 해 \(x\) 주변에서 새로운 해 \(x'\)를 탐색합니다. 이 새로운 해 \(x'\)가 더 좋으면 \(x'\)로 이동하고, 그렇지 않으면 그대로 둡니다.
단봉 함수 문제만 해결할 수 있으며, 다봉 함수 문제는 지역 최적 해에 빠질 수 있습니다.
P4035 [JSOI2008] 구형 공간 생성기
문제 요약: \(n\)개의 점 좌표가 주어지면, 중심점을 찾아야 합니다.
해결책: 무작위화. 무작위로 점을 하나 선택하여 중심점으로 가정하고, 각 점과 비교하여 평균 거리 \(r\)를 계산합니다. 이 점까지의 거리가 \(r\)보다 크면 이 점에서 멀리 있다는 의미이므로 중심점에 이 점 방향의 힘을 가합니다. \(r\)보다 작으면 가깝다는 의미이므로 중심점에 이 점과 반대 방향의 힘을 가합니다. 모든 점을 비교한 후, 가정한 중심점을 합력 방향으로 이동시키며, 이동 거리는 현재 온도와 관련이 있습니다. 시간이 지날수록 온도는 낮아집니다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 15;
int n;
double distances[N][N];
double center[N], point_distances[N], force[N];
void calculate_forces()
{
double avg_distance = 0;
for (int i = 0; i < n + 1; i++)
{
point_distances[i] = force[i] = 0;
for (int j = 0; j < n; j++)
point_distances[i] += (distances[i][j] - center[j]) * (distances[i][j] - center[j]);
point_distances[i] = sqrt(point_distances[i]);
avg_distance += point_distances[i] / (n + 1);
}
for (int i = 0; i < n + 1; i++)
for (int j = 0; j < n; j++)
force[j] += (point_distances[i] - avg_distance) * (distances[i][j] - center[j]) / avg_distance;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n + 1; i++)
for (int j = 0; j < n; j++)
{
scanf("%lf", &distances[i][j]);
center[j] += distances[i][j] / (n + 1);
}
for (double temp = 1e4; temp > 1e-6; temp *= 0.99995)
{
calculate_forces();
for (int i = 0; i < n; i++)
center[i] += force[i] * temp;
}
for (int i = 0; i < n; i++)
printf("%.3lf ", abs(center[i]));
return 0;
}
최상의 답변을 얻기 위해 여러 번 힐 클라이밍을 할 수 있습니다. 방법으로는 초기 상태 수정, 감쇠 파라미터 수정, 초기 온도 수정 등이 있습니다. 그런 다음 전역 최적 해를 기록하여 답변을 업데이트합니다. 각 힐 클라이밍이 끝난 후 전역 최적 해를 업데이트합니다.