Đề tài Phương pháp Tham lam

Nhóm 8: Báo cáo chương 5-phần 1: Đây là lần đầu nhóm thực hiện nên không thể tránh khỏi những thiếu sót, rất mong sự góp ý của Thầy và các bạn! Xin chân thành cám ơn Thầy và các bạn. Phương pháp “Tham lam”: Tiến trình thực hiện phương pháp Tham lam 1. Xác định cấu trúc con tối ưu 2. Xây dựng giải pháp đệ quy 3. Chứng minh: tại mỗi bước đệ qui, lựa chọn Tham lam là một trong những lựa chọn cho kết quả tối ưu 4. Chỉ ra: sau mỗi lựa chọn Tham lam, một trong những bài toán con sẽ rỗng 5. Xây dựng giải pháp đệ quy cho chiến lược Tham lam 6. Khử đệ quy Tổng quát, thực hiện phương pháp Tham lam qua các bước: 1. Tìm lựa chọn sao cho các bước tiếp theo chỉ việc giải quyết một bài toán con. 2. Chứng minh: với sự lựa chọn Tham lam tại mỗi bước  luôn tìm được 1 giải pháp tối ưu (cho bài toán ban đầu). 3. Chỉ ra rằng: với sự lựa chọn Tham lam tại mỗi bước  giải pháp tối ưu của bài toán con còn lại kết hợp với sự lựa chọn Tham lam này sẽ đi đến một giải pháp tối ưu (cho bài toán ban đầu). Hai đặc tính quan trọng của phương pháp tham lam: 1. Tính lựa chọn tham lam: Một bài toán có “tính lựa chọn Tham lam” nếu có thể tìm được một giải pháp tối ưu toàn cục bằng cách lựa chọn tối ưu cục bộ. 2. Cấu trúc con tối ưu: Một bài toán có “cấu trúc con tối ưu” nếu giải pháp tối ưu cho bài toán này chứa các giải pháp tối ưu cho các bài toán con của nó. Phần 3: Giải thuật mã hóa Huffman Giới thiệu bài toán: Giả sử có một thông báo C là một chuỗi các ký tự, trong đó mỗi ký tự xuất hiện độc lập với cùng một xác xuất tại bất kỳ vị trí nào trong thông báo. Yêu cầu đặt ra là mã hóa thông báo thành một chuỗi các ký tự 0, 1. Ví dụ: Xét thông báo gồm 5 ký tự a,b,c,d,e với tần suất các ký tự: Chiều dài trung bình của dãy nhị phân là:ltb=wili=3 Cách khác là: xây dựng từ mã không là tiền tố của nhau. Chiều dài trung bình của dãy nhị phân là:ltb=wili  2.2 Vậy có cách mã hóa nào có ltb=1) do begin sapxep(a); a[0]:=taonut(a[0],a[1]); gspt(a); end; end; Độ phức tạp tính toán: O(n2) Tính đúng đắn của giải thuật Huffman: Để chứng minh thuật toán Huffman là đúng, ta chỉ ra rằng bài toán xác định mã tiền tố tối ưu thể hiện lựa chọn tham lam. Bổ đề 16.2 Cho C là một bảng mẫu tự mà mỗi ký tự c có tần số là w[c]. Cho x và y là 2 ký tự trong C có tần số thấp nhất. Thì tồn tại mã tiền tố tối ưu đối với C mà trong đó những từ mã của x và y có chiều dài giống nhau và chỉ khác duy nhất ở bit cuối cùng. Bổ đề 16.3 Cho C là một bảng mẫu tự cho trước với tần số w[c] xác định với mỗi ký tự. Cho x và y là hai ký tự trong C với tần số nhỏ nhất. Cho C’ là bảng mẫu tự C với x và y bị xoá và có thêm ký tự mới z, vì vậy C’=C-{x,y}+{z}; xác định f của C’ cũng là của C, loại trừ rằng w[z]=w[x]+w[y]. Cho T’ là cây bất kỳ biểu diễn mã tiền tố tối ưu của bảng mẫu tự C’. Thì cây T, thu được từ T’ bằng việc thay thế nút lá z với một nút trong có x và y là con, biểu diễn mã tiền tố tối ưu cho bảng mẫu tự C. Bổ đề 16.4 Thủ tục Huffman hình thành nên mã tiền tố tối ưu. Cơ sở lý thuyết của phương pháp tham lam