Phương pháp sinh và thuật toán quay lùi

Hàm đệ quy là hàm mà trong thân hàm lạigọi chính nó.• Hàm đệ quy kém hiệu qủa vì: tốn bộ nhớva gọi hàm qúa nhiều lần. Tuy nhiên viếthàm đệ quy rất ngắn gọn.Tuy nhiên nhiềugiải thuật vẫn phải dùng kỹ thuật đệ quyvì việc khử đệ quy không dễ dàng.• Vòng lặp và stack là những kỹ thuật giúpkhử giải thuật đệ quy.
Nội dung trích xuất từ tài liệu:
Phương pháp sinh và thuật toán quay lùi Chương 8 Phương pháp sinh vàThuật toán quay lui. Mục tiêu• Giải thích được sinh dữ liệu là gì.• Biết sử dụng một số giải thuật sinh.• Biết sử dụng giải thuật quay lui để giải một số bài toán. 2 Nội dung• Ôn tập• Bài toán tổ hợp• Phương pháp sinh• Thuật toán quay lui 3 Ôn tập• Hàm đệ quy là hàm mà trong thân hàm lại gọi chính nó.• Hàm đệ quy kém hiệu qủa vì: tốn bộ nhớ va gọi hàm qúa nhiều lần. Tuy nhiên viết hàm đệ quy rất ngắn gọn.Tuy nhiên nhiều giải thuật vẫn phải dùng kỹ thuật đệ quy vì việc khử đệ quy không dễ dàng.• Vòng lặp và stack là những kỹ thuật giúp khử giải thuật đệ quy. 4 8.1- Bài toán tổ hợp• Có n biến x1, x2, x3, ..., xn• Mỗi biến xi có thể mang trị thuộc về 1 tập hợp Pi  Miền của bài toán là tập tích P1 x P2 x P3 x ... x Pn• Phép gán trị (assignment): Là một bộ trị a1, a2, a3, ..., an Trong đó a1  ai ∈ Pi• Một lời giải của bài toán là 1 phép gán trị.• Một phép gán trị được gọi là một cấu hình. 5 Bài toán tổ hợp Các phép gán x y z• Ví dụ: Có 3 nhân viên bảo vệ a b c làm 3 ca sáng, chiều tối. Trong a c b 1 ca chỉ có 1 bảo vệ. Hỏi các b a c cách bố trí các bảo vệ? b c a• Mã hóa bài toán: c a b {x, y, z} là tập biến có thứ tự c b a mô tả cho 3 ca :sáng, chiều, tối theo thứ tự. Số lời giải là số hoán vị của tập hợp 3 Miền trị của 3 biến là phần tử này:{ a,b,c } mô tả cho 3 bảo vệ. 3*2*1 = 3! = 6. Bài toán liệt kê các hoán vị của một tập hợp n phần tử có thứ tự có độ phức tạp n! 6 Bài toán tổ hợp x y z a d m Số phép gán: a d n 3 * 2 * 3 = 18• Ví dụ: Tìm số a d t a e m chuỗi có độ dài 3 a e n Tích của các ký tự xyz với a e t số phần tử b d mx ∈ { a,b,c}, của các b d n b d t miền trịy ∈ { d,e}, b e m b e nz ∈ { m,n,t} b e t c d m• Nhận xét: 3 biến c d n Độ phức tạp: nm với c d t có 3 miền trị n: số phần tử trung bình c e m của mỗi miền trị, khác nhau c e n m: là số miền trị c e t 7 Bài toán tổ hợp Bài toán tổ hợpcó độ phức tạp là n! hoặc nm Làm thế nào tạo ra các phép gán trị ?  Phương pháp sinh. 88.2- Phương pháp sinh (Generating) 9 8.2.1- Định nghĩa• Sinh: Tạo ra dữ liệu.• Phương pháp sinh: Từ dữ liệu ban đầu, sinh ra dữ liệu kế tiếp cho đến khi kết thúc.• Dùng để giải quyết bài toán liệt kê của lý thuyết tổ hợp.• Điều kiện của thuật toán sinh:(1) Có thể xác định 1 thứ tự tập các cấu hình của tổ hợp (thứ tự của các phép gán trị, thường dùng thứ tự từ điển).(2)Có một cấu hình cuối (điều kiện kết thúc của giải thuật).(3) Có một cách để suy ra được cấu hình kế tiếp. 10 Thứ tự từ điển• S1=“1234589”• S2=“1235789”• S1 < S2 nếu có 1 vị trí i tại đó S1[ i ] < S2[ i ] 11 8.2.2- Một ví dụ x y z Dùng thứBài toán:Tìm số chuỗi có a d m tự từ điển a d nđộ dài 3 ký tự xyz với để so sánh a d tx ∈ { a,b,c}, y ∈ { d,e}, a e m các phépz ∈ { m,n,t} a e n ...