Hướng dẫn giải của Bài toán người du lịch
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm đường đi qua tất cả các thành phố (từ 1 đến n) đúng một lần và quay lại thành phố xuất phát (thành phố 1) sao cho tổng chi phí là nhỏ nhất. Đây là bài toán du lịch salesman (TSP) kinh điển. Input cho biết n thành phố và m đường đi có hướng với chi phí tương ứng. Nếu không có đường đi trực tiếp giữa hai thành phố thì coi như chi phí vô cùng lớn (không thể đi). Do n ≤ 20, ta có thể sử dụng thuật toán quy hoạch động trên tập con (DP on subsets).
Các cách tiếp cận
Cách Quy hoạch động bitmask (Full TSP)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 20;
const ll INF = 1e18;
ll costMat[MAXN][MAXN]; // costMat[i][j]: chi phí từ i->j
ll dp[1 << MAXN][MAXN]; // dp[mask][u]: chi phí nhỏ nhất đi qua các node trong mask, kết thúc tại u
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// Khởi tạo ma trận chi phí với INF
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
costMat[i][j] = INF;
// Đọc input
for (int k = 0; k < m; ++k) {
int u, v;
ll c;
cin >> u >> v >> c;
u--; v--; // Chuyển về index 0
if (c < costMat[u][v]) {
costMat[u][v] = c;
}
}
// Khởi tạo DP
int totalMask = 1 << n;
for (int mask = 0; mask < totalMask; ++mask) {
for (int i = 0; i < n; ++i) {
dp[mask][i] = INF;
}
}
// Xuất phát từ node 0 (thành phố 1)
dp[1][0] = 0;
// Duyệt qua các mask
for (int mask = 1; mask < totalMask; ++mask) {
if ((mask & 1) == 0) continue; // Phải có node 0
for (int u = 0; u < n; ++u) {
if ((mask & (1 << u)) == 0) continue; // u phải có trong mask
if (dp[mask][u] == INF) continue;
for (int v = 0; v < n; ++v) {
if (mask & (1 << v)) continue; // v phải chưa có trong mask
// Cập nhật trạng thái mới
int newMask = mask | (1 << v);
if (costMat[u][v] != INF) {
dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + costMat[u][v]);
}
}
}
}
// Tìm kết quả: quay lại node 0
ll ans = INF;
int fullMask = (1 << n) - 1;
for (int u = 0; u < n; ++u) {
if (costMat[u][0] != INF && dp[fullMask][u] != INF) {
ans = min(ans, dp[fullMask][u] + costMat[u][0]);
}
}
if (ans >= INF) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
- Time Complexity: O(2^n * n^2)
- Space Complexity: O(2^n * n)
Đây là thuật toán chuẩn cho TSP với n nhỏ. Ta sử dụng một mảng 2 chiều dp[mask][u], trong đó mask là một bitmask biểu diễn tập hợp các thành phố đã đi qua, và u là thành phố cuối cùng trong hành trình hiện tại. Trạng thái dp[mask][u] lưu chi phí nhỏ nhất để đi từ thành phố 1 đến u qua tất cả các thành phố trong mask. Ta duyệt qua tất cả các mask, với mỗi mask, ta thử các cách chuyển sang mask lớn hơn bằng cách thêm một thành phố mới v chưa có trong mask, với chi phí là dp[mask][u] + cost[u][v]. Cuối cùng, ta xét các đường về lại thành phố 1 để tìm kết quả tối ưu.
Cách Backtracking có cắt tỉa (Branch and Bound)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[25][25];
int cmin = INT_MAX; // Chi phí nhỏ nhất trong ma trận c
int ans = INT_MAX;
bool visited[25];
int path[25]; // Lưu vết đường đi
void Try(int k, int currentCost) {
for (int i = 2; i <= n; ++i) {
if (!visited[i] && c[path[k-1]][i] != 0) {
// Cắt tỉa: nếu chi phí hiện tại + chi phí tối thiểu cho các bước còn lại >= ans thì bỏ qua
if (currentCost + cmin * (n - k + 1) >= ans) continue;
visited[i] = true;
path[k] = i;
int newCost = currentCost + c[path[k-1]][i];
if (k == n) {
// Đã đi đủ n thành phố, thử quay về 1
if (c[i][1] != 0) {
ans = min(ans, newCost + c[i][1]);
}
} else {
Try(k + 1, newCost);
}
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, cost;
cin >> u >> v >> cost;
c[u][v] = cost;
cmin = min(cmin, cost);
}
path[1] = 1; // Xuất phát từ thành phố 1
visited[1] = true;
Try(2, 0); // Bắt đầu từ bước thứ 2
cout << ans << endl;
return 0;
}
- Time Complexity: O(n!) trong trường hợp xấu nhất, nhưng thực tế chạy nhanh nhờ cắt tỉa.
- Space Complexity: O(n)
Thuật toán này thử tất cả các cách xếp thứ tự các thành phố (sinh hoán vị). Hàm Try(k) sẽ thử chọn thành phố tiếp theo cho vị trí thứ k trong hành trình. Để tăng tốc, ta sử dụng kỹ thuật Branch and Bound: ước lượng chi phí tối thiểu cần thêm để hoàn thành hành trình (dựa trên cmin) và so sánh với kết quả tốt nhất đang có (ans). Nếu chi phí dự kiến vượt quá ans, ta không cần duyệt nhánh đó nữa. Đây là cách tiếp cận đơn giản, dễ code nhưng chậm hơn DP nếu n lớn.
Cách Quy hoạch động dạng khác (Tối ưu hóa)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 20;
const ll INF = 1e18;
ll costMat[MAXN][MAXN];
ll dp[1 << MAXN][MAXN];
vector<int> adj[MAXN]; // Danh sách kề để tối ưu vòng lặp
int n, m;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
costMat[i][j] = INF;
for (int k = 0; k < m; ++k) {
int u, v;
ll c;
cin >> u >> v >> c;
u--; v--;
if (c < costMat[u][v]) {
costMat[u][v] = c;
}
}
// Xây dựng danh sách kề để giảm số lần lặp
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (costMat[i][j] != INF) {
adj[i].push_back(j);
}
}
}
int totalMask = 1 << n;
for (int mask = 0; mask < totalMask; ++mask) {
for (int i = 0; i < n; ++i) {
dp[mask][i] = INF;
}
}
dp[1][0] = 0;
for (int mask = 1; mask < totalMask; ++mask) {
if ((mask & 1) == 0) continue;
for (int u = 0; u < n; ++u) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == INF) continue;
// Thay vì duyệt tất cả v, chỉ xét các v có đường đi trực tiếp
for (int v : adj[u]) {
if (mask & (1 << v)) continue;
int newMask = mask | (1 << v);
dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + costMat[u][v]);
}
}
}
ll ans = INF;
int fullMask = (1 << n) - 1;
for (int u = 0; u < n; ++u) {
if (costMat[u][0] != INF && dp[fullMask][u] != INF) {
ans = min(ans, dp[fullMask][u] + costMat[u][0]);
}
}
if (ans >= INF) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
- Time Complexity: O(2^n * m)
- Space Complexity: O(2^n * n)
Phiên bản cải tiến củaApproach 1. Thay vì duyệt qua tất cả các thành phố có thể đến tiếp theo (v từ 0 đến n-1), ta chỉ duyệt qua các thành phố có đường đi trực tiếp từ u (danh sách kề). Điều này giảm độ phức tạp từ O(2^n * n^2) xuống O(2^n * m) (vì m < 400, số cạnh thực tế ít hơn n^2). Logic cơ bản vẫn giữ nguyên: quy hoạch động trên bitmask.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(2^n * n^2) | O(2^n * n) | Quy hoạch động bitmask (Full TSP) |
| 2 | O(n!) trong trường hợp xấu nhất, nhưng thực tế chạy nhanh nhờ cắt tỉa. | O(n) | Backtracking có cắt tỉa (Branch and Bound) |
| 3 | O(2^n * m) | O(2^n * n) | Quy hoạch động dạng khác (Tối ưu hóa) |
Bài học kinh nghiệm
- Bài toán này là TSP classic, với n ≤ 20, lời giải tối ưu là Quy hoạch động trên tập con (Subset DP) sử dụng bitmask.
- Mask 1<<(i-1) biểu diễn thành phố i.
- Trạng thái dp[mask][u] là chi phí nhỏ nhất đi qua các node trong mask, kết thúc tại u.
- Cần phải kiểm tra xem có đường đi trực tiếp (costMat[u][v] != INF) trước khi cập nhật DP.
Lỗi thường gặp
- Quên kiểm tra đường đi trực tiếp giữa các thành phố (giả định đồ thị đầy đủ trong khi input chỉ cho các cạnh có sẵn).
- Lỗi bitmask: Quên dịch bit (ví dụ: 1 << (u-1)) hoặc bắt đầu từ 0/1 không nhất quán.
- Tràn số (overflow): Chi phí có thể lên tới 10^6 và nhân với số thành phố, cần dùng kiểu dữ liệu lớn như long long.
- Quên trường hợp không có đường về thành phố xuất phát.
Bình luận