App: TSP so găng greedy, SA và GA

Giới thiệu

Bài này cho 3 cách tìm tour ngắn đấu nhau. Cùng bản đồ và giờ đấu, ai ngắn hơn thì thắng.

Kiến thức cần nhớ

Greedy và 2-opt

• Greedy luôn đi thành phố gần nhất tiếp theo.
• Nhanh nhưng thiển cận, dễ chọn sai sớm.
• 2-opt tháo 2 cạnh cắt nhau rồi nối lại cho ngắn hơn.
• Ví dụ đời thường: đi chợ ghé sạp gần nhất rồi tối ưu lại vòng đi.

SA thoát kẹt bằng nhiệt

• SA bắt đầu từ tour ngẫu nhiên, đề xuất đổi 2-opt.
• Tour tệ hơn vẫn nhận với xác suất giảm dần theo nhiệt.
• Lịch mát hình học, kẹt lâu thì hâm nóng lại.
• Ví dụ đời thường: leo lên dốc nhỏ để xuống thung lũng sâu hơn.

GA đấu bằng quần thể

• GA giữ cả đàn tour, chọn cha mẹ bằng tournament.
• Lai OX giữ thứ tự, đột biến swap giữ đa dạng.
• Giữ tinh hoa elites sang thế hệ sau.
• Cùng seed và ngân sách giờ để đấu công bằng.

Ví dụ

• Input: bản đồ 8 thành phố có optimum brute-force. Output: ít nhất 1 metaheuristic chạm optimum.
• Giải thích: bản đồ nhỏ nên SA hoặc GA tìm được tour tốt nhất.
• Input: 5 bản đồ 50 thành phố. Output: SA và GA ngắn hơn greedy ít nhất 5%.
• Giải thích: greedy kẹt cực tiểu địa phương, 2 metaheuristic thoát được.

💻 Bài tập

Ngôn ngữ: C++ (khuyến nghị) hoặc Python có Numba. Dùng code ngày 78, 114, 115, 122. Nộp vào day-136-tsp/.

Bài 1: Khung thi đấu công bằng

struct Solver { virtual std::string name() const = 0;
                virtual std::vector<int> solve(const Matrix &d, uint64_t seed, double timeBudgetMs) = 0; };

Ràng buộc công bằng: cùng ngân sách thời gian (ví dụ 2 giây), cùng 10 seed, cùng máy. Mọi tour trả về phải hợp lệ (kiểm tra là hoán vị).

Bài 2: Bảng đấu

Bộ dữ liệu: berlin52 (tối ưu 7542), kroA100 (tối ưu 21282), và 1000 điểm ngẫu nhiên.

bộ          solver       best      trung_bình   độ_lệch   gap_so_tối_ưu
berlin52    Greedy       ...
berlin52    Greedy2Opt   ...
berlin52    SA           ...
berlin52    GA           ...
kroA100     ...
random1000  ...          (không có tối ưu, so với best tổng)

Bài 3: Hội tụ theo thời gian và báo cáo (nâng cao)

1. Ghi độ dài tour tốt nhất theo thời gian cho SA và GA. Vẽ cả 2 đường trên cùng hình (trung vị 10 seed).
2. Thử ngân sách 0.1, 1, 10 giây. Solver nào thắng ở ngân sách ngắn, solver nào thắng ở ngân sách dài?
3. Vẽ tour tốt nhất của mỗi solver trên kroA100.
4. REPORT.md: bảng, hình, khuyến nghị "khi nào dùng solver nào".

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

• Mọi tour hợp lệ, có kiểm tra tự động.
• Bảng đấu 3 bộ x 4 solver x 10 seed.
• Hình hội tụ theo thời gian.
• Khuyến nghị gắn với số liệu.

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

• Greedy nearest neighbor nhanh nhưng yếu ở điểm gì?
• 2-opt cải thiện tour bằng cách nào?
• SA chấp nhận tour tệ để làm gì?
• Vì sao đấu TSP phải cố định seed và giờ?

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