Tìm hiểu về thuật toán Quay Lui (Backtracking): Tư tưởng, Mô hình và Ứng dụng

Quay lui (Backtracking) là một kỹ thuật thiết kế giải thuật mạnh mẽ dựa trên đệ quy, thường được sử dụng để giải quyết các bài toán tìm kiếm nghiệm trong một không gian nghiệm lớn. Thuật toán này hoạt động bằng cách xây dựng lời giải từng bước, tại mỗi bước, thuật toán sẽ chọn một trong số các lựa chọn khả dĩ và tiếp tục đệ quy. Nếu lựa chọn hiện tại không dẫn đến lời giải, thuật toán sẽ quay lui (backtrack) để thử một lựa chọn khác. Thuật ngữ “backtrack” được đề xuất lần đầu bởi nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Tư tưởng cốt lõi của thuật toán Quay Lui

Quay lui đặc biệt hữu dụng trong việc liệt kê các cấu hình, trong đó mỗi cấu hình được xây dựng từ các phần tử, và mỗi phần tử lại được chọn thông qua việc thử tất cả các khả năng.

Quá trình liệt kê cấu hình, ví dụ X[1…n], diễn ra như sau:

  1. Bước 1: Xác định tất cả các giá trị mà X[1] có thể nhận. Thử gán lần lượt các giá trị này cho X[1]. Với mỗi giá trị của X[1], ta thực hiện bước tiếp theo.
  2. Bước 2: Xác định tất cả các giá trị mà X[2] có thể nhận. Thử gán lần lượt các giá trị này cho X[2]. Với mỗi giá trị của X[2], ta tiếp tục xét khả năng của X[3], và cứ tiếp tục như vậy cho đến bước cuối cùng.
  3. Bước n: Xác định tất cả các giá trị mà X[n] có thể nhận. Thử gán lần lượt các giá trị này cho X[n]. Khi X[n] đã được gán giá trị, ta thông báo cấu hình tìm được.

Về bản chất, thuật toán quay lui là một quá trình tìm kiếm theo chiều sâu (Depth-First Search – DFS) trên cây không gian trạng thái của bài toán.

Mô hình thuật toán Quay Lui

Dưới đây là mã giả mô tả 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];
      }
    }
  }
}

Trong đó:

  • k: chỉ số của phần tử hiện tại đang được xét.
  • D: tập hợp các giá trị có thể gán cho phần tử thứ k.
  • Chấp nhận i: điều kiện để giá trị i được chấp nhận cho phần tử thứ k.
  • Thành công: điều kiện để một cấu hình được coi là một lời giải hợp lệ.

Ứng dụng thuật toán Quay Lui: Giải bài toán Sudoku

Sudoku là một trò chơi trí tuệ phổ biến, trong đó người chơi cần điền các số từ 1 đến 9 vào một bảng vuông 9×9, sao cho mỗi hàng, mỗi cột và mỗi khối 3×3 đều chứa tất cả các số từ 1 đến 9 mà không lặp lại. Một số ô vuông sẽ được điền sẵn số, và nhiệm vụ của người chơi là điền vào các ô còn trống.

Thuật toán quay lui (Backtracking)Thuật toán quay lui (Backtracking)

Thuật toán quay lui có thể được áp dụng để giải bài toán Sudoku như sau:

  1. Tìm ô trống: Xác định một ô trống trên bảng Sudoku.
  2. Thử các giá trị: Thử điền các số từ 1 đến 9 vào ô trống đó.
  3. Kiểm tra tính hợp lệ: Với mỗi giá trị, kiểm tra xem việc điền số đó có làm vi phạm luật chơi Sudoku hay không (tức là, số đó có xuất hiện trong cùng hàng, cột hoặc khối 3×3 hay không).
  4. Đệ quy: Nếu giá trị là hợp lệ, gọi đệ quy thuật toán để tiếp tục điền các ô trống còn lại.
  5. Quay lui: Nếu không có giá trị nào hợp lệ, hoặc nếu việc điền một giá trị dẫn đến bế tắc sau này, quay lui và thử một giá trị khác cho ô trống hiện tại.

Dưới đây là mã giả của thuật toán giải Sudoku bằng quay lui (lưu ý rằng mảng S có kích thước 9×9):

void solveSudoku(int S[9][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; // Quay lui: bỏ chọn và thử giá trị khác
      }
    }
  } else {
    solveSudoku(S,x,y+1);
  }
}

boolean checkValid(int S[9][9], int x, int y, int k){
  // Kiểm tra hàng
  for(int i = 0; i < 9 ; i++){
    if(S[x][i] == k) return false;
  }
  // Kiểm tra cột
  for(int i = 0; i < 9 ; i++){
    if(S[i][y] == k) return false;
  }
  // Kiểm tra khối 3x3
  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;
}

Ưu điểm và Nhược điểm của thuật toán Quay Lui

Ưu điểm:

  • Tính tổng quát: Quay lui có thể áp dụng cho nhiều bài toán tìm kiếm, liệt kê cấu hình.
  • Khả năng tránh các trường hợp không cần thiết: Nhiều cài đặt quay lui có thể tránh việc thử các trường hợp chưa hoàn chỉnh, giúp giảm thời gian chạy.
  • Dễ cài đặt: So với một số thuật toán phức tạp khác, quay lui tương đối dễ hiểu và cài đặt.

Nhược điểm:

  • Độ phức tạp cao: Trong trường hợp xấu nhất, độ phức tạp của quay lui có thể là cấp số mũ, đặc biệt khi không gian tìm kiếm lớn.
  • Khả năng rơi vào tình trạng “thrashing”: Quá trình tìm kiếm có thể gặp phải bế tắc lặp đi lặp lại với cùng một nguyên nhân.
  • Thực hiện các công việc dư thừa: Việc đánh giá lại lời giải mỗi khi quay lui có thể gây ra công việc dư thừa.
  • Không có cơ chế nhìn trước: Quay lui chuẩn không có khả năng dự đoán các nhánh tìm kiếm sẽ dẫn đến bế tắc trong tương lai. Do đó, nó có thể đi vào các nhánh không có triển vọng.

Mặc dù có những nhược điểm, thuật toán quay lui vẫn là một công cụ quan trọng và hữu ích trong việc giải quyết nhiều bài toán khác nhau trong khoa học máy tính và các lĩnh vực liên quan. Việc lựa chọn sử dụng quay lui hay một thuật toán khác phụ thuộc vào đặc điểm cụ thể của bài toán và yêu cầu về hiệu suất.