Capstone: tối ưu TSP và vẽ đồ thị tổng hợp

Giới thiệu

Bạn tìm đường thăm mọi thành phố ngắn nhất. Thử nhiều cách rồi so kết quả.

Kiến thức cần nhớ

TSP là gì

• TSP là đi qua mọi thành phố rồi về chỗ cũ.
• Định nghĩa: tìm tour ngắn nhất, bài toán khó nổi tiếng.
• Ví dụ đời thường: giống shipper đi mọi điểm rồi về kho.
• Thử mọi cách chỉ hợp khi thành phố ít.

Brute-force, greedy và DP

• Brute-force thử mọi tour, đúng nhưng rất chậm.
• Greedy mỗi bước đi tới thành phố gần nhất.
• Ví dụ đời thường: greedy như luôn chọn quán gần nhất.
• DP nhớ kết quả con nên nhanh hơn brute-force.

Heuristic và 2-opt

• Heuristic là cách gần đúng, nhanh nhưng không chắc tốt nhất.
• 2-opt gỡ hai đoạn chéo nhau để tour ngắn lại.
• Ví dụ đời thường: 2-opt như gỡ dây rối cho gọn.
• Vẽ ít giao cắt giúp nhìn tour rõ hơn.

# độ dài một tour
def do_dai(tour, xa):
    tong = 0  # cộng dồn quãng đường
    for i in range(len(tour)):
        a = tour[i]  # điểm hiện tại
        b = tour[(i + 1) % len(tour)]  # điểm tiếp theo
        tong += xa[a][b]  # cộng đoạn này
    return tong

Ví dụ

• Input 4 thành phố -> brute-force thử mọi tour rồi chọn ngắn nhất.
• Tour bị chéo nhau -> 2-opt gỡ chéo cho ngắn lại.

💻 Bài tập

Ngôn ngữ: C++ cho TSP, Python cho vẽ. Gom code ngày 16, 78, 114, 115, 121, 136. Nộp vào day-156-capstone/.

Bài 1: Thư viện TSP thống nhất

tsp/
  io.hpp          đọc TSPLIB (EUC_2D), đọc/ghi tour
  exact.hpp       bruteForce (n <= 10), heldKarp (n <= 20)
  heuristic.hpp   nearestNeighbor, twoOpt, orOpt
  meta.hpp        simulatedAnnealing, geneticAlgorithm
  verify.hpp      isValidTour, tourLength

CLI: tsp solve --algo sa --time 5 --seed 1 berlin52.tsp > tour.txt.

Test bắt buộc:

• Held-Karp khớp brute-force với mọi n <= 10 (100 bộ ngẫu nhiên).
• Mọi thuật toán trả tour hợp lệ.
• twoOpt không bao giờ làm tour dài hơn.

Bài 2: Bảng so sánh cuối cùng

Chạy mọi thuật toán phù hợp trên: 10 điểm, 20 điểm (có tối ưu từ Held-Karp), berlin52, kroA100, 1000 điểm ngẫu nhiên.

bộ        n      thuật_toán    độ_dài   gap(%)   thời_gian
tiny10    10     brute         ...      0
tiny10    10     heldKarp      ...      0
...

Bài 3: Trực quan hóa ít giao cắt (nâng cao)

1. Vẽ tour tốt nhất cho mỗi bộ. Đếm số cạnh cắt nhau trong tour (hàm ngày 120). Tour sau 2-opt phải có 0 giao cắt: chứng minh bằng số.
2. Tạo GIF quá trình SA cải thiện tour trên kroA100 (mỗi 5% tiến trình 1 khung).
3. REPORT.md: bảng, hình, giải thích vì sao tour tối ưu Euclid không có giao cắt.

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

• 3 nhóm test bắt buộc pass.
• CLI chạy được mọi thuật toán.
• Bảng so sánh 5 bộ dữ liệu.
• Có GIF và chứng minh 0 giao cắt sau 2-opt.

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

1. TSP yêu cầu tour thế nào?
2. Greedy chọn bước tiếp theo ra sao?
3. 2-opt làm gì?
4. Vì sao không brute-force khi n lớn?

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