SA cho TSP: transition, 2-opt và tỉa cành

Giới thiệu

Bài này học tìm tour ngắn thăm mọi thành phố. Dùng để giao hàng, khoan mạch và xếp lịch chạy.

Kiến thức cần nhớ

TSP đúng và xấp xỉ

• Định nghĩa: thăm mỗi thành phố 1 lần rồi về chỗ cũ.
• Vét cạn chỉ nổi tới khoảng 10-12 thành phố, quy hoạch động Held-Karp tới khoảng 25.
• Xấp xỉ gồm tham lam, 2-opt, ủ nhiệt, di truyền.
• Ví dụ đời thường: như shipper tìm vòng giao nhanh nhất.
• Tour đẹp gọn ít cắt, tour xấu nhiều chéo đan nhau.

2-opt gỡ rối

• Định nghĩa: cắt 2 cạnh chéo rồi nối chéo lại hết cắt.
• Tour ngắn ngay mà không tính lại toàn bộ đường.
• Lặp tới khi hết cặp cải thiện thì dừng lại.
• Ví dụ đời thường: như gỡ 2 dây đan bằng cách đổi đầu.
• Giữ danh sách cạnh gần để chạy nổi trăm thành phố.

Tỉa miền

• Định nghĩa: dùng tri thức cắt bớt không gian tìm kiếm.
• Gom điểm theo quận rồi giải từng cụm nhỏ trước.
• Cấm cạnh quá dài vượt ngưỡng cho phép.
• Ví dụ đời thường: như chia quận giao rồi mới nối liên quận.
• Giảm chục lần số tour mà hiếm mất nghiệm tốt.

Ví dụ

• Input: tour có 2 cạnh chéo nhau -> Output: 2-opt nối lại ngắn hơn.
• Giải thích: hết cắt chéo là tổng đường giảm ngay.

# Thử 2-opt trên 1 cặp cạnh
if dai(a, c) + dai(b, d) < dai(a, b) + dai(c, d):
    tour = noi_lai(tour, i, j)  # gỡ chéo, giữ ngắn
print(do_dai(tour))

💻 Bài tập

Ngôn ngữ: C++ (khuyến nghị vì nhiều vòng lặp) hoặc Python có Numba. Dùng lại code ngày 16, 78. Nộp vào day-114/.

Bài 1: 2-opt nhanh

double twoOptDelta(const std::vector<int> &tour, int i, int j, const Matrix &d);   // O(1)
void   apply2Opt(std::vector<int> &tour, int i, int j);                             // đảo đoạn i+1..j

delta = d(a,c) + d(b,d) - d(a,b) - d(c,d) với a = tour[i], b = tour[i+1], c = tour[j], d = tour[j+1].

Tour có 2 cạnh chéo nhau -> delta < 0, sau apply2Opt hết chéo
Test: delta tính O(1) bằng tourLength(sau) - tourLength(trước) trên 1000 cặp ngẫu nhiên

Bài 2: SA cho TSP

1. Láng giềng: chọn ngẫu nhiên (i, j), dùng twoOptDelta.
2. Lịch nhiệt hình học. Khởi tạo bằng tham lam.
3. Chạy trên bộ berlin52 (TSPLIB, tối ưu đã biết = 7542) và 1 bộ 200 điểm ngẫu nhiên.

bộ            greedy    greedy+2opt    SA       tối_ưu
berlin52      ...       ...            ...      7542
random200     ...       ...            ...      (không biết)

Vẽ tour tốt nhất của SA trên berlin52.

Bài 3: Tỉa cành bằng danh sách láng giềng (nâng cao)

1. Với mỗi thành phố, giữ 10 thành phố gần nhất (dùng k-d tree ngày 69).
2. Chỉ thử 2-opt với c nằm trong danh sách láng giềng của a.
3. Chạy trên 2000 điểm ngẫu nhiên. So thời gian và độ dài tour với bản không tỉa.
4. Thêm Or-opt (dời 1-3 thành phố liên tiếp sang chỗ khác). So kết quả.

✅ Tiêu chí hoàn thành

• twoOptDelta khớp tính lại toàn bộ trên 1000 cặp.
• SA trên berlin52 trong vòng 5% tối ưu.
• Bảng so sánh có số thật và hình tour.
• Bài 3 cho thấy tỉa cành nhanh hơn rõ mà tour gần như không dài hơn.

❓ Câu hỏi ôn tập

• TSP cần tìm gì?
• 2-opt gỡ cái gì?
• Đổi kề khác đảo đoạn sao?
• Tỉa miền để làm gì?

🌕 Bạn đã hoàn thành ngày 114. Làm hết bài tập phía trên rồi sang ngày tiếp theo.