TSP dưới 3 chiến lược - brute-force, greedy, DP

Giới thiệu

Bài này học bài toán người bán hàng rong TSP. Bạn dùng nó để chọn tour ngắn nhất theo quy mô n.

Kiến thức cần nhớ

Bài toán TSP

• Cho n thành phố, tìm vòng qua hết mà ngắn nhất.
• Bản tối ưu thuộc lớp NP-khó. Bản quyết định "có tour dài không quá K không" là NP-đầy đủ: kiểm một tour cho sẵn thì dễ, tìm thì khó.
• Ví dụ đời thường: như shipper tìm vòng giao hết đơn mà ít xăng nhất.
• Cần cả nghiệm chuẩn n nhỏ và mẹo nhanh n lớn.

Vét cạn

• Liệt kê mọi hoán vị, tính tổng đường rồi giữ ngắn nhất.
• Cố định điểm xuất phát vì tour xoay vòng là 1.
• Cỡ n nhân giai thừa nên n bằng 20 là bó tay.
• Giá trị duy nhất là đáp án chuẩn để chấm mẹo khác.

Tham lam láng giềng gần nhất

• Mỗi bước đi tới thành phố chưa thăm gần nhất.
• Chỉ cỡ n bình phương nên chạy tới hàng nghìn thành phố.
• Không bảo đảm tốt: vét sạch cụm gần rồi nhảy đắt sang cụm xa.
• Ví dụ đời thường: như ăn hết món gần rồi mới chạy xa, tổng đường dài.

Held-Karp và so sánh

• Trạng thái là tập đã thăm và điểm đang đứng.
• Số trạng thái n nhân 2 mũ n, vẫn mũ nhưng hơn hẳn giai thừa.
• Cài bằng mặt nạ bit, không sao chép tập mỗi trạng thái.
• Quy tắc: n nhỏ vét cạn, n vừa Held-Karp, n lớn tham lam.

Ví dụ

• Input: mọi thành phố trên 1 đường thẳng. Output: tour tối ưu đi 1 lèo rồi quay về.
• Giải thích: tổng bằng 2 lần chiều dài đoạn, cả 3 cách đều ra vậy.
• Input: dữ liệu 2 cụm xa nhau. Output: tham lam dài hơn đáp án chuẩn rõ rệt.
• Giải thích: tham lam vét 1 cụm trước rồi trả cú nhảy đắt.

💻 Bài tập

Ngôn ngữ: C++. Dùng lại code ngày 16. Nộp vào day-078/.

Bài 1: Held-Karp

std::pair<double, std::vector<int>> heldKarp(const Matrix &d);
// dp[mask][j]: đường ngắn nhất bắt đầu ở 0, đi qua đúng tập mask, kết thúc ở j
// mask là bit, luôn chứa bit 0

Ma trận 4 thành phố ngày 16 -> 80, cùng tour với vét cạn
Thành phố trên 1 đường thẳng tại 0, 1, 3, 7 -> 14 (đi tới 7 rồi quay về)

Bài 2: So 3 chiến lược

Sinh điểm ngẫu nhiên trên mặt phẳng với n = 8, 10, 12, 16, 20, 5 bộ mỗi cỡ.

n    brute(ms)    held_karp(ms)    greedy(ms)    greedy/opt
8    ...
20   (bỏ qua)     ...

Vẽ thời gian theo n (trục y log). Ước lượng n lớn nhất Held-Karp chạy được trong 10 giây và bộ nhớ khi đó.

Bài 3: Cải thiện tham lam bằng 2-opt (nâng cao)

1. twoOpt(tour, d): lặp tìm cặp cạnh (a,b), (c,d) mà đảo đoạn giữa làm tour ngắn đi. Dừng khi không cải thiện được.
2. Chạy greedy + 2-opt trên n = 12..20 và so với Held-Karp. In tỉ lệ trung bình.
3. Chạy greedy + 2-opt trên n = 1000. In độ dài và thời gian.

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

• Held-Karp khớp vét cạn với mọi n <= 10 (50 bộ ngẫu nhiên).
• Bảng so sánh có số thật và hình thời gian.
• 2-opt giảm rõ tỉ lệ greedy/opt.
• Viết được số trạng thái $n 2^n$ và chi phí mỗi trạng thái $O(n)$ nên tổng $O(n^2 2^n)$.

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

• TSP phát biểu thế nào và vì sao NP-khó?
• Vét cạn tốn cỡ bao nhiêu?
• Tham lam thất bại ở dữ liệu nào?
• Held-Karp hơn vét cạn ở điểm nào?

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