Tóm Tắt
suy nghĩ
được sử dụng để xử lý yếu tố liệt kê thông số kỹ thuật. mỗi thông số kỹ thuật được thiết kế xây dựng từng thành phần. mỗi mục được chọn lại để thử toàn bộ những năng lực .
Bạn đang xem: Backtracking là gì
Bạn đang đọc: Thuật toán quay lui (Backtracking)
Xem thêm : Tầm quan trọng của mua hàng trong doanh nghiệp thương mại – Blog của Mr. Logistics Việt Nam
các bước trong cấu hình của danh sách x [1 … n]:
- xem xét tất cả các giá trị có thể có của x [1], thử x [1] để lấy chúng. cho mỗi giá trị của x [1]:
- chúng tôi sẽ xem xét tất cả các giá trị có thể có của x [2], chúng tôi sẽ thử x [2] một lần nữa cho các giá trị đó. với mỗi giá trị của x [2], hãy xem xét giá trị của x [3] … và cứ tiếp tục như vậy cho đến bước:
- …
- ….
- xem xét tất cả các giá trị có thể có của x [n], cố gắng làm cho x [n] lần lượt nhận các giá trị đó.
- báo cáo cấu hình được tìm thấy.
Bản chất của backtracking là một tìm kiếm sâu.
mô hình thuật toán
- mã giả cho thuật toán bẻ khóa ngược.
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 9×9 ô 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 3×3 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:
Xem thêm : DMP là gì ? 1001 câu hỏi có đáp án về nền tảng công nghệ tiên tiến hữu dụng này
vận dụng backtracking để xử lý yếu tố sudoku. ý tưởng sáng tạo : mỗi bước tìm tập hợp những giá trị hoàn toàn có thể để điền vào ô trống, sau đó điền đệ quy vào ô tiếp theo. mã giả thuật toán ( ở đây, ma trận chỉ là 9 × 9 × 9 )
bình luận
Source: https://final-blade.com
Category : Kiến thức Internet
