Brute-force và greedy nhập môn qua TSP

Giới thiệu

Bài này học vét cạn và tham lam qua giao hàng. Bạn hiểu nhanh và chuẩn khó cùng lúc.

Kiến thức cần nhớ

TSP — thăm mỗi nơi 1 lần

• Vào là n thành phố và khoảng cách.
• Ra là tour ngắn nhất quay về chỗ cũ.
• Ví dụ đời thường: shipper đi 1 vòng giao hết đơn.
• Phát biểu dễ nhưng giải tối ưu rất khó.

Vét cạn — thử hết

• Liệt kê mọi tour rồi chọn ngắn nhất.
• n thành phố có (n-1)! tour.
• 5 nơi còn làm tay, 10 nơi máy cũng đuối.
• Ví dụ đời thường: thử mọi đường đi rồi so.
• Chuẩn tuyệt đối nhưng chỉ dùng khi n nhỏ.

Tham lam — gần thì đi trước

• Mỗi bước đi tới nơi gần nhất chưa thăm.
• Nhanh nhưng hay sập bẫy đường cuối dài.
• Ví dụ đời thường: thấy quán gần là ghé luôn.
• Hợp khi cần nhanh, chấp nhận gần đúng.

Ví dụ

• Input: 3 nơi cách đều 10. Output: mọi tour dài 30.
• Giải thích: đường nào cũng bằng nhau nên 2 cách đồng thuận.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-016/. Khoảng cách là ma trận đối xứng std::vector<std::vector<double>>, tour bắt đầu và kết thúc ở thành phố 0.

Bài 1: Vét cạn TSP

4 thành phố:
     A  B  C  D
A    0 10 15 20
B   10  0 35 25
C   15 35  0 30
D   20 25 30  0
bruteForce -> 80, tour A B D C A

Đo thời gian với $n = 6, 8, 10, 11$. In bảng và ước lượng $n = 15$ mất bao lâu.

Bài 2: Tham lam láng giềng gần nhất

Viết nearestNeighbor(const Matrix &d, int start). Mỗi bước tới thành phố gần nhất chưa thăm. Hòa thì chọn chỉ số nhỏ hơn.

1. Chạy với mọi điểm xuất phát, lấy tour tốt nhất.
2. Sinh 200 điểm ngẫu nhiên trên mặt phẳng $[0, 1000]^2$ (seed cố định). So độ dài và thời gian với bruteForce ở $n = 10$.

Bài 3: Bẫy tham lam (nâng cao)

1. Tự thiết kế ma trận 5 thành phố mà tour tham lam từ 0 dài hơn tối ưu ít nhất 25%. Ghi ma trận và 2 tour vào README.md.
2. Chạy 1000 bộ 9 điểm ngẫu nhiên. In tỉ lệ greedy / optimal trung bình và lớn nhất.

Kết quả mẫu: avg ratio ~1.1-1.25, max ratio > 1.4

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

• Ví dụ 4 thành phố ra đúng 80.
• Bảng thời gian vét cạn cho thấy tăng theo giai thừa.
• Có ma trận bẫy tự thiết kế kèm giải thích.
• Nêu được độ phức tạp: vét cạn $O(n!)$, tham lam $O(n^2)$.

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

• TSP vào ra là gì?
• Vì sao vét cạn chỉ dùng khi n nhỏ?
• Tham lam đi thế nào?
• Khi nào chấp nhận nghiệm gần đúng?

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