Tìm Hiểu Về Thuật Toán Quay Lui (Backtracking)

DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)

Trong bài viết này chúng ta sẽ tìm hiều về thuật toán quay lui.

Thuật toán quay lui (Backtracking)

Quay lui hay Backtracking là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

Quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1...n]:

• Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
• Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]...tiếp tục như vậy cho tới bước:
• ...
• ....
• Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
• Thông báo cấu hình tìm được.

Mô hình thuật toán

• Mã giả cho thuật toán quay lui.

Backtracking(k) { for([Mỗi phương án chọn i(thuộc tập D)]) { if ([Chấp nhận i]) { [Chọn i cho X[k]]; if ([Thành công]) { [Đưa ra kết quả]; } else { Backtracking(k+1); //=> thoát khỏi bước thứ i và quay lui về bước thứ i-1 tiếp tục xét các phần tử [Bỏ chọn i cho X[k]]; } } } }

Đây là một thuật toán đòi hỏi phải có khả năng logic tốt một chút, và để có thể hình dung được thuật toán quay lui bạn phải thực sự nắm rõ Hàm đệ quy. Mình có một bài viết riêng về đệ quy nếu bạn chưa nắm rõ đệ quy có thể đọc thêm: Tìm hiểu về Hàm đệ quy trong lập trình.

Mình sẽ mô phỏng lại quá trình thực hiện của thuật toán Backtracking.

Ví dụ mình có hàm Backtracking liệt kê dãy nhị phân có độ dài là 3(Tập chung vào hàm backtrac thôi nhé).

#include <iostream> using namespace std; int n = 3; int a[3]; void show(){ for(int i = 0; i<n; i++){ cout<<a[i]; } cout<<"\n"; } void Backtracking(int k){ for(int i = 0; i<= 1; i++) { a[k] = i; if(k == n-1){ show(); } else{ Backtracking(k+1); } } } int main() { Backtracking(0); }

Mình có thể mô phỏng lại quá trình thực hiện của hàm trên. Nếu bạn nhìn vào hàm backtracking có thế hình dung được quá trình chạy của hàm như bên dưới thì tức là bạn đã hiểu hàm backtracking, còn nếu chưa thì bạn tiếp tục cố gắng nhé, vì đây thực sự không phải là một hàm quá dễ.

#include <iostream> using namespace std; int n = 3; int a[3]; void show(){ for(int i = 0; i<n; i++){ cout<<a[i]; } cout<<"\n"; } void moPhong_Backtracking(){ int k = 0; for(int i = 0; i<= 1; i++) { a[k] = i; k = 1; for(int i1 = 0; i1 <= 1; i1++){ a[k] = i1; k = 2; for(int i2 = 0; i2 <= 1; i2++){ a[k] = i2; show(); } k=1; } k = 0; } } int main() { moPhong_Backtracking(); }

Tương tự nếu như hàm Backtracking mà là liệt kê dãy nhị phân có độ dài là 100 thì nó sẽ có 100 vòng lặp lồng vào nhau như bên trên.

Cảm ơn bạn đã đọc bài viết chúc bạn học tốt!

[Xem tất cả bài viết chủ đề C/C++ tại đây]