Hướng dẫn backtracking c++ - backtracking c ++
Show
Đã đăng vào thg 7 27, 2017 4:42 CH 4 phút đọc 4 phút đọc 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ưởngDù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]:
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
Ví dụ: Trò chơi SudokuSudoku 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)
Nhận xét
All rights reserved Thuật toán quay lui (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. 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. Thuật toán quay lui thường được sử dụng để giải bài toán liệt kê các cấu hình (như bài toán sinh các xâu nhị phân). Mỗi cấu hình được xây dựng bằng cách xác định 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]: Để cài đặt thuật toán quay lui, chúng ta sử dụng một chương trình con (hàm Thuật toán quay lui sẽ bắt đầu bằng lời gọi Dưới đây, chúng ta cùng xem mã chương trình sinh các dãy nhị phân có độ dài Các giải khác bằng cách sử dụng vòng lặp, xin mời bạn đọc xem tại đây Thuật toán sinh các dãy nhị phân có độ dài n Mời các bạn xem chi tiết trong bài Thuật toán giải sudoku bằng quay lui backtracking Xét bàn cờ tổng quát kích thướ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). |