Giao diện
Greedy & Backtracking
Khi đối mặt với bài toán tối ưu hóa, kỹ sư thường đứng trước hai lựa chọn chiến lược: cam kết sớm hay giữ quyền thay đổi. Greedy cam kết — tại mỗi bước, nó chọn phương án tốt nhất hiện tại và không bao giờ ngoảnh lại. Backtracking giữ mọi lựa chọn mở — nó duyệt hệ thống toàn bộ không gian nghiệm, quay lui ngay khi phát hiện nhánh vô vọng.
Hai paradigm này không thay thế nhau mà bổ sung cho nhau. Greedy cho tốc độ — thường O(n log n) — nhưng đòi hỏi chứng minh toán học rằng tối ưu cục bộ dẫn đến tối ưu toàn cục. Backtracking đảm bảo tìm nghiệm nếu tồn tại — nhưng chi phí mũ O(k^n) buộc bạn phải thiết kế cắt tỉa (pruning) thông minh. Hiểu đúng bản chất và giới hạn của từng paradigm là kỹ năng thiết kế thuật toán cốt lõi.
Bản chất hai paradigm
Greedy — Tham lam có chiến lược
Tại mỗi bước quyết định, Greedy chọn phương án tốt nhất xét riêng tại bước đó với kỳ vọng rằng chuỗi các lựa chọn cục bộ tối ưu sẽ dẫn đến nghiệm toàn cục tối ưu. Điều kiện tiên quyết: bài toán phải có tính chất lựa chọn tham lam (greedy-choice property) và cấu trúc con tối ưu (optimal substructure).
Đặc trưng kỹ thuật:
- Không quay lui — mỗi quyết định là vĩnh viễn
- Độ phức tạp thời gian thường là đa thức: O(n log n) hoặc tốt hơn
- Không phải lúc nào cũng cho nghiệm tối ưu — sai khi thiếu chứng minh
Ứng dụng tiêu biểu: Huffman Coding, Dijkstra, Kruskal/Prim MST, Activity Selection, Fractional Knapsack.
Backtracking — Duyệt có hệ thống
Backtracking xây dựng nghiệm từng bước, tại mỗi bước thử lần lượt các lựa chọn hợp lệ. Khi phát hiện lựa chọn hiện tại dẫn đến bế tắc, nó quay lui (undo) và thử lựa chọn tiếp theo. Bản chất là DFS trên cây không gian nghiệm kết hợp cắt tỉa.
Đặc trưng kỹ thuật:
- Duyệt toàn bộ không gian nghiệm nếu cần
- Độ phức tạp thường là mũ: O(k^n) hoặc O(n!)
- Pruning là chìa khóa — cắt tỉa tốt giảm thời gian hàng trăm lần
Ứng dụng tiêu biểu: N-Queens, Sudoku Solver, Graph Coloring, Constraint Satisfaction Problems (CSP).
So sánh trực diện
| Tiêu chí | Greedy | Backtracking |
|---|---|---|
| Chiến lược | Tối ưu cục bộ → Kỳ vọng tối ưu toàn cục | Duyệt hệ thống → Cắt tỉa nhánh bế tắc |
| Thời gian | Đa thức (nhanh) | Mũ (chậm, phụ thuộc pruning) |
| Đảm bảo tối ưu | Chỉ khi chứng minh được | Luôn tìm nghiệm nếu tồn tại |
| Bộ nhớ | O(1) – O(n) | O(depth) call stack |
| Khi nào dùng | Có greedy-choice property | Cần tất cả nghiệm, hoặc không có cách nhanh hơn |
| Rủi ro | Cho nghiệm sai nếu thiếu chứng minh | Timeout nếu pruning kém |
Lộ trình học
text
┌─────────────────────────────┐
│ Greedy & Backtracking │
└──────────┬──────────────────-┘
│
┌────────────────┼────────────────┐
▼ ▼
┌─────────────────┐ ┌──────────────────┐
│ GREEDY │ │ BACKTRACKING │
│ │ │ │
│ Huffman Coding │ │ N-Queens Problem │
│ (nén dữ liệu) │ │ (ràng buộc CSP) │
└─────────────────┘ └──────────────────-┘Thứ tự khuyến nghị:
Huffman Coding — Nền tảng Greedy: xây cây Huffman, mã prefix-free, phân tích tỷ lệ nén. Ứng dụng thực tế trong ZIP, GZIP, HTTP/2 HPACK.
N-Queens Problem — Kinh điển Backtracking: constraint propagation, chiến lược cắt tỉa, tối ưu bitwise. Kết nối với CSP trong công nghiệp.
🧠 Quiz
Câu 1: Bài N-Queens yêu cầu gì?
- [ ] A) Đặt N quân hậu sao cho tất cả cùng hàng
- [x] B) Đặt N quân hậu trên bàn cờ N×N sao cho không quân nào tấn công quân khác
- [ ] C) Tìm đường đi ngắn nhất cho quân hậu
- [ ] D) Đếm số ô an toàn trên bàn cờ
💡 Giải thích: Mỗi hàng đặt đúng 1 quân hậu. Tại mỗi hàng, thử từng cột — kiểm tra conflict (cùng cột, cùng đường chéo). Nếu conflict → backtrack. Thuật toán backtracking cắt tỉa rất hiệu quả: N=8 chỉ duyệt ~15,000 node thay vì 8⁸ = 16 triệu.
Câu 2: Huffman Coding tạo mã prefix-free nghĩa là gì?
- [ ] A) Mọi mã có cùng độ dài
- [x] B) Không mã nào là tiền tố (prefix) của mã khác → giải mã không nhập nhằng
- [ ] C) Mã bắt đầu bằng bit 0
- [ ] D) Mỗi ký tự có đúng 8 bit
💡 Giải thích: Prefix-free: nếu 'a' = "01", thì không ký tự nào có mã bắt đầu bằng "01" (như "010", "011"). Nhờ vậy, khi đọc bitstream, ta biết chính xác khi nào một ký tự kết thúc mà không cần delimiter. Đây là nền tảng của nén dữ liệu.