Backtracking (Quay lui) là kỹ thuật giải bài toán dựa trên đệ quy, xây dựng giải pháp từng bước, loại bỏ các nhánh không thỏa mãn ràng buộc.
Áp dụng cho:
- Bài toán quyết định: tìm một giải pháp khả thi.
- Bài toán tối ưu: tìm giải pháp tốt nhất.
- Bài toán liệt kê: tìm tất cả giải pháp khả thi.
Thuật toán thử các nhánh, nếu không dẫn đến giải pháp thì quay lui (backtrack) để thử nhánh khác.
Thuật toán chung
Bước 1: Nếu vị trí hiện tại là đích → thành công. Bước 2: Ngược lại, Bước 3: Nếu vị trí hiện tại là ngõ cụt → thất bại. Bước 4: Nếu không phải ngõ cụt → khám phá và lặp lại các bước trên.
Ví dụ: Bài toán N-Queen
Đặt n quân hậu trên bàn cờ n×n sao cho không quân nào ăn được quân khác. Giải cho 4-Queen:
{0,1,0,0}
{0,0,0,1}
{1,0,0,0}
{0,0,1,0}
Ví dụ: Chuột trong mê cung (Rat in a Maze)
Tìm đường từ [0][0] đến [n-1][n-1] trong ma trận, tránh chướng ngại vật. Dùng backtracking thử từng bước, quay lui khi gặp đường cụt.