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 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. | 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. Nội dung Ôn tập Bài toán tổ hợp Phương pháp sinh Thuật toán quay lui Ô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 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. 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. Bài toán tổ hợp Ví dụ: Có 3 nhân viên bảo vệ làm 3 ca sáng, chiều tối. Trong 1 ca chỉ có 1 bảo vệ. Hỏi các cách bố trí các bảo vệ? Mã hóa bài toán: {x, y, z} là tập biến có thứ tự mô tả cho 3 ca :sáng, chiều, tối theo thứ tự. Miền trị của 3 biến là { a,b,c } mô tả cho 3 bảo vệ. Các phép gán x y z a b c a c b b a c b c a c a b c b a Số lời giải là số hoán vị của tập hợp 3 phần tử này: 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! Bài toán tổ hợp Ví dụ: Tìm số chuỗi có độ dài 3 ký tự xyz với x ∈ { a,b,c}, y ∈ { d,e}, z ∈ { m,n,t} Nhận xét: 3 biến có 3 miền trị khác nhau x y z a d m a d n a d t a e m a e n a e t b d m b d n b d t b e m b e n b e t c d m c d n c d t c e m c e n c e t Số phép gán: 3 * 2 * 3 = 18 Tích của các số phần tử của các miền trị Độ phức tạp: nm với n: số phần tử trung bình của mỗi miền trị, m: là số miền trị Bài toán tổ hợp Bài toán tổ hợp có độ 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. Phương pháp sinh (Generating) Định | 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. Nội dung Ôn tập Bài toán tổ hợp Phương pháp sinh Thuật toán quay lui Ô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 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. 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. Bài toán tổ hợp Ví dụ: Có 3 nhân viên bảo vệ làm 3 ca sáng, chiều tối. .
