Table of contents
Open Table of contents
1. Ý tưởng
Backtracking là chiến lược giải bài toán bằng cách xây dựng lời giải dần dần, và loại bỏ sớm những con đường không dẫn tới kết quả.
2. Thành phần
Ta thường có hai loại ràng buộc:
- Ràng buộc cục bộ — kiểm tra tại từng bước, xem lựa chọn hiện tại có hợp lệ không.
- Ràng buộc toàn cục — kiểm tra khi lời giải đã đầy đủ, xem nó có là một lời giải hoàn chỉnh không.
Mã giả:
3. Các bài toán kinh điển
2.1. N-queens
Đầu tiên chúng ta phải xác định được ràng buộc cục bộ và ràng buộc toàn cục.
- Ràng buộc cục bộ: Kiểm tra xem vị trí con hậu hiện tại có xung đột với các con hậu trước đó(cùng hàng, cột, đường chéo)
- Ràng buộc toàn bộ: Đã xác định đủ n con hậu hay chưa
Khi đó, thuật toán sẽ chạy như sau:
- Tiến từng bước: đặt từng quân hậu từ hàng 1 đến hàng n.
- Kiểm tra cục bộ tại mỗi bước — nếu không hợp lệ, quay lui.
- Nếu đến hàng n mà vẫn không có xung đột nào — ta đã có một lời giải hoàn chỉnh