Backtracking là gì

  -  

Quay lui là 1 trong kĩ thuật xây cất giải thuật dựa trên đệ quy. Ý tưởng của con 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ới đệ quy. Tín đồ đầu tiên đặt ra thuật ngữ này (backtrack) là công ty toán học bạn Mỹ D. H. Lehmer vào trong thời hạn 1950.

Bạn đang xem: Backtracking là gì

Tư tưởng

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

Các bước trong việc liệt kê thông số kỹ thuật dạng X<1...n>:

Xét toàn bộ các cực hiếm X<1> rất có thể nhận, thử X<1> nhận những giá trị đó. Cùng với mỗi quý hiếm 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 cực hiếm X<2> lại xét khả năng giá trị của X<3>...tiếp tục như vậy tính đến bước:.......Xét tất cả giá trị X hoàn toàn có thể nhận, thử mang đến X dấn lần lượt giá trị đó.Thông báo thông số kỹ thuật tìm được.

Bản chất của con quay lui là một quá trình tìm tìm theo chiều sâu(Depth-First Search).

Xem thêm: Fairy Tail Vs One Piece 2 - Game One Piece Đại Chiến Giang Hồ

Mô hình thuật toán

Mã giả cho thuật toán cù lui.

Backtracking(k) for() if () >;if () <Đưa ra kết quả>; else Backtracking(k+1);>;

Ví dụ: Trò đùa Sudoku

Sudoku là 1 trong những trò chơi khá thịnh hành và chắc ai 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ó mức giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số trong những ô 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ừ bỏ 1-9 vào những ô con lại sao cho: mặt hàng ngang là các số khác biệt từ 1 mang đến 9, mặt hàng dọc là những số khác biệt từ 1 đến 9, cùng mỗi khối 3x3 chính là các số không giống nhau từ 1 mang lại 9. Sau đó là 1 ví dụ như về đề bài xích và lời giải:
*

Áp dụng con quay lui để giải việc sudoku. Ý tưởng: mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và kế tiếp đệ quy để điền ô tiếp theo. đưa mã của thuật toán (ở đây để ý mảng chỉ có kích 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 == 0){ for (int k = 1; k

Nhận xét

-Ưu điểm: câu hỏi quay lui là thử toàn bộ các tổ hợp để tìm kiếm được một lời giải. Thế bạo gan của phương thức này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp không hoàn chỉnh, nhờ kia giảm thời hạn chạy.

Xem thêm: Võ Lâm Truyền Kỳ 2 - Một Số Hỗ Trợ Sau Khi Phục Sinh Bạn Đồng Hành

Nhược điểm: vào trường hợp xấu độc nhất độ phức tạp của cù 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 search kiếm cứ gặp gỡ phải thất vọng với cùng một nguyên nhân.Thực hiện tại các các bước dư thừa: mỗi lần chúng ta quay lui, chúng ta cần phải review lại giải mã trong khi đôi lúc điều ấy không cần thiết.Không nhanh chóng phát hiện nay được các tài năng bị thất vọng trong tương lai. Tảo lui chuẩn, không có cơ chế nhìn về sau này để nhận biết được nhánh tìm kiếm sẽ lấn sân vào bế tắc.