- vừa được xem lúc

Thuật toán quay lui (Backtracking)

0 0 38

Người đăng: Nguyen Van Truong

Theo Viblo Asia

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

Tư tưởng

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.

Bản 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ổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9x9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn 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ừ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3x3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước 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 chú ý 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ả các tổ 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ài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian 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ó mắc 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 bế tắc 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 chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
    • Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết đc nhánh tìm kiếm sẽ đi vào bế tắc.

Bình luận

Bài viết tương tự

- vừa được xem lúc

Giới thiệu Typescript - Sự khác nhau giữa Typescript và Javascript

Typescript là gì. TypeScript là một ngôn ngữ giúp cung cấp quy mô lớn hơn so với JavaScript.

0 0 495

- vừa được xem lúc

Cài đặt WSL / WSL2 trên Windows 10 để code như trên Ubuntu

Sau vài ba năm mình chuyển qua code trên Ubuntu thì thật không thể phủ nhận rằng mình đã yêu em nó. Cá nhân mình sử dụng Ubuntu để code web thì thật là tuyệt vời.

0 0 371

- vừa được xem lúc

Đặt tên commit message sao cho "tình nghĩa anh em chắc chắn bền lâu"????

. Lời mở đầu. .

1 1 685

- vừa được xem lúc

Tìm hiểu về Resource Controller trong Laravel

Giới thiệu. Trong laravel, việc sử dụng các route post, get, group để gọi đến 1 action của Controller đã là quá quen đối với các bạn sử dụng framework này.

0 0 331

- vừa được xem lúc

Phân quyền đơn giản với package Laravel permission

Như các bạn đã biết, phân quyền trong một ứng dụng là một phần không thể thiếu trong việc phát triển phần mềm, dù đó là ứng dụng web hay là mobile. Vậy nên, hôm nay mình sẽ giới thiệu một package có thể giúp các bạn phân quyền nhanh và đơn giản trong một website được viết bằng PHP với framework là L

0 0 417

- vừa được xem lúc

Bạn đã biết các tips này khi làm việc với chuỗi trong JavaScript chưa ?

Hi xin chào các bạn, tiếp tục chuỗi chủ đề về cái thằng JavaScript này, hôm nay mình sẽ giới thiệu cho các bạn một số thủ thuật hay ho khi làm việc với chuỗi trong JavaScript có thể bạn đã hoặc chưa từng dùng. Cụ thể như nào thì hãy cùng mình tìm hiểu trong bài viết này nhé (go).

0 0 413