Tóm tắt¶

Tóm tắt cốt lõi¶

Thuật toán quay lui về mặt bản chất là một phương pháp tìm kiếm vét cạn. Nó tìm kiếm các lời giải đáp ứng các điều kiện quy định bằng cách thực hiện duyệt theo chiều sâu không gian lời giải. Trong quá trình tìm kiếm, khi tìm thấy một lời giải thỏa mãn điều kiện, nó sẽ được ghi lại. Quá trình tìm kiếm kết thúc sau khi tìm thấy tất cả các lời giải hoặc khi quá trình duyệt hoàn tất.
Quá trình tìm kiếm của thuật toán quay lui gồm hai phần: thử nghiệm và quay lui. Nó thử nghiệm các lựa chọn khác nhau thông qua tìm kiếm theo chiều sâu. Khi gặp các tình huống vi phạm ràng buộc, nó sẽ đảo ngược lựa chọn trước đó, quay về trạng thái trước đó, và tiếp tục khám phá các phương án khác. Thử nghiệm và quay lui là hai thao tác theo hai hướng ngược nhau.
Các bài toán quay lui thường chứa nhiều ràng buộc, những ràng buộc này có thể được sử dụng để thực hiện các thao tác cắt tỉa. Cắt tỉa có thể kết thúc sớm các nhánh tìm kiếm không cần thiết, giúp cải thiện đáng kể hiệu suất tìm kiếm.
Thuật toán quay lui chủ yếu được sử dụng để giải quyết các bài toán tìm kiếm và bài toán thỏa mãn ràng buộc. Mặc dù các bài toán tối ưu hóa tổ hợp có thể được giải quyết bằng quay lui, nhưng thường có các giải pháp hiệu quả hơn hoặc có hiệu suất tốt hơn.
Bài toán hoán vị nhằm tìm tất cả các hoán vị có thể có của các phần tử trong một tập hợp cho trước. Chúng ta sử dụng một mảng để ghi lại xem mỗi phần tử đã được chọn hay chưa, từ đó cắt tỉa các nhánh tìm kiếm cố gắng chọn lặp lại cùng một phần tử, đảm bảo mỗi phần tử được chọn đúng một lần.
Trong bài toán hoán vị, nếu tập hợp chứa các phần tử trùng lặp, kết quả cuối cùng sẽ chứa các hoán vị trùng lặp. Chúng ta cần áp đặt một ràng buộc sao cho các phần tử bằng nhau chỉ có thể được chọn một lần trong mỗi vòng, điều này thường được thực hiện bằng cách sử dụng một tập hợp băm (hash set).
Bài toán tổng tập con nhằm tìm tất cả các tập con của một tập hợp cho trước có tổng bằng một giá trị mục tiêu. Vì tập hợp không có thứ tự nhưng quá trình tìm kiếm lại xuất kết quả theo mọi thứ tự nên các tập con trùng lặp sẽ được tạo ra. Chúng ta sắp xếp dữ liệu trước khi quay lui và sử dụng một biến để chỉ ra điểm bắt đầu duyệt của mỗi vòng, từ đó cắt tỉa các nhánh tìm kiếm tạo ra các tập con trùng lặp.
Đối với bài toán tổng tập con, các phần tử bằng nhau trong mảng sẽ tạo ra các tập con trùng lặp. Chúng ta tận dụng điều kiện tiên quyết là mảng đã được sắp xếp bằng cách kiểm tra xem các phần tử liền kề có bằng nhau hay không để thực hiện cắt tỉa, đảm bảo các phần tử bằng nhau chỉ có thể được chọn một lần trong mỗi vòng.
Bài toán \(n\) quân hậu nhằm tìm các cách xếp đặt \(n\) quân hậu trên một bàn cờ kích thước \(n \times n\) sao cho không có hai quân hậu nào có thể tấn công nhau. Các ràng buộc của bài toán này bao gồm ràng buộc hàng, ràng buộc cột, và ràng buộc đường chéo chính cùng đường chéo phụ. Để đáp ứng các ràng buộc hàng, chúng ta áp dụng chiến lược đặt quân theo từng hàng, đảm bảo đặt đúng một quân hậu trên mỗi hàng.
Việc xử lý ràng buộc cột và ràng buộc đường chéo là tương tự nhau. Đối với ràng buộc cột, chúng ta sử dụng một mảng để ghi lại xem mỗi cột đã có quân hậu hay chưa, từ đó biểu thị xem ô được chọn có hợp lệ hay không. Đối với ràng buộc đường chéo, chúng ta sử dụng hai mảng để ghi lại riêng biệt xem quân hậu có tồn tại trên mỗi đường chéo chính hoặc đường chéo phụ hay không. Thách thức nằm ở chỗ tìm ra quy luật của chỉ số hàng-cột đặc trưng cho các ô nằm trên cùng một đường chéo chính (đường chéo phụ).

Hỏi & Đáp¶

Hỏi: Làm thế nào để hiểu mối quan hệ giữa quay lui và đệ quy?

Nhìn chung, quay lui là một chiến lược thuật toán, trong khi đệ quy được xem như là một công cụ.

Quay lui thường được cài đặt bằng đệ quy. Tuy nhiên, quay lui chỉ là một ứng dụng của đệ quy, cụ thể là việc sử dụng nó trong các bài toán tìm kiếm.
Cấu trúc của đệ quy phản ánh một mô hình giải quyết vấn đề dựa trên việc phân rã một bài toán lớn thành các bài toán con, và nó thường được sử dụng trong chia để trị, quay lui, và quy hoạch động (đệ quy có nhớ).