Quay lui 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, từng bước một chọn một trong số các lựa chọn khả dĩ và đệ quy. Người trước hết đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào trong khoảng thời gian 1950.

Bạn Đang Xem: Thuật toán quay lui (Backtracking)

Tư tưởng

Dùng làm 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 thành phần. Mỗi thành phần lại được chọn bằng phương pháp thử tất cả những khả năng.

Xem Thêm : Nhiễm sắc thể là gì?

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

• Xét tất cả những giá trị X[1] có thể nhận, thử X[1] nhận thêm những 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 những 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 tuần tự giá trị đó.
• Thông tin cấu hình tìm được.

Thực chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).

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); [Bỏ chọn i cho X[k]]; } } } }

Ví dụ: Trò chơi Sudoku

Sudoku là một trò chơi khá phổ thông và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9×9 ô vuông con. Mỗi ô vuông con có mức giá trị trong khoảng tầm từ một đến 9. Lúc đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và sót lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ một đến 9, hàng dọc là các số khác nhau từ một đến 9, và mỗi khối 3×3 đây chính là các số khác nhau từ một đến 9. Sau đây là một trong những ví dụ về đề bài và lời giải:

Xem Thêm : Mộ số cách để khôi phục dữ liệu bị mã hóa bởi virus tống tiền

Vận dụng quay lui để giải bài toán sudoku. Ý tưởng: Từng bước một tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây lưu ý mảng chỉ có kích thước 9×9×9)

void solveSudoku(int S[][9], int x, int y){ if(y == 9){ if(x == 8){ printSolution(S); exit(0); } else { solveSudoku(S, x+1,0); } } else if(S[x][y] == 0){ for (int k = 1; k <=9; k++){ if(checkValid(S,x,y,k)){ S[x][y] = k; solveSudoku(S, x, y+1); S[x][y] = 0; } } } else { solveSudoku(S,x,y+1); } } boolean checkValid(int S[][9], int x, int y, int k){ for(int i = 0; i <9 ; i++){ if(S[x][i] == k) return false; } for(int i = 0; i <9 ; i++){ if(S[i][y] == k) return false; } int a = x/3, b = y/3; for(int i = 3*a; i < 3*a+3; i++){ for(int j = 3*b; j < 3*b+3; j++){ if(S[i][j] == k) return false; } } return true; }

Nhận xét

• -Ưu điểm: Việc quay lui là thử tất cả những tổng hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cấu hình thiết lập tránh khỏi việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời kì chạy.

• Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó phạm phải các nhược điểm sau:

  • Rơi vào tình trạng “thrashing”: qúa trình tìm kiếm cứ gặp phải thuyệt vọng với cùng một nguyên nhân.
  • Thực hiện các công việc dư thừa: Mỗi lần tất cả chúng ta quay lui, tất cả chúng ta cần phải thẩm định lại lời giải trong những khi đôi lúc điều đó không cấp thiết.
  • Không sớm phát hiện được những khả năng bị thuyệt vọng trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận mặt đc nhánh tìm kiếm sẽ đi vào thuyệt vọng.