Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT
BÀI 2: KĨ THUẬT QUAY LUI
Mở đầu
Bài học
Hình vẽ
Học xong bài này em sẽ: - Tìm hiểu được chương trình liệt kê dãy bit độ dài n bằng kĩ thuật đệ quy - Nêu được ý tưởng của kĩ thuật quay lui - Tìm hiểu được lời giải một số bài toán sử dụng kĩ thuật quay lui
Yêu cầu
Hình vẽ
Trong bài học trước, các em đã tìm hiểu bài toán Chọn mua đồ dùng học tập với các tình huống mua một đồ dùng hoặc hai đồ dùng. Nếu bài toán không cố định số lượng đồ dùng cần mua mà có thể mua một số đồ dùng với tổng giá trị không vượt quá T (đồng) và tổng mức độ yêu thức của các đồ dùng đó là lớn nhất, em hãy trình bày ý tưởng giải quyết bài toán
Bài toán Mua đồ tổng quát
Bài toán
Cho n đồ dùng với mức giá tương ứng là latex(p_0, p_1, ...., p_(n-1)) ( đồng) và có mức độ yêu thích của Hồng tương ứng là latex(s_0, s_1, ...., s_(n-)). Em hãy giúp Hồng chọn mua một số đồ dùng với tổng giá trị không vuột quá T ( đồng) và tổng mức độ yêu thích là lớn nhất.
Ảnh
Cách giải
Hình vẽ
Để giải quyết bài toán Mua đồ tổng quát bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dạy bít tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiê ra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích để chọn phương án tối ưu
Liệt kê dãy bit độ dài n
Câu hỏi
Em hãy tìm hiểu chương trình liệt kê dãy bit độ dài n bằng kĩ thuật đệ quy trong Hình 1 và chạy thử nghiệm chương trình. Cho biết số lượng dãy bit nhị phân độ dài 3, 5, 10 tương ứng là bao nhiêu
Ảnh
Cách xây dựng
1. Bắt đầu từ X rỗng, lệnh x = [ ] và gọi thủ tục đệ quy backtrack(0) để xây dựng bắt đầu từ phần tử 0/ 2. Thành phần i (latex(0 le i le n-1)) sẽ lần lượt nhận giá trị 0 và 1 bằng lệnh for v in reange(2) 3. Để xét được khả năng tiếp theo, hành động quay lui được thực hiện bằng cách loại bỏ ghi nhận thành phần cuối cùng của X bằng lệnh x.pop().
Quá trình xây dựng nhị phân
Ảnh
Kĩ thuật quay lui
Bài toán
Giả sử lời giải của bài toán có dạng X - latex(x_0, x_1,...,x_(n-1)) với latex(x_1 in C_1) Trong đó latex(C_1) là các tập các giá trị có thể của latex(x_1) để xét tất cả các khả năng của lời giải, ta xây dựng lời giải dần từng bước 1. Bắt đầu từ lời giải rỗng [ ] 2. Giả sử, hiện tại đang xây dựng được i thành phần latex(x_0, x_1,...,x_(n-1)), để xây dựng thành phần latex(x_i) cần xét từng khả năng trong latex(C_i) Quá trình sẽ dừng lại khi tất cả các khả năng lựa chọn của các thành phần của lời giải đều được xét
Mô hình
Ảnh
Bài tập
Bài 1
Em hãy tìm hiểu, soạn thảo chương trình giải toán Mua đô tổng quát trong Hình 4 bằng kĩ thuật quay lui và chạy thử nghiệm với các bộ dữ liệu trong Bảng 2
Ảnh
Bài 1
Ảnh
Bài 2
Hồng có n tệp dữ liệu được đánh số từ 0 đến n-1 và có kích thước tương ứng là latex(s_0, s_1,...,s_(n-1)) (Mb). Hồng muốn tìm cách lưu trữ được nhiều tệp dữ liệu nhâ bằng hai đĩa ổ cứng, mỗi ổ có dung lượng (Mb). Em hãy lập trình giải quyết bài toán trên, chương tình sẽ nhập vào số nguyên D và dãy số latex(s_0, s_1,...,s_(n-1)), sau đó đưa ra phương án lưu trữ là một dãy số latex(x_0, x_1,...,x_(n-1)), trong đó latex(x_i (0 le i le n - 1)) nhận 1 trong ba giá trị 0, 1 hoặc 2. Mô tả quá trình xây dựng các dãy X. Chạy thử nghiệm với các bộ dữ liệu trong bảng 3
Bài 2
Ảnh
Bài 2
Ảnh
Câu hỏi
Bài tập trắc nghiệm
Trong những câu sau đây, câu nào nói đúng khi nói về kĩ thuật quay lui
Kĩ thuật quay lui không thể liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán
Khi cài đặt kĩ thuật quay lui, bắt buộc phải sự dụng kĩ thuật để quy
Kĩ thuật quay lui là một kĩ thuật theo ý tưởng của kĩ thuật duyệt
Kết thúc
Tóm tắt bài học
Hình vẽ
Kĩ thuật quay lui xây dựng tất cả các khả năng của lời giải bằng cách mở rộng từng thành phần và quay lui, bắt đầu từ lời giải rỗng. Với cách làm này, kĩ thuật quay lui có thể xét tất cả các khả năng của lời giải và kiểm tra, đánh giá đề chọn nghiệm của bài toán theo ý tưởng của kĩ thuật duyệt Khi cài đặt kĩ thuật quay lui, người ta thường sử dụng kĩ thuật đệ quy
TÓM TẮT BÀI HỌC
Tạm biệt
Ảnh