Mô phỏng tôi luyện (Simulated Annealing)
Heuristic mô phỏng tôi luyện cho bài tối ưu khó: vì sao leo đồi bị kẹt, xác suất chấp nhận e^(-Δ/T), lịch nhiệt theo thời gian, thiết kế bước đi và tính chênh lệch gia tăng, kèm số liệu chạy thật so với đáp án tối ưu.
Mô phỏng tôi luyện (simulated annealing, SA) là một heuristic tìm kiếm ngẫu nhiên cho các bài tối ưu hóa khó: người du lịch (TSP), xếp lịch, chia nhóm, đặt điểm trên mặt phẳng, bài chấm điểm theo độ tốt của đáp án. Khi không có thuật toán đa thức (hoặc không nghĩ ra), vét cạn hay là bất khả thi, SA cho một đáp án rất gần tối ưu trong một khoảng thời gian cố định do ta chọn. Đổi lại, nó không bảo đảm gì cả: không chắc tối ưu, không chắc lần chạy nào cũng ra cùng kết quả.
Trang Thuật toán ngẫu nhiên đã có một đoạn giới thiệu ngắn về SA. Trang này đi sâu hơn: vì sao leo đồi bị kẹt, chọn nhiệt độ ra sao, thiết kế bước đi, tính chênh lệch nhanh, và so kết quả thực tế với đáp án tối ưu.
Ý tưởng / Trực giác
Tìm kiếm cục bộ và leo đồi
Mọi heuristic loại này đều dựa trên ba thứ:
- Trạng thái : một đáp án hợp lệ (một hoán vị các thành phố, một cách chia nhóm, một tọa độ).
- Hàm chi phí cần làm nhỏ nhất (độ dài chu trình, số ràng buộc bị vi phạm...).
- Hàng xóm (neighbour): các trạng thái nhận được từ bằng một thay đổi nhỏ (đảo một đoạn, đổi chỗ hai phần tử, dịch một điểm một chút).
Leo đồi (hill climbing, hay tìm kiếm cục bộ) đơn giản nhất: lặp lại "chọn một hàng xóm , nếu thì chuyển sang ". Khi không còn hàng xóm nào tốt hơn, ta dừng ở một cực tiểu địa phương: tốt nhất trong vùng lân cận, nhưng chưa chắc tốt nhất toàn cục.
Hình dung là một dãy núi và ta đi tìm đáy thung lũng sâu nhất trong sương mù, chỉ nhìn được một bước quanh chân. Leo đồi luôn bước xuống, nên rơi vào thung lũng nào thì kẹt luôn ở thung lũng đó. Muốn sang thung lũng sâu hơn, bắt buộc phải leo lên qua một đỉnh đèo trước.
Chấp nhận bước tệ hơn với xác suất
SA sửa đúng chỗ đó. Đặt :
là nhiệt độ. Công thức này (tiêu chuẩn Metropolis) có hai tính chất trực quan:
- Bước tệ hơn càng ít ( nhỏ) thì càng dễ được nhận.
- Nhiệt độ càng cao thì càng dễ nhận bước tệ. Khi , SA trở thành leo đồi.
Ví dụ thực tế với hai mức tệ và :
Ta giảm dần theo thời gian: lúc đầu (nóng) trạng thái đi lung tung khắp nơi, dễ vượt đèo sang thung lũng khác; về sau (nguội) chỉ còn bước xuống, tinh chỉnh trong thung lũng tốt nhất đã tìm được. Tên gọi lấy từ luyện kim: kim loại nung nóng rồi làm nguội chậm thì các nguyên tử kịp xếp vào cấu trúc năng lượng thấp; làm nguội đột ngột (tôi nhanh) thì kẹt ở cấu trúc lỗi.
Có một định lý lý thuyết: nếu giảm nhiệt cực chậm (kiểu ) thì SA hội tụ về tối ưu toàn cục với xác suất . Nhưng "cực chậm" nghĩa là lâu hơn cả vét cạn, nên trong thực tế (và trong phòng thi) SA chỉ là heuristic: ta chọn lịch nhiệt vừa với giới hạn thời gian và chấp nhận kết quả gần tối ưu.
Luôn lưu đáp án tốt nhất
Vì SA cố ý đi lên, trạng thái hiện tại cuối cùng có thể tệ hơn trạng thái tốt nhất từng gặp. Luôn giữ riêng best và in best, không in trạng thái hiện tại.
Thiết kế một lời giải SA
Hàng xóm và tính chênh lệch gia tăng
Hai yêu cầu cho bước đi:
- Đủ nhỏ để gần (nếu bước đi là "xáo trộn lại toàn bộ" thì SA chỉ còn là thử ngẫu nhiên).
- Tính nhanh, lý tưởng là , không tính lại từ đầu. Số bước trong giới hạn thời gian quyết định chất lượng, nên đây thường là chỗ quan trọng nhất.
Với TSP, bước 2-opt: chọn và đảo ngược đoạn của chu trình. Chỉ hai cạnh thay đổi: và bị bỏ, và được thêm (các cạnh bên trong đoạn chỉ đổi chiều, độ dài không đổi). Vì vậy
Tính tốn ; chỉ khi nhận bước đi mới phải đảo đoạn (). Cố định (thành phố luôn đứng đầu) để khỏi phải xử lý vòng quanh.
Một vài bước đi hay dùng khác: đổi chỗ hai phần tử, chuyển một phần tử sang vị trí khác (or-opt), đổi nhóm của một phần tử, dịch tọa độ một điểm theo vectơ ngẫu nhiên. Có thể trộn nhiều loại bước đi, chọn ngẫu nhiên mỗi lần.
Lịch nhiệt theo thời gian
Lịch hình học (geometric) phổ biến nhất: giảm từ xuống theo cấp số nhân. Trong thi đấu, thay vì cố định số bước, ta gắn nhiệt độ với thời gian đã chạy :
Ưu điểm: chương trình luôn dùng đúng ngân sách thời gian, dù máy chấm nhanh hay chậm, dù lớn hay nhỏ. Đọc đồng hồ khá đắt nên chỉ đọc mỗi bước một lần.
Chọn , theo độ lớn điển hình của chứ không đoán mò:
- : lúc đầu một bước tệ điển hình nên được nhận với xác suất khoảng đến . Nếu điển hình là thì đến .
- : cuối cùng gần như không nhận bước tệ nhỏ nhất đáng kể, ví dụ hoặc nhỏ hơn.
Cách nhanh để biết : chạy thử vài nghìn bước ngẫu nhiên và in trung bình , hoặc in tỉ lệ nhận bước tệ theo từng giai đoạn (như bảng ở ví dụ dưới) rồi chỉnh.
Khởi động lại (restart)
Một lần SA vẫn có thể kết thúc ở cực tiểu địa phương. Hai cách tận dụng thêm:
- Nhiều lần chạy ngắn: chia thời gian thành lần SA độc lập, lấy kết quả tốt nhất. Hợp khi không gian trạng thái có nhiều vùng tốt rời nhau.
- Khởi động lại từ
best: khi lâu không cải thiện, quay về trạng thái tốt nhất và tăng nhẹ nhiệt độ (reheat).
Ngay cả leo đồi thuần, nếu khởi động lại ngẫu nhiên nhiều lần, cũng đã mạnh hơn hẳn leo đồi một lần (xem số liệu bên dưới).
Ví dụ chạy tay: TSP với 10 thành phố
Mười thành phố (đánh số ), cần tìm chu trình ngắn nhất đi qua tất cả:
| Thành phố | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 14 | 14 | 16 | 6 | 16 | 20 | 5 | 14 | 4 | 17 | |
| 17 | 14 | 18 | 5 | 15 | 19 | 3 | 9 | 2 | 20 |
Đáp án tối ưu (tính bằng quy hoạch động bitmask Held-Karp ) là , chu trình :
graph 10 10 1 2 2 4 4 9 9 7 7 8 8 5 5 6 6 10 10 3 3 1 pos 1 280 60 pos 2 280 120 pos 3 320 40 pos 4 120 300 pos 5 320 100 pos 6 400 20 pos 7 100 340 pos 8 280 220 pos 9 80 360 pos 10 340 0 path green 1 2 4 9 7 8 5 6 10 3 1
Leo đồi bị kẹt ở đâu
Chạy leo đồi 2-opt "thử mọi cặp , nhận bước nào làm ngắn đi, lặp đến khi không cải thiện được" từ hoán vị ban đầu ngẫu nhiên. Nó chỉ dừng ở đúng bốn chu trình khác nhau, và chỉ số lần ra tối ưu:
| Cực tiểu địa phương (2-opt) | Độ dài | Số lần dừng ở đây (trên 2000) |
|---|---|---|
| (tối ưu) | ||
Chu trình tệ nhất trong bảng () trông như sau:
graph 10 10 1 4 4 9 9 7 7 8 8 2 2 5 5 3 3 6 6 10 10 1 pos 1 280 60 pos 2 280 120 pos 3 320 40 pos 4 120 300 pos 5 320 100 pos 6 400 20 pos 7 100 340 pos 8 280 220 pos 9 80 360 pos 10 340 0 path red 1 4 9 7 8 2 5 3 6 10 1
So với tối ưu, thành phố và nằm sai chỗ: muốn sửa phải "nhấc" hai thành phố sang vị trí khác cùng lúc, nhưng mọi bước 2-opt đơn lẻ từ đây đều làm chu trình dài ra. Leo đồi không bao giờ đi bước dài ra, nên kẹt vĩnh viễn.
SA vượt qua như thế nào
Bảng dưới ghi lại một lần chạy SA trên cùng bộ dữ liệu (bản có in log, bước, , , lịch hình học). Cột cuối là tỉ lệ bước tệ hơn được nhận trong giai đoạn đó:
| Tiến độ | Hiện tại | Tốt nhất | Nhận bước tệ | |
|---|---|---|---|---|
Quan sát:
- Giai đoạn nóng (), trạng thái hiện tại nhảy quanh đến , tệ hơn nhiều so với tốt nhất: SA đang khám phá, gần một nửa số bước tệ vẫn được nhận.
- Khoảng giữa () nó tìm thấy tối ưu .
- Cuối cùng trạng thái hiện tại lại trôi sang cực tiểu địa phương (chu trình thứ hai trong bảng trên) và kẹt ở đó khi đã nguội. Nếu in trạng thái hiện tại thay vì
bestthì đã sai: đây chính là lý do phải lưubest.
So với đáp án tối ưu
Cùng bộ dữ liệu, mỗi cách chạy lần, ngân sách bước mỗi lần (số đo thực tế):
| Phương pháp | Số lần ra tối ưu | Trung bình | Tệ nhất |
|---|---|---|---|
| Leo đồi 2-opt, một lần | |||
| Leo đồi, khởi động lại khi bước không cải thiện | |||
| SA, , |
Với các bộ thành phố ngẫu nhiên tọa độ trong ( bước, lần mỗi bộ), leo đồi một lần ra tối ưu đến số lần tùy bộ, còn SA ra tối ưu đến . Chương trình hoàn chỉnh dưới đây (chạy theo thời gian) đã được đối chiếu với Held-Karp trên bộ ngẫu nhiên , mỗi bộ chạy giây: đúng , bộ còn lại ra thay vì (chạy lại bộ đó thì ra đúng). Một lần trượt trên là lời nhắc rằng SA không có bảo đảm.
Cài đặt
Đọc và tọa độ, in độ dài chu trình tốt nhất tìm được và chính chu trình đó. Lịch nhiệt theo thời gian, bước 2-opt, tính .
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double rnd01() { return uniform_real_distribution<double>(0, 1)(rng); }
int rndInt(int lo, int hi) { return uniform_int_distribution<int>(lo, hi)(rng); }
int n;
vector<double> X, Y;
double dist(int a, int b) { return hypot(X[a] - X[b], Y[a] - Y[b]); }
double tourLength(const vector<int>& p) {
double s = 0;
for (int i = 0; i < n; i++) s += dist(p[i], p[(i + 1) % n]);
return s;
}
int main() {
scanf("%d", &n);
X.resize(n); Y.resize(n);
for (int i = 0; i < n; i++) scanf("%lf %lf", &X[i], &Y[i]);
const double TIME_LIMIT = 0.5; // seconds, keep a safety margin
const double T0 = 100, T1 = 0.01; // start / end temperature
auto start = chrono::steady_clock::now();
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin() + 1, p.end(), rng);
double cur = tourLength(p), best = cur;
vector<int> bestP = p;
double T = T0;
for (long long iter = 0; n >= 4; iter++) {
if ((iter & 255) == 0) { // read the clock only every 256 steps
double t = chrono::duration<double>(chrono::steady_clock::now() - start).count();
if (t > TIME_LIMIT) break;
T = T0 * pow(T1 / T0, t / TIME_LIMIT); // geometric cooling over time
}
// 2-opt neighbour: reverse p[i..j]; only edges (i-1,i) and (j,j+1) change
int i = rndInt(1, n - 1), j = rndInt(1, n - 1);
if (i > j) swap(i, j);
if (i == j) continue;
int a = p[i - 1], b = p[i], c = p[j], d = p[(j + 1) % n];
double delta = dist(a, c) + dist(b, d) - dist(a, b) - dist(c, d);
if (delta <= 0 || rnd01() < exp(-delta / T)) {
reverse(p.begin() + i, p.begin() + j + 1);
cur += delta;
if (cur < best - 1e-9) { best = cur; bestP = p; }
}
}
printf("%.4f\n", tourLength(bestP)); // recompute to remove drift
for (int i = 0; i < n; i++) printf("%d%c", bestP[i] + 1, i + 1 < n ? ' ' : '\n');
}
import math
import random
import sys
import time
def main():
data = sys.stdin.read().split()
n = int(data[0])
xs = [float(data[1 + 2 * i]) for i in range(n)]
ys = [float(data[2 + 2 * i]) for i in range(n)]
def dist(a, b):
return math.hypot(xs[a] - xs[b], ys[a] - ys[b])
def tour_length(p):
return sum(dist(p[i], p[(i + 1) % n]) for i in range(n))
TIME_LIMIT = 0.5 # seconds
T0, T1 = 100.0, 0.01 # start / end temperature
start = time.perf_counter()
p = list(range(n))
rest = p[1:]
random.shuffle(rest) # random module is seeded from the OS
p[1:] = rest
cur = best = tour_length(p)
best_p = p[:]
T = T0
it = 0
while n >= 4:
if it % 256 == 0: # read the clock only every 256 steps
t = time.perf_counter() - start
if t > TIME_LIMIT:
break
T = T0 * (T1 / T0) ** (t / TIME_LIMIT)
it += 1
i = random.randint(1, n - 1)
j = random.randint(1, n - 1)
if i > j:
i, j = j, i
if i == j:
continue
a, b, c, d = p[i - 1], p[i], p[j], p[(j + 1) % n]
delta = dist(a, c) + dist(b, d) - dist(a, b) - dist(c, d)
if delta <= 0 or random.random() < math.exp(-delta / T):
p[i:j + 1] = p[i:j + 1][::-1]
cur += delta
if cur < best - 1e-9:
best = cur
best_p = p[:]
print(f"{tour_length(best_p):.4f}")
print(" ".join(str(v + 1) for v in best_p))
main()
Trên bộ thành phố ở trên, cả hai bản đều in
50.4938
1 3 10 6 5 8 7 9 4 2
(hoặc cùng chu trình theo chiều ngược lại 1 2 4 9 7 8 5 6 10 3). Với mọi chu trình đều như nhau nên vòng lặp bị bỏ qua. Trong giây bản C++ chạy khoảng bước, bản Python khoảng bước (chậm hơn khoảng lần), nên với bài lớn hãy dùng C++.
Bài toán liên tục: đường tròn bao nhỏ nhất
Với trạng thái là một điểm trên mặt phẳng, bước đi là "dịch theo hướng ngẫu nhiên một đoạn tỉ lệ với ": nhiệt độ vừa là thang chấp nhận vừa là bán kính bước. Ví dụ tìm tâm làm nhỏ nhất (bán kính đường tròn bao):
// cost(x, y) = max distance from (x, y) to the points
double x = X[0], y = Y[0], cur = cost(x, y), best = cur, bx = x, by = y;
double T0 = 10, T1 = 1e-7, T = T0;
for (long long iter = 0;; iter++) {
if ((iter & 63) == 0) {
double t = chrono::duration<double>(chrono::steady_clock::now() - start).count();
if (t > TIME_LIMIT) break;
T = T0 * pow(T1 / T0, t / TIME_LIMIT);
}
// step length shrinks together with the temperature
double ang = rnd01() * 2 * M_PI, len = T * rnd01();
double nx = x + len * cos(ang), ny = y + len * sin(ang);
double nc = cost(nx, ny), delta = nc - cur;
if (delta <= 0 || rnd01() < exp(-delta / T)) {
x = nx; y = ny; cur = nc;
if (cur < best) { best = cur; bx = x; by = y; }
}
}
Trên thành phố ở trên (chạy giây) nó cho bán kính , đáp án đúng là . Trên bộ ngẫu nhiên (, tọa độ trong ), sai số lớn nhất so với vét cạn là : đủ cho bài chấm điểm, không đủ cho bài đòi sai số . Bài này có lời giải đúng kỳ vọng (thuật toán Welzl trong Thuật toán ngẫu nhiên), còn bài tổng khoảng cách nhỏ nhất (điểm Fermat) có Weiszfeld. Hàm lồi như vậy thì cũng có thể dùng tìm kiếm tam phân lồng nhau.
Độ phức tạp
SA không có độ phức tạp theo nghĩa thông thường: ta chọn trước thời gian chạy.
- Thời gian: . Với TSP 2-opt: tính , áp dụng (đảo đoạn) nhưng chỉ khi được nhận; về cuối tỉ lệ nhận rất thấp nên mỗi bước gần như . Thêm mỗi lần cập nhật
best(sao chép hoán vị), số lần này nhỏ. - Bộ nhớ: cho trạng thái hiện tại và trạng thái tốt nhất, cộng dữ liệu đầu vào.
- Chất lượng tăng theo số bước, nên mọi tối ưu hằng số (tính gia tăng, tránh
powmỗi bước, đọc đồng hồ thưa) đều trực tiếp làm đáp án tốt hơn.
So sánh: vét cạn TSP , Held-Karp thời gian và bộ nhớ (chỉ tới ); SA chạy được với hàng nghìn nhưng không bảo đảm tối ưu.
Khi nào dùng SA trong thi đấu
- Bài chấm điểm theo chất lượng (scoring, partial credit): điểm tỉ lệ với độ tốt so với mốc ban giám khảo. Đây là đất của SA.
- Bài chỉ nộp kết quả (output-only): có sẵn input, được chạy SA ở nhà hàng phút hay hàng giờ rồi nộp file (hoặc in sẵn đáp án).
- Không gian tìm kiếm nhỏ nhưng khó cấu trúc: SA thường tìm được tối ưu thật (như ví dụ trên), nhất là khi đề chỉ cần "đủ tốt" (không tệ hơn đáp án giám khảo quá ).
- Tối ưu hình học liên tục có hàm chi phí dễ tính: điểm Fermat, tâm đường tròn bao, đặt trạm. Thường có thuật toán đúng nhưng SA viết nhanh, dùng để vét subtask hoặc đối chiếu.
- Không dùng khi bài đòi đáp án tối ưu chính xác và có thuật toán đúng: một lần sai là mất cả test. Khi đó hãy nghĩ tới quay lui có cắt tỉa, quy hoạch động bitmask, tham lam có chứng minh. SA cũng hữu ích như máy dò: chạy SA trên test nhỏ để đoán cấu trúc đáp án tối ưu, rồi chứng minh và viết lời giải đúng.
⚠️ Lỗi thường gặp
- Đọc đồng hồ mỗi bước.
chrono::steady_clock::now()(hayclock()) tốn hàng chục nano giây, có thể nhiều hơn cả tính , số bước giảm vài lần. Chỉ đọc mỗi bước (ví dụ(iter & 255) == 0) và tính lại lúc đó. Ngược lại, đặtTIME_LIMITsát giới hạn đề là TLE: chừa lại thời gian đọc input, in output và độ lệch của máy chấm (ví dụ giới hạn giây thì dừng ở đến giây). Lưu ýclock()đo thời gian CPU, một số máy chấm đo thời gian thực. - Thang nhiệt độ sai. Triệu chứng: quá nhỏ so với thì SA chỉ là leo đồi; quá lớn thì đến cuối vẫn đi lung tung, kết quả tệ. Nhiệt độ phải cùng đơn vị với : tọa độ tới cần khác hẳn tọa độ tới . In tỉ lệ nhận bước tệ theo từng giai đoạn: nên khoảng đến lúc đầu và gần lúc cuối.
- In trạng thái hiện tại thay vì
best. Như ví dụ trên, cuối quá trình trạng thái hiện tại có thể đã trôi sang cực tiểu tệ hơn. Luôn lưu và inbest. - Cộng dồn bị trôi số.
cur += deltaqua hàng triệu bước tích lũy sai số dấu phẩy động; hoặc tệ hơn, công thức viết sai vàcurkhông còn đúng . Khi debug, thỉnh thoảng socurvới tính lại từ đầu (assert(fabs(cur - f(s)) < eps)); khi in kết quả, tính lại chobest. - Seed cố định hoặc
rand(). Seed cố định làm mọi lần chạy giống hệt nhau (chạy lại không có cơ hội khác) và dễ bị dựng test;rand()trên Windows chỉ tới nênrand() % nlệch và không chọn được chỉ số lớn. Dùngmt19937seed theo thời gian vàuniform_int_distribution. Khi debug thì tạm thời cố định seed để tái hiện lỗi. - Tính
expcho cả bước tốt. Với rất lớn,exp(-delta / T)tràn thànhinf(vẫn đúng nhưng tốn thời gian); với thì chia cho . Kiểm tradelta <= 0trước, và đảm bảo . - Bước đi phá ràng buộc hoặc quá to. Bước đi sinh trạng thái không hợp lệ (điểm ra ngoài miền, hai phần tử trùng nhau) thì phải chiếu về miền hợp lệ hoặc cộng phạt vào . Bước đi quá to (ví dụ trong bài liên tục dịch cố định đơn vị) thì lúc nguội không tinh chỉnh được; hãy cho độ dài bước giảm theo .
- Tin rằng SA đúng. Kết quả là heuristic: dù lần ra tối ưu trên một bộ test, vẫn có bộ khác trượt (như ở trên). Trên bài đòi đáp án chính xác, đối chiếu với vét cạn trên test nhỏ trước khi dựa vào nó, và ưu tiên thuật toán đúng nếu có.
Biến thể và liên hệ
- Leo đồi có hàm thế: nếu mỗi bước sửa làm một đại lượng nguyên dương giảm ngặt (ví dụ số cạnh vi phạm), leo đồi chắc chắn dừng và đôi khi chứng minh được là dừng ở lời giải hợp lệ. Khi đó nó là thuật toán đúng, không còn là heuristic (xem bài
dimahorsebên dưới). - Ngưỡng chấp nhận (threshold accepting, late acceptance): thay xác suất bằng "nhận nếu " với ngưỡng giảm dần, nhanh hơn vì không gọi
expvàrnd. - Tìm kiếm cục bộ lặp (iterated local search, basin hopping): leo đồi tới cực tiểu, nhiễu loạn mạnh vài phần tử, leo lại, giữ nếu tốt hơn.
- Tối ưu xen kẽ: khi cố định một phần, phần còn lại giải đúng được (như cố định cách chia nhóm thì vị trí tối ưu của mỗi trạm là trung vị hình học), xen kẽ hai bước và dùng SA hoặc khởi động lại để thoát cực tiểu.
- Quay lui với nhánh cận: chính xác, dùng SA để tìm trước một đáp án tốt làm cận ban đầu giúp cắt tỉa mạnh hơn.
Bài tập luyện
- Chia phe ngựa (dimahorse) (Rất khó): tìm kiếm cục bộ thuần: đổi nhóm một đỉnh vi phạm, số cặp kẻ thù cùng nhóm giảm ngặt nên chắc chắn dừng ở lời giải hợp lệ.
- Ăng-ten chuyển tiếp không gian con hành tinh (icpc26mbk) (Rất khó): bài -median Euclid NP-khó, chỉ cần không tệ hơn giám khảo quá : tìm kiếm cục bộ swap, xen kẽ với Weiszfeld, nhiều lần khởi động lại.
- Dựng cột ăng-ten (tddn26_antenna) (Chuyên gia): rải điểm sao cho khoảng cách nhỏ nhất lớn nhất, chấm điểm theo tỉ số với mốc; tối ưu liên tục có chiếu ràng buộc, nhiều điểm xuất phát và basin hopping.
- Trang trí (olp30426_decor) (Chuyên gia): SA trên tập đỉnh phụ với nhiều loại bước đi (thêm, xóa, dịch, trượt), cập nhật chi phí gia tăng chỉ cho các cặp bị ảnh hưởng.
- Các bức tường (tst23_walls) (Bậc thầy): bài chỉ nộp kết quả, chạy SA ở nhà với bước đi "đảo mặt gương một bức tường", dùng hàm chi phí xấp xỉ tính nhanh để khởi động.
Bình luận