Greedy & Backtracking - Tổng Quan

"Greedy lấy cái tốt nhất ngay bây giờ. Backtracking thử tất cả rồi chọn." - HPN

Hai Paradigm Quan Trọng

🏃 Greedy (Tham Lam)

Philosophy: Tại mỗi bước, chọn lựa chọn tốt nhất hiện tại với hy vọng dẫn đến kết quả tối ưu toàn cục.

Đặc điểm:

• Không quay lui (no backtracking)
• Nhanh: Thường O(N log N) hoặc tốt hơn
• Không phải lúc nào cũng đúng! Cần chứng minh.

Ví dụ điển hình:

• Huffman Coding (nén dữ liệu)
• Dijkstra (shortest path)
• Kruskal/Prim (MST)
• Activity Selection

🔙 Backtracking (Quay Lui)

Philosophy: Thử từng khả năng, nếu không thỏa mãn → quay lui và thử khả năng khác.

Đặc điểm:

• Duyệt toàn bộ không gian tìm kiếm
• Exponential: Thường O(k^N) hoặc N!
• Pruning (cắt tỉa) để giảm không gian tìm kiếm

Ví dụ điển hình:

• N-Queens Problem
• Sudoku Solver
• Maze Solving
• Constraint Satisfaction Problems (CSP)

So Sánh

Aspect	Greedy	Backtracking
Approach	Local optimal → Global optimal	Try all → Prune invalid
Time	Polynomial (fast)	Exponential (slow)
Guarantee	Không luôn đúng	Luôn tìm được nếu có
When to use	Có chứng minh greedy works	Tìm TẤT CẢ solutions
Memory	O(1) - O(N)	O(depth) stack

Roadmap Module

Bắt đầu từ đâu?

1. Huffman Coding - Nền tảng của ZIP, GZIP
2. N-Queens Problem - Classic backtracking

💡 HPN's Rule

"Greedy khi có thể chứng minh. Backtracking khi cần tất cả solutions hoặc không có cách nào tốt hơn."