Kĩ thuật leo đồi
Kĩ thuật leo đồi
Mục tiêu của bài này là cung cấp kiến thức về leo đồi một cách hiệu quả nhất, sao cho người mới học cảm thấy dễ hiểu, và người đã biết leo đồi thấy được các kĩ thuật nâng cao (và phức tạp) trong leo đồi.
1. Những kiến thức cơ bản nhất về leo đồi
Những thứ được ghi trong mục này là quan trọng với người bắt đầu. Nếu đây là lần đầu tiên bạn tìm hiểu về leo đồi, bạn nên đọc kĩ mục này.
Leo đồi dùng để tìm min/max của một hàm số.
Hàm số thích hợp để leo đồi là hàm có dạng f(x) với x là số thực. Hàm càng liên tục và càng trơn (ít cực trị và ít dốc) thì càng dễ leo đồi.
Ý tưởng chung của leo đồi: Giả sử hàm số của ta là f(x), đầu tiên ta chọn một điểm rơi x, sau đó di chuyển x tới vùng lân cận mà có f(x) cao hơn (hoặc thấp hơn, tất nhiên, tuỳ bài), và cuối cùng, dừng lại ở một cực trị. Quá trình di chuyển được xử lý nhanh với số bước di chuyển là O(log(R/eps))). Quá trình này được trình bày chi tiết ở mục “Mở đầu về leo đồi 1D” bên dưới.
Sau đây là một số khái niệm nâng cao (có thể bạn không cần biết). Leo đồi trên hàm có dạng f(x) gọi là leo đồi 1D. Ngoài ra, ta có thể leo đồi trên hàm f(x,y) với x, y là số thực, leo đồi trên hàm này gọi là leo đồi 2D. Với các hàm số mà f(x) có x là số nguyên, tôi không có kinh nghiệm về leo đồi trên những hàm này và cũng không biết có làm được hay không. Với các hàm số f(x) mà f(x) là số nguyên (x là số thực), ta phải dùng phương pháp xử lý “đồng bằng” được viết ở bên dưới.
2. Mở đầu về leo đồi 1D
Về cơ bản, leo đồi 1D gồm hai quá trình, thả dù và di chuyển:
Bước 1: Thả dù
Chọn một giá trị x ngẫu nhiên.
Bước 2: Di chuyển
Đầu tiên, giữ nguyên x hoặc di chuyển x đến x+R hoặc x-R (chọn phương án tốt nhất trong ba phương án, cụ thể hơn, bằng cách so sánh f(x), f(x+R), f(x-R)).
Sau đó, giữ nguyên x hoặc di chuyển x đến x+R/2 hoặc x-R/2.
Tiếp theo, giữ nguyên x hoặc di chuyển x đến x+R/4 hoặc x-R/4.
Làm tiếp quá trình trên với độ sâu cần thiết (O(log (R/epsilon)), khoảng 25-30 bước, tuỳ bài).
Lặp lại các bước trên một số lần, rồi chọn lấy kết quả tốt nhất. Việc chọn số lần thả dù và số bước di chuyển sao cho tối ưu sẽ được trình bày ở mục bên dưới.
Bài tập ví dụ
Trên mặt phẳng, có N đoạn thẳng (1 ≤ N ≤ 2000). Hãy tìm một đường tròn với tâm (x, y) có bán kính lớn nhất thoả mãn:
0 ≤ x ≤ L
y=0
Miền trong của hình tròn không chứa bất kì phần nào của N đoạn thẳng. Nói cách khác, không có đoạn thẳng nào được cắt hình tròn (mặc dù chúng có thể tiếp xúc với hình tròn đó.
Toạ độ của đầu mút các đoạn thẳng là số nguyên và có giá trị tuyệt đối không quá 20000. L là số nguyên và nằm trong khoảng 0..10000.
Nhiệm vụ của bạn là đưa ra bán kính đường tròn tối đa, viết chính xác 3 chữ số phần thập phân.
Nhận xét
Gọi f(x) là bán kính lớn nhất đạt được của đường tròn có tâm ở (x, 0). Ta dùng kĩ thuật leo đồi để tìm max f(x). Vì đây là hàm liên tục, ít dốc, nên leo đồi rất dễ. Các bước leo đồi đã được ghi rõ ràng ở bên trên nên tôi không nhắc lại.
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<double, double> point;
typedef pair<point, double> line;
#define X first
#define Y second
const int N = 2003;
int n;
double L;
point a[N], b[N], u[N];
line d[N];
point operator-(point a, point b) {
return point(a.X - b.X, a.Y - b.Y);
}
point operator!(point a) {
return point(-a.Y, a.X);
}
double operator^(point a, point b) {
return a.X * b.X + a.Y * b.Y;
}
double operator*(point a, point b) {
return a.X * b.Y - a.Y * b.X;
}
double abs(point M) {
return sqrt(M.X * M.X + M.Y * M.Y);
}
double abs(double a, double b) {
return a > b ? a - b : b - a;
}
double dist(line d, point M) {
return abs((d.X.X * M.X + d.X.Y * M.Y - d.Y) / abs(d.X), 0.0);
}
bool in_order(double a, double b, double c) {
return a <= b + 1e-9 && b <= c + 1e-9 || c <= b + 1e-9 && b <= a + 1e-9;
}
double f(double x) {
x = max(min(x, L), 0.0);
point M(x, 0);
double Min = 23e9;
for (int i = 1; i <= n; i++) {
if (in_order(u[i] ^ a[i], u[i] ^ M, u[i] ^ b[i]))
Min = min(Min, dist(d[i], M));
else
Min = min(Min, min(abs(M - a[i]), abs(M - b[i])));
}
return Min;
}
const int Depth = 20;
double climb(double x, double R) {
double F = f(x);
for (int i = 1; i <= Depth; i++) {
R /= 2;
double F1 = f(x - R);
double F2 = f(x + R);
if (F < F1 || F < F2) {
if (F1 > F2) {
x -= R;
F = F1;
} else {
x += R;
F = F2;
}
}
}
return F;
}
int main() {
scanf("%d%lf", &n, &L);
for (int i = 1; i <= n; i++) {
int x, y, p, q;
scanf("%d%d%d%d", &x, &y, &p, &q);
a[i] = point(x, y);
b[i] = point(p, q);
u[i] = b[i] - a[i];
d[i] = line(!u[i], (!u[i]) ^ a[i]);
}
double Max = 0.0;
const int B = 100;
for (int i = 0; i < B; i++)
Max = max(Max, climb(L / B * i, L / B));
printf("%.3lf\n", Max);
}
3. Vấn đề “đồng bằng” trong leo đồi 1D
Đồng bằng là các khoảng mà giá trị của hàm mục tiêu ở đó là hằng số. Đồng bằng hay gặp khi giá trị của hàm mục tiêu là số nguyên.
Tại đồng bằng, hàm mục tiêu không chỉ cho ta hướng để tối ưu. Một khi rơi vào đồng bằng, ta không thể di chuyển. Vậy nên ta phải loại bỏ đồng bằng. Để làm được điều này, có một cách đó là điều chỉnh hàm mục tiêu.
Một trường hợp về tác dụng của việc khử đồng bằng. Ở hình bên phải, ta có thể leo đồi theo đường màu cam, điều mà không thể làm tương tự ở hình bên trái.
Thay vì dùng hàm số trả về kết quả kiểu double hay int, ta sẽ dùng pair. f(x).first lưu giá trị thật sự của hàm số. f(x).second là một giá trị khác đánh giá độ tốt của điểm x. Ở đây, trường second là quan trọng, nó giúp ta phân biệt cao thấp giữa những giá trị mà có first giống nhau.
Một trường hợp bắt buộc phải khử đồng bằng. Nếu không, xác suất tìm được nghiệm đúng gần như bằng 0 (thả dù trúng điểm là nghiệm).
Đặc biệt, với trường hợp hàm số trả về kiểu số nguyên, có một cách xử lý hay như sau. Thay vì trả về giá trị kiểu nguyên, ta trả về giá trị kiểu thực. Phần nguyên chính là giá trị ban đầu của f(x), còn phần thập phân (lớn hơn 0 và bé hơn 1) là phần đánh giá của điểm rơi. Trong cách này, có hai chú ý. Thứ nhất, phần đánh giá phải bé hơn hẳn 1 (để giữ nguyên phần nguyên). Thứ hai, phần đánh giá phải lớn hơn hẳn 0 (để an toàn khi trích lấy phần nguyên bằng ép kiểu).
Bài tập ví dụ
Cho N điểm trên mặt phẳng (1 <= N <= 1000). Bob muốn vẽ 1 đường thẳng L. Mỗi điểm có khoảng cách tới L không quá d sẽ giúp Bob ghi được 1 điểm. Xác định số điểm tối đa Bob có thể ghi được.
Toạ độ các điểm là số nguyên và có trị tuyệt đối nhỏ hơn hoặc bằng 1000. d nằm trong khoảng từ 0 đến 1000.
Biết d và toạ độ các điểm, nhiệm vụ của bạn là in ra số điểm tối đa Bob có thể ghi được.
Nhận xét
Nếu biết được phương của đường thẳng, ta sẽ tìm được số điểm tối đa ghi được trong O(N log N). Thật vậy, giả sử phương của đường thẳng là u, đầu tiên ta vẽ một đường thẳng bất kì vuông góc với u, sau đó chiếu N điểm lên đường thẳng này. Tiếp theo, trên đường thẳng này, ta tìm một đoạn có độ dài 2*d chứa nhiều điểm nhất. Số điểm trên đoạn này chính là kết quả của bài toán. Vấn đề còn lại của chúng ta là tìm ra phương của đường thẳng.
Gọi h(t) là số điểm lớn nhất đạt được khi phương của đường thẳng có góc là t. Ta sẽ leo đồi để tìm max h(t).
Vì giá trị của hàm số h(t) là kiểu nguyên, trên hàm này sẽ xuất hiện đồng bằng. Ta chỉnh sửa bằng cách, cho hàm này trả về kiểu thực, bây giờ ta phải định nghĩa phần thập phân. Giả sử sau khi chiếu các điểm xuống đường thẳng, đoạn độ dài 2*d tối ưu kéo dài từ L đến R, ta sẽ xem khoảng cách từ điểm thứ L-1 đến R là bao nhiêu. Gọi khoảng cách này là p, thì p càng bé càng tốt. Bây giờ ta muốn đưa p vào hàm số như một giá trị đánh giá, và đồng thời đảm bảo giá trị đánh giá này lớn hơn 0 và nhỏ hơn 1. Có nhiều cách làm, tuy nhiên cách tiêu biểu mà tôi dùng là: định nghĩa phần thập phân của hàm h(t) là (2*d)/p.
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1003, Depth = 25;
int n, D, x[N], y[N];
double z[N];
double h(double t) {
for (int i = 1; i <= n; i++)
z[i] = x[i] * sin(t) + y[i] * cos(t);
sort(z + 1, z + n + 1);
double Max = 0.0;
int j = 1;
for (int i = 1; i <= n; i++) {
while (z[i] - z[j] > 2 * D + 1e-6) j++;
double Frac = (j == 1 ? 1e-6 : (2 * D) / (z[i] - z[j - 1]));
Max = max(Max, i - j + 1 + Frac);
}
return Max;
}
double climb(double t, double R) {
double H = h(t);
for (int i = 1; i <= Depth; i++) {
R /= 2;
double H1 = h(t - R);
double H2 = h(t + R);
if (H < H1 || H < H2) {
if (H1 > H2) {
t -= R;
H = H1;
} else {
t += R;
H = H2;
}
}
}
return H;
}
int main() {
scanf("%d%d", &n, &D);
for (int i = 1; i <= n; i++)
scanf("%d%d", &x[i], &y[i]);
double Max = 0.0;
const int B = 360;
for (int i = 0; i < B; i++)
Max = max(Max, climb((2 * M_PI) * i / B, (2 * M_PI) / B));
cerr << Max << endl;
cout << int(Max) << endl;
}
4. Chặn nhánh trong leo đồi 1D
Không phải bài nào cũng có thể chặn nhánh. Tuy nhiên, nếu chặn nhánh thành công, chương trình thường chạy rất nhanh (theo kinh nghiệm, nhanh hơn khoảng 5-10 lần). Vì vậy, nếu bạn yêu thích việc leo đồi, bạn nên biết phương pháp này.
Như ta đã biết, thời gian chạy của leo đồi bị ảnh hưởng bới số lần thả dù và độ sâu. Trong hai yếu tố này, độ sâu là thứ ta có thể chặn nhánh.
Giả sử trạng thái leo đồi là (x, R) nghĩa là đang đứng ở vị trí x, bước nhảy hiện tại là R/2. Vì các bước nhảy là R/2, R/4, R/8, ... nên ta chỉ có thể nhảy đến vị trí trong khoảng x-R đến x+R. Nhận xét thấy, khi R càng bé, thì khoảng của hàm mục tiêu cũng bị thu hẹp lại. Ta định nghĩa g(x, R) là cận trên của hàm f trong đoạn [x-R, x+R], nói cách khác f(x)<=g(x, R). Khi đó nếu g(x, R) không lớn hơn giá trị tốt nhất hiện tại (giá trị lớn nhất của f mà ta đã tìm được), ta sẽ chặn nhánh.
Bài tập ví dụ
Cho biết tâm và bán kính của n hình tròn (1<=N<=100000). Tìm điểm M cách gốc toạ độ một khoảng đúng bằng L sao cho M thuộc nhiều hình tròn nhất. In ra số lượng hình tròn chứa M.
Nhận xét
Gọi f(x) là số hình tròn chứa M khi M tạo với trục hoành một góc x. Ta sẽ dùng leo đồi để tìm max f. Gọi g(x, R) là cận trên của f(x) với x thuộc đoạn [x-R, x+R]. Ta tính g(x, R) như sau:
- Khởi tạo biến kết quả bằng 0.
- Đầu tiên ta tính điểm M, M = (L*sin(t), L*cos(t)).
- Với mỗi hình tròn (I, r), nếu IM <= r + R*L, tăng biến kết quả lên 1.
Giải thích: Khoảng cách từ I đến M hiện tại là IM, nếu x thay đổi một góc là R, làm cho điểm M di chuyển đến điểm M', thì MM' nhỏ hơn hoặc bằng cung MM'. Ta biết rằng độ dài cung MM' là R*L. Thế nên MM' <= R*L. Giả sử hình tròn (I, r) chứa M', tức là IM' <= r, mà MM' = R*L, nên IM' + MM' <= r + R*L, suy ra IM <= r + R*L.
Nói cách khác, khoảng cách hiện tại của I và M là IM. Khi t di chuyển một lượng tối đa là R thì M di chuyển một lượng tối đa là L*R. Tức là trong trường hợp tốt nhất, khoảng cách I đến M giảm xuống còn IM - R*L. Vì thế điều ta cần kiểm tra là IM - R*L <= r.
5. Leo đồi 2D
(chờ chút)