Wiki › Thuật toán › Mô phỏng tôi luyện (Simulated Annealing)

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.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 22 phút 4 lượt xem

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 O(n!) hay O(2n) 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 s: 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í f(s) 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ừ s 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 s′, nếu f(s′)<f(s) thì chuyển sang s′". 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 f 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 e−Δ/T

SA sửa đúng chỗ đó. Đặt Δ=f(s′)−f(s):

P(nhận s′)={1nếu Δ≤0,e−Δ/Tnếu Δ>0.

T>0 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 T→0, SA trở thành leo đồi.

Ví dụ thực tế với hai mức tệ Δ=1 và Δ=5:

T e−1/T e−5/T
20 0.951 0.779
5 0.819 0.368
1 0.368 0.00674
0.1 4.54·10−5 1.93·10−22

Ta giảm dần T 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 Tk=c/logk) thì SA hội tụ về tối ưu toàn cục với xác suất 1. 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:

  1. Đủ nhỏ để f(s′) gần f(s) (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).
  2. Tính Δ nhanh, lý tưởng là O(1), không tính lại f 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 1≤i<j≤n−1 và đảo ngược đoạn pi,…,pj của chu trình. Chỉ hai cạnh thay đổi: (pi−1,pi) và (pj,pj+1) bị bỏ, (pi−1,pj) và (pi,pj+1) được thêm (các cạnh bên trong đoạn chỉ đổi chiều, độ dài không đổi). Vì vậy

Δ=d(a,c)+d(b,e)−d(a,b)−d(c,e),a=pi−1, b=pi, c=pj, e=pj+1.

Tính Δ tốn O(1); chỉ khi nhận bước đi mới phải đảo đoạn (O(n)). Cố định p0 (thành phố 1 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: T giảm từ T0 xuống T1 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 t∈[0,TL]:

T(t)=T0·(T1T0)t/TL.

Ư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ù n lớn hay nhỏ. Đọc đồng hồ khá đắt nên chỉ đọc mỗi 256 bước một lần.

Chọn T0, T1 theo độ lớn điển hình của Δ chứ không đoán mò:

  • T0: 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 30% đến 60%. Nếu Δ điển hình là δ thì T0≈δ đến 2δ.
  • T1: cuối cùng gần như không nhận bước tệ nhỏ nhất đáng kể, ví dụ T1≈δ/100 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 k 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ố 1..10), 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
x 14 14 16 6 16 20 5 14 4 17
y 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 O(2nn2)) là 50.4938, chu trình 1→2→4→9→7→8→5→6→10→3→1:

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 (i,j), nhận bước nào làm ngắn đi, lặp đến khi không cải thiện được" từ 2000 hoán vị ban đầu ngẫu nhiên. Nó chỉ dừng ở đúng bốn chu trình khác nhau, và chỉ 16% 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)
1,2,4,9,7,8,5,6,10,3 (tối ưu) 50.4938 318
1,3,10,6,5,2,8,7,9,4 50.7860 595
1,2,4,9,7,8,5,3,6,10 51.7306 455
1,4,9,7,8,2,5,3,6,10 52.0227 632

Chu trình tệ nhất trong bảng (52.0227) 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ố 2 và 3 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, 3000 bước, T0=20, T1=0.01, 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 độ T Hiện tại Tốt nhất Nhận bước tệ
0 20 107.13 107.13
0.1 9.352 69.61 55.11 49%
0.2 4.373 69.00 52.04 35%
0.3 2.045 64.07 50.79 21%
0.4 0.956 52.22 50.79 9%
0.5 0.447 50.51 50.49 6%
0.6 0.209 50.79 50.49 3%
0.8 0.046 50.79 50.49 2%
1.0 0.010 50.79 50.49

Quan sát:

  • Giai đoạn nóng (T≥4), trạng thái hiện tại nhảy quanh 64 đến 70, 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 (T≈0.5) nó tìm thấy tối ưu 50.49.
  • Cuối cùng trạng thái hiện tại lại trôi sang cực tiểu địa phương 50.79 (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ì best thì đã sai: đây chính là lý do phải lưu best.
So với đáp án tối ưu

Cùng bộ dữ liệu, mỗi cách chạy 1000 lần, ngân sách 20000 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 287/1000 51.1679 52.0227
Leo đồi, khởi động lại khi 2000 bước không cải thiện 953/1000 50.5076 50.7860
SA, T0=20, T1=0.01 1000/1000 50.4938 50.4938

Với các bộ 16 thành phố ngẫu nhiên tọa độ trong [0,100] (50000 bước, 300 lần mỗi bộ), leo đồi một lần ra tối ưu 13% đến 85% số lần tùy bộ, còn SA ra tối ưu 92% đến 100%. 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 200 bộ ngẫu nhiên n≤15, mỗi bộ chạy 0.1 giây: đúng 199/200, bộ còn lại ra 307.17 thay vì 288.89 (chạy lại bộ đó thì ra đúng). Một lần trượt trên 200 là lời nhắc rằng SA không có bảo đảm.

Cài đặt

Đọc n 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 O(1).

C++
#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');
}
Python
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ộ 10 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 n≤3 mọi chu trình đều như nhau nên vòng lặp bị bỏ qua. Trong 0.5 giây bản C++ chạy khoảng 5.9·106 bước, bản Python khoảng 2.8·105 bước (chậm hơn khoảng 20 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 T": 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 (x,y) làm nhỏ nhất maxi‖Pi−(x,y)‖ (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 10 thành phố ở trên (chạy 0.2 giây) nó cho bán kính 11.672622, đáp án đúng là 11.672618. Trên 60 bộ ngẫu nhiên (n≤30, tọa độ trong [0,100]), sai số lớn nhất so với vét cạn là 1.3·10−4: đủ cho bài chấm điểm, không đủ cho bài đòi sai số 10−6. Bài này có lời giải đúng O(n) 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: số bước×(chi phí tính Δ+xác suất nhận×chi phí áp dụng). Với TSP 2-opt: tính Δ O(1), áp dụng (đảo đoạn) 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ư O(1). Thêm O(n) mỗi lần cập nhật best (sao chép hoán vị), số lần này nhỏ.
  • Bộ nhớ: O(n) 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 pow mỗ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 O(n!), Held-Karp O(2nn2) thời gian và O(2nn) bộ nhớ (chỉ tới n≈20); SA chạy được với n 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á 1%).
  • 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() (hay clock()) 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 2k bước (ví dụ (iter & 255) == 0) và tính lại T lúc đó. Ngược lại, đặt TIME_LIMIT sá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 1 giây thì dừng ở 0.8 đến 0.9 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: T0 quá nhỏ so với Δ thì SA chỉ là leo đồi; T1 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 109 cần T0 khác hẳn tọa độ tới 100. In tỉ lệ nhận bước tệ theo từng giai đoạn: nên khoảng 40% đến 60% lúc đầu và gần 0% 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à in best.
  • Cộng dồn Δ bị trôi số. cur += delta qua 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à cur không còn đúng f. Khi debug, thỉnh thoảng so cur với f tính lại từ đầu (assert(fabs(cur - f(s)) < eps)); khi in kết quả, tính lại f cho best.
  • 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 32767 nên rand() % n lệch và không chọn được chỉ số lớn. Dùng mt19937 seed 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 exp cho cả bước tốt. Với Δ<0 rất lớn, exp(-delta / T) tràn thành inf (vẫn đúng nhưng tốn thời gian); với T=0 thì chia cho 0. Kiểm tra delta <= 0 trước, và đảm bảo T1>0.
  • 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 f. Bước đi quá to (ví dụ trong bài liên tục dịch cố định 10 đơn vị) thì lúc nguội không tinh chỉnh được; hãy cho độ dài bước giảm theo T.
  • Tin rằng SA đúng. Kết quả là heuristic: dù 1000/1000 lần ra tối ưu trên một bộ test, vẫn có bộ khác trượt (như 1/200 ở 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 dimahorse bê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 exp và 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 m-median Euclid NP-khó, chỉ cần không tệ hơn giám khảo quá 1%: 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 P đ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.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0