Chương trình bài toán tham lam bài toán balo c năm 2024

Uploaded by

Hồ Văn

Nội dung chính Show

Uploaded by
Available Formats
Share this document
Did you find this document useful?
Is this content inappropriate?
Uploaded by
Reward Your Curiosity

0% found this document useful (0 votes)

291 views

17 pages

Copyright

Available Formats

DOCX, PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

0% found this document useful (0 votes)

291 views17 pages

Bài Niên Luận Cái Balo Nl26

Uploaded by

Hồ Văn

Jump to Page

You are on page 1of 17

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

Hỗ trợ thanh toán qua INTERNET BANKING tất cả các ngân hàng: VietcomBank, BIDV, VietinBank, SacomBank, TechcomBank, Á Châu, TPbank, MBbank, AgriBank, VPbank, SHB, MaritimeBank, DongAbank, VIB, EximBank, HDbank, NCB, Việt Á, OceanBank, PGbank, BacAbank...

Bạn cần đăng nhập để tải code qua chức năng này!

ĐĂNG NHẬP NGAY

Hỗ trợ CHUYỂN KHOẢN TRỰC TIẾP qua các số tài khoản ngân hàng: VietcomBank, BIDV, VietinBank, SacomBank, TechcomBank, Á Châu, TPbank, MBbank, AgriBank, VPbank, SHB, MaritimeBank

Bạn cần đăng nhập để tải code qua chức năng này!

ĐĂNG NHẬP NGAY

1. ĐẠI HỌC KHOA HỌC KHOA CÔNG NGHỆ THÔNG TIN [[ Tiểu luận học phần Phân tích Thiết kế thuật toán THUẬT TOÁN THAM LAM (GREEDY ALGORITHM) Học viên thực hiện: Nhóm 8 ‐ Lớp KHMT Khóa 2009‐2011 Hoàng Minh Lê Viết Chinh Nguyễn Mạnh Cường Lương Việt Tiến Trần Khánh Hưng Giáo viên hướng dẫn: TS Hoàng Quang Huế, Tháng 11 năm 2009
2. lam http://www.ebook.edu.vn Trang 1 LỜI NÓI ĐẦU Giải thuật cho những bài toán tối ưu thường đi qua một số bước, với một tập hợp các chọn lựa tại mỗi bước. Với nhiều bài toán tối ưu hoá có thể sử dụng phương pháp đơn giản và hiệu quả hơn phương pháp qui hoạch động. Phương pháp tham lam luôn chọn phương án tốt nhất vào thời điểm hiện tại. Nó chọn tối ưu cục bộ với hy vọng rằng lựa chọn này sẽ dẫn đến một kết quả tối ưu toàn cục. Trong chương này sẽ chỉ ra những bài toán tối ưu mà có thể được giải quyết bằng phương pháp tham lam. Trước khi đọc chương này chúng ta nên đọc kỹ về phần quy hoạch động. Phương pháp tham lam không phải luôn mang lại các kết quả tối ưu, nhưng có nhiều bài toán nó có thể giải quyết được. Trong khuôn khổ đề tài này, nhóm chúng tôi xin đưa ra các phần như sau: - Phần 1: giới thiệu bài toán chọn hoạt động, đối với vấn đề này thì phương pháp tham lam là hiệu quả để đưa ra kết quả. Ta sẽ đi đến một phương pháp tham lam bởi việc xét đến đầu tiên là một giải pháp quy hoạch động và sau đó chỉ ra rằng ta có thể luôn đưa ra những lựa chọn tham lam để đi đến một kết quả tối ưu. - Phần 2: nhắc lại những yếu tố cơ bản của phương pháp tham lam, đưa ra một một cách tiếp cận trực tiếp hơn để chứng minh phương pháp tham lam đúng hơn dựa trên quy hoạch động đã đề cập ở phần 1. - Phần 3: giới thiệu một ứng dụng quan trọng của kỹ thuật tham lam: một mô hình của các chuẩn nén dữ liệu. - Phần 4: ta nghiên cứu kỹ một số lý thuyết tổng hợp cơ sở được gọi là "matroids" mà đối với vấn đề này phương pháp tham lam luôn đưa ra kết quả tối ưu. - Phần 5: minh hoạ ứng dụng của việc sử dụng maitroids trong một bài toán lập lịch làm việc với thời hạn cuối cùng và số tiền phạt. Mặc dù nội dung của tiểu luận được dịch từ Chương 16 trong cuốn Introdution To Algorithms, đây là một cuốn sách được viết khá công phu và kỹ lưỡng của nhóm tác giả Thomas H. Cormen, Charles E. Leiserson và Ronald L. Rivest. Tuy nhiên, vì thời gian thực hiện tiểu luận có hạn, đồng thời còn nhiều hạn chế trong vấn đề ngôn ngữ, nên chắc
3. lam http://www.ebook.edu.vn Trang 2 chắn tiểu luận sẽ có nhiều sai sót. Rất mong sự góp ý của Thầy và các bạn lớp Cao học ngành Khoa Học Máy Tính khóa 2009 để chúng tôi hoàn chỉnh tiểu luận. Xin chân thành cảm ơn TS. Hoàng Quang đã tận tụy giúp đỡ chúng tôi hoàn thành tiểu luận này.
4. lam http://www.ebook.edu.vn Trang 3 PHẦN 1: BÀI TOÁN CHỌN HOẠT ĐỘNG 1.1.Giới thiệu bài toán Bài toán sắp xếp lịch cho nhiều hoạt động với ý nghĩa để có thể sử dụng chung một tài nguyên (mỗi thời điểm chỉ có một hoạt động sử dụng tài nguyên chung), với mục tiêu là sắp xếp sao càng có nhiều hoạt động tương thích sử dụng tài nguyên càng tốt. Giả sử ta có một tập hợp S = {a1,a2,..an } là tập các hoạt động muốn sử dụng tài nguyên, ví dụ một hội trường, chỉ mỗi một hoạt động tại mỗi thời điểm. Mỗi hoạt động ai sẽ có thời điểm bắt đầu là si và thời điểm kết thúc là fi, với điều kiện 0 ≤ si < fi < ∞. Nếu hoạt động ai được chọn, thì nó sẽ độc chiếm tài nguyên trong khoảng thời gian [si, fi). Hoạt động ai và aj được gọi là tương thích lẫn nhau nếu như khoảng thời gian [si, fi) và [aj, fj) là không giao nhau (Ví dụ ai và aj là tương thích nếu si ≥ fj hoặc sj ≥ fi ). Trong bài toán chọn hoạt động ta phải chọn tập con lớn nhất của các hoạt động tương thích lẫn nhau. Chẳng hạn, xem tập S của các hoạt động sau, mà ta có thể sắp xếp tăng dần theo thời điểm kết thúc. i 1 2 3 4 5 6 7 8 9 10 11 Si 1 3 0 5 3 5 6 8 8 2 12 Fi 4 5 6 7 8 9 10 11 12 13 14 Ta sẽ thấy một cách ngắn gọn là tại sao nó thuận lợi để xem xét các hoạt động trong trình tự sắp xếp. Chẳng hạn như, một tập con {a3, a9, a11 } bao gồm những hoạt động tương thích lẫn nhau. Nó không phải là tập con lớn nhất, vì một tập con {a1, a4, a8, a11} là lớn hơn. Thật ra {a1, a4, a8, a11} là tập con lớn nhất của các hoạt động tương thích lẫn nhau; một tập con lớn nhất khác là {a2, a4, a9, a11}. Ta sẽ giải quyết bài toán này trong một vài bước. Ta bắt đầu bởi việc đưa ra công thức của giải pháp quy hoạch động đối với bài toán này trong đó ta tổng hợp các giải pháp tối ưu đối với hai bài toán con để thiết lập giải pháp tối ưu của bài toán gốc. Ta có các lựa chọn khi quyết định các bài toán để sử dụng trong một giải pháp tối ưu. Sau đó, ta sẽ nhận thấy rằng ta chỉ cần một lựa chọn duy nhất - lựa chọn tham lam - và sau khi ta lựa chọn chỉ còn một bài toán con, một bài toán con còn lại sẽ rỗng. Dựa trên những nhận xét
5. lam http://www.ebook.edu.vn Trang 4 này, ta sẽ xây dựng một giải thuật tham lam đệ quy để giải quyết bài toán lập lịch hoạt động. Ta sẽ hoàn thành quá trình xây dựng giải thuật tham lam bởi việc biến đổi giải thuật đệ quy sang giải thuật lặp. Mặc dù những bước ta thực hiện trong phần này thể hiện mối liên quan nhiều hơn là tiêu biểu cho sự phát triển của phương pháp tham lam, chúng minh hoạ cho mối quan hệ của phương pháp tham lam và quy hoạch động. 1.2. Cấu trúc con tối ưu của bài toán chọn hoạt động Như đã đề cập ở trên, ta bắt đầu bằng phương quy hoạch động để giải quyết bài toán lựa chọn hoạt động. Như ở chương 15, bước đầu tiên là tìm ra cấu trúc con tối ưu và sau đó sử dụng nó để xây dựng một giải pháp tối ưu cho bài toán từ các giải pháp tối ưu cho các bài toán con. Ta nhận thấy rằng ở chương 15 ta cần định nghĩa một không gian thích hợp của bài toán con. Ta hãy bắt đầu bằng việc định nghĩa các tập hợp: Sij = {ak ∈S : fi ≤ sk < fk ≤ sj } Sao cho Sij là một tập con của các hoạt động trong tập S mà có thể bắt đầu sau khi hoạt động ai kết thúc và kết thúc trước hoạt động aj bắt đầu. Thật ra, Sij chứa tất cả các hoạt động tương thích với ai và aj và cũng tương thích với tất cả các hoạt động hoàn thành không trễ hơn ai và tất cả các hoạt động bắt đầu không sớm hơn aj bắt đầu. Để thuận tiện trong việc biểu diễn bài toán, không mất tính tổng quát, ta thêm vào những hoạt động giả sử a0 và an+1 với qui ước rằng f0 = 0 và Sn+1 = ∞. Sau đó S = S0..n+1, và phạm vi của i và j được cho bởi 0 ≤ i, j ≤n+1. Ta có thể giới hạn hơn nữa phạm vi của i và j như sau. Giả sử rằng các hoạt động đó được sắp xếp theo một thứ tự tăng dần của thời điểm kết thúc: f0 ≤ f1 ≤ f2 ≤...≤fn ≤ fn+1. (16.1) Ta dễ dàng thấy rằng Sij = Ø với i ≥ j. Tại sao? Giả sử rằng tồn tại hoạt động ak ∈ Sij sao cho i ≥ j, vì vậy ai kế tiếp aj trong thứ tự sắp xếp. Sau đó ta sẽ có fi ≤ sk < fk ≤ sj < fj. Vì vậy, fi < fj, điều này mâu thuẫn với giả thiết rằng ai kế tiếp aj trong thứ tự sắp xếp. Ta có thể kết luận rằng, ta sắp xếp các hoạt động theo thứ tự tăng dần của thời điểm kết thúc, phạm vi của các bài toán con của ta là chọn một tập con cực đại của
6. lam http://www.ebook.edu.vn Trang 5 các hoạt động tương thích lẫn nhau từ Sij với 0 ≤ i < j ≤ n+1, biết rằng tất cả các Sij khác là đều rỗng. Để nhận ra được cấu trúc con của bài toán chọn hoạt động, ta xét một bài toán con khác rỗng Sij, và giả sử rằng một giải pháp đối với Sij tồn tại một hoạt động ak, mà fi ≤ sk < fk ≤ sj. Việc chọn hoạt động ak sẽ phát sinh ra hai bài toán con, Sik (những hoạt động mà bắt đầu sau khi ai kết thúc và kết thúc trước khi ak bắt đầu) và Skj (những hoạt động mà bắt đầu sau khi ak kết thúc và kết thúc trước khi aj bắt đầu), mỗi hoạt đó bao gồm một tập con của các hoạt động trong Sij. Giải pháp của ta đối với bài toán Sij là tổng hợp hai giải pháp cho hai bài toán con Sik và Skj, ứng với hoạt động ak. Vì vậy số các hoạt động trong giải pháp đối với Sij của ta là kích thước của bài toán Sik, cộng với kích thước của bài toán Skj, cộng với một (cho ak). Cấu trúc con tối ưu của bài toán này là như sau. Nếu Aij là giải pháp tối ưu cho bài toán có chứa các hoạt động ak. Thì giải pháp Aik cho Sik và Akj cho Skj được sử dụng trong Sij cũng tối ưu. Lý luận cắt và dán thông thường áp dụng. Thật vậy, nếu tồn tại một giải pháp A'ik cho Sik chứa nhiều hoạt động hơn Aik, ta có thể thay Aik bởi A'ik trong Aij, ta sẽ tìm ra một giải pháp khác đối với Sij có nhiều hoạt động hơn Aij. Điều này trái với giả thiết ta co rằng Aij là giải pháp tối ưu đối với Sij. Tương tự, nếu ta có một giải pháp A'kj đối với Skj với nhiều hoạt động hơn Akj, ta có thể thay thế Akj bởi A'kj để đưa ra một giải pháp cho Sij với nhiều hoạt động hơn Aij. Bây giờ ta sử dụng cấu trúc con tối ưu để chỉ ra rằng có thể xây dựng một giải pháp tối ưu cho bài toán từ những giải pháp tối ưu đối với những bài toán con. Ta đã thấy rằng giải pháp nào đó cho bài toán con khác rỗng Sij có chứa hoạt động ak, và giải pháp tối ưu bất kỳ đó chứa trong nó những giải pháp tối ưu đối với bài toán con Sik và Skj. Vì vậy, ta có thể xây dựng một tập con cực đại của những hoạt động tương thích lẫn nhau trong Sij bởi việc phân chia bài toán thành hai bài toán con (tìm tập con lớn nhất của các hoạt động tương thích lẫn nhau trong Sik và Skj ), tìm ra những tập con lớn nhất Aik và Akj của những hoạt động tương thích lẫn nhau đối với những bài toán con này, và thành lập tập con lớn nhất Aij của các hoạt động tương thích lẫn nhau như: Aij = Aik U {ak } U Akj (16.2)
7. lam http://www.ebook.edu.vn Trang 6 Giải pháp tối ưu cho bài toán chính là giải pháp cho S0,n+1. 1.3. Giải pháp đệ quy Bước thứ hai trong việc phát triển giải pháp quy hoạch động là định nghĩa một cách đệ quy giá trị của giải pháp tối ưu. Đối với những bài toán chọn hoạt động, gọi c[i,j] là số các hoạt động trong tập con lớn nhất chứa các hoạt động tương thích lẫn nhau trong Sij. Ta có c[i,j] = 0 khi Sij = Ø, hoặc c[i,j] = 0 khi i ≥ j. Xét một tập con Sij khác rỗng. Như ta đã thấy, nếu ak được sử dụng trong tập con lớn nhất các hoạt động tương thích lẫn nhau của Sij, Ta cũng sử dụng các tập con lớn nhất của các hoạt động tương thích lẫn nhau cho các bài toán con Sik và Skj. Dùng công thức (16.2), ta có công thức c[i,j] = c[i,k] + c[k,j] + 1. Công thức đệ quy này cho thấy rằng ta biết giá trị của k, mà ta không biết. Ta có i-j-1 giá trị có thể chấp nhận cho k, cụ thể là k = i+1,..., j-1. Vì tập con lớn nhất của Sij phải dùng một trong những giá trị này của k, ta phải kiểm tra tất cả chúng để tìm ra giá trị tốt nhất. Vì vậy công thức đệ quy đầy đủ của c[i,j] trở thành: { } ⎪ ⎩ ⎪ ⎨ ⎧ ≠ + + = = < < φ φ ij j k i ij S if j k c k i c S if j i c 1 ] , [ ] , [ max 0 ] , [ (16.3) 1.4. Biến đổi một giải pháp quy hoạch động thành một giải pháp tham lam Tại điểm này, nó sẽ là một bài tập dễ hiểu lập một cái bảng, từ dưới lên, thuật toán quy hoạch động dựa trên công thức (16.3). Thực ra, bài tập 16.1-1 yêu cầu bạn thực hiện điều này. Có hai sự xác định then chốt, tuy nhiên, điều này cho phép ta đơn giản hoá giải pháp của ta. Định lý 16.1 Xét một bài toán con khác rỗng Sij,và nếu am là một hoạt động trong Sij có thời điểm kết thúc sớm nhất: fm = min{fk : ak ∈ Sij}. Thì: 1. Hoạt động am được sử dụng trong một tập con lớn nhất nào đó của các hoạt động tương thích lẫn nhau của Sij.
8. lam http://www.ebook.edu.vn Trang 7 2. Bài toán con Sim là rỗng, do đó nếu chọn am thì chỉ còn duy nhất bài toán con khác rỗng Smj. Chứng minh Ta chứng minh phần hai trước vì đơn giản hơn. Giả sử rằng Sim là khác rỗng, do đó có một hoạt động ak nào đó sao cho fi ≤ sk < fk ≤ sm < fm . Mà ak cũng nằm trong Sij và nó có thời gian kết thúc sớm hơn am, điều này mâu thuẫn với việc chọn am Ta kết luận rằng Sim là rỗng. Để chứng minh phần thứ nhất, ta giả sử rằng, Aij là một tập con lớn nhất của các hoạt động tương thích lẫn nhau của Sij, và ta sắp xếp các hoạt động của Aij theo thứ tự tăng dần của thời điểm kết thúc. Gọi ak là hoạt động đầu tiên trong Aij. Nếu ak = am, thì ta đã chứng minh được, chỉ ra rằng am được sử dụng trong tập con lớn nhất nào đó của các hoạt động tương thích lẫn nhau của Sij. Nếu ak ≠ am, ta xây dựng tập con A’ij = Aij – {ak} ∪ {am}. các hoạt động trong A’ij thì tách rời nhau, các hoạt động trong Aij thì, ak là hoạt động kết thúc đầu tiên trong Aij, và fm ≤ fk. Chú ý rằng A’ij có số hoạt động giống như Aij, ta thấy rằng A’ij cũng là một tập con lớn nhất của các hoạt động tương thích lẫn nhau của Sij mà có chứa am. Tại sao định lý 16.1 có giá trị? Quay về phần 15.3 cấu trúc con tối ưu làm thay đổi cách nhiều bài toán được sử dụng trong giải pháp tối ưu để đến bài toán gốc và trong nhiều cách chọn ta có xác định những bài toán con để sử dụng. Trong giải pháp quy hoạch động, hai bài toán con được sử dụng trong giải pháp tối ưu, và có j-i-1 cách chọn khi giải quyết bài toán con Sij. Định lý 16.1 giảm cả số lượng lớn đáng kể này: chỉ duy nhất một bài toán con được sử dụng trong giải pháp tối ưu (một bài toán con khác thì là rỗng), và khi giải quyết bài toán con Sij, ta cần xem duy nhất một cách chọn: một cách với thời gian kết thúc sớm nhất trong Sij. May mắn thay, ta có thể dễ dàng xác định đây là hoạt động nào. Cùng với việc giảm số các bài toán con và số cách chọn, định lý 16.1 cung cấp một lợi ích khác: ta có thể giải quyết mỗi bài toán con theo kiểu từ trên xuống (top-down), hơn là kiểu từ dưới lên (bottom-up) sử dụng điển hình trong quy hoạch động. Để giải quyết bài toán con Sij, ta chọn hoạt động am trong Sij với thời gian kết thúc sớm nhất và thêm vào
9. lam http://www.ebook.edu.vn Trang 8 giải pháp này một tập của các hoạt động dùng trong giải pháp tối ưu đối với bài toán con Sij. Bởi vì ta biết rằng, có chọn am, ta sẽ được sử dụng một giải pháp nào đó cho Smj trong giải pháp tối ưu của ta cho Sij, ta không cần giải quyết Smj trước việc giải quyết Sij. Để giải quyết Sij, ta có thể chọn am trước tiên như hoạt động trong Sij với thời điểm kết thúc sớm nhất và sau đó giải quyết Smj. Cũng chú ý rằng có một mô hình đối với những bài toán con mà ta giải quyết. Bài toán ban đầu của ta là S =S0,n+1. Giả sử rằng chọn am1 là hoạt động trong S0,n+1 với thời điểm kết thúc sớm nhất. (Từ việc sắp xếp các hoạt động theo thứ tự thời điểm kết thúc tăng dần và f0 = 0, ta phải có m1 = 1.) Bài toán con tiếp theo là Sm1,n+1. Bây giờ giả sử rằng ta chọn am2 là hoạt động trong Sm1,n+1 với thời điểm kết thúc sớm nhất. (Nó không cần thiết trong trường hợp m2 = 2). Bài toán con tiếp theo là Sm2,n+1. Tiếp theo, ta thấy rằng mỗi bài toán con sẽ có dạng S i m ,n+1 cho số hoạt động mi nào đó. Tóm lại, mỗi bài toán con gồm có các hoạt động cuối cùng để kết thúc, và một số các hoạt động biến đổi từ bài toán con này đến bài toán con khác. Cũng có một mô hình đối với các hoạt động mà ta chọn. Bởi vì ta luôn luôn chọn hoạt động với thời điểm kết thúc sớm nhất trong S i m ,n+1, thời điểm kết thúc của các hoạt động được chọn qua tất cả các bài toán con sẽ làm gia tăng nghiêm trọng thời gian. Tuy nhiên, ta có thể xem như mỗi hoạt động là một toàn diện, trong việc sắp xếp tăng dần của thời điểm kết thúc. Hoạt động am mà ta chọn khi giải quyết một bài toán con thì luôn là một hoạt động với thời điểm kết thúc sớm nhất mà có thể được lập lịch hợp lý. Hoạt động được chọn như vậy là chọn lựa “tham lam” trong hướng này, qua trực giác, nó để lại nhiều cơ hội có thể cho những hoạt động còn lại để lập lịch. Đó là, lựa chọn tham lam là một cách mà cực đại hoá số lượng đáng kể của thời gian còn lại chưa lập lịch. 1.5. Giải pháp tham lam đệ quy Bây giờ ta đã thấy cách tổ chức hiệu quả giải pháp quy hoạch động, và cách xử lý nó theo phương pháp từ trên xuống, ta xem một giải thuật mà nó hoạt động một cách thuần tuý trong thuật toán tham lam, kiểu từ trên xuống. Dễ hiểu, một giải thuật đệ quy như là thủ tục RECURSIVE-ACTIVITY-SELECTOR. Nó lấy thời điểm bắt đầu và kết thúc của
10. lam http://www.ebook.edu.vn Trang 9 các hoạt động, được trình bày như các mảng s và f, xem như những chỉ số bắt đầu i và n mà nó định nghĩa bài toán con Si,n+1 nó là để giải quyết. (Tham số n chỉ hoạt động thực tế cuối cùng an trong bài toán con và không chỉ hoạt động không có thật an+1 mà nó cũng ở trong bài toán con). Nó trả về một tập lớn nhất của các hoạt động tương thích lẫn nhau trong Si,n+1 .Ta cho rằng n hoạt động đưa vào được sắp xếp theo thời điểm kết thúc tăng dần, theo công thức (16.1). nếu không, ta có thể sắp xếp chúng theo thứ tự này với độ phức tạp O(nlgn), phá vỡ sự ràng buộc một cách tuỳ tiện. Lời gọi ban đầu là RECURSIVE-ACTIVITY-SELECTOR(s,f, 0, n). RECURSIVE-ACTIVITY-SELECTOR(s,f,i,n) 1 mÅi+1 2 while m≤ n and sm<fi ¾Tìm hoạt động đầu tiên trong Si,n+1 3 do m Åm+1 4 if m<n 5 Then return {am}∪ RECURSIVE-ACTIVITY-SELECTOR(s,f,m,n) 6 else return ∅ Minh hoạ 16.1 chỉ ra sự thực hiện của thuật toán. Trong việc gọi đệ quy của RECURSIVE-ACTIVITY-SELECTOR(s,f,i,n), vòng lặp while của dòng 2-3 tìm kiếm hoạt động đầu tiên trong vòng lặp ví dụ ai+1, ai+2, …, an, cho đến khi nó tím thấy hoạt động đầu tiên am mà tương thích với ai, một hoạt động như vậy có Sm ≥ fi. Nếu vòng lặp giới hạn bởi nó tìm thấy một hoạt động như vậy giải thuật quay lại dòng 5 sự kết hợp của {am} và tập con cực đại của Sm,n+1 quay lại bởi việc gọi đệ quy RECURSIVE-ACTIVITY- SELECTOR(s,f,m,n). Một cách lựa chọn, vòng lặp có thể giới hạn bởi m>n, trong trường hợp này ta đã có kiểm tra tất cả các hoạt động mà không tìm thấy một hoạt động nào tương thích với ai. Trong trường hợp này Si,n+1= ∅, vì vậy giải thuật sẽ trả về ∅ ở dòng 6. 1.6. Giải pháp tham lam lặp Ta dễ dàng chuyển đổi giải thuật đệ quy thành giải thuật lặp. Giải thuật RECURSIVE- ACTIVITY-SELECTOR thì hầu như “đệ qui yếu“ (xem bài toán 7-4): nó kết thúc với lời gọi đệ quy chính nó theo một sự thực hiện kết hợp. Dễ dàng để thay đổi một giải thuật đệ
11. lam http://www.ebook.edu.vn Trang 10 qui yếu thành giải thuật lặp, thật ra, một số trình biên dịch cho ngôn ngữ lập trình bất kỳ thực hiện công việc này một cách tự động. Như đã được viết, RECURSIVE-ACTIVITY- SELECTOR thực hiện cho các bài toán con Si,n+1…, những bài toán con mà có các hoạt động kết thúc cuối cùng. Giải thuật GREEDY-ACTIVITY-SELECTOR là một phiên bản lặp của giải thuật RECURSIVE-ACTIVITY-SELECTOR, ở đây cũng giả sử các hoạt động đầu vào được sắp xếp theo thời điểm kết thúc tăng dần. Nó tập hợp các hoạt động được chọn vào một tập A và quay lại tập này khi nó đã được thực hiện xong.
12. lam http://www.ebook.edu.vn Trang 11 Hình 16.1 Sự thực hiện của RECURSIVE-ACTIVITY-SELECTOR trong hoạt động 11 được cho sớm hơn. Các hoạt động đã được xem trong mỗi lời đệ quy xuất hiện giữa những đường kẻ ngang. Hoạt động không có thật a0 kết thúc tại thời điểm 0, và trong lời gọi ban đầu RECURSIVE-ACTIVITY-SELECTOR (s,f,0,11), hoạt động a1 được chọn. Trong mỗi lời gọi đệ quy, những hoạt động mà đã được chọn được tô đen, và các hoạt động tmàu tô trắng đang được xem xét. Nếu thời gian bắt đầu của một hoạt động xảy ra trước thời gian kêt thúc của hoạt động mới được chọn (mũi tên giữa chúng chỉ sang trái), nó bị loại. Trái lại (mũi tên chỉ trực tiếp hay qua phải), nó được chọn. Lời gọi đệ quy cuối cùng, RECURSIVE-ACTIVITY-SELECTOR (s, f, 0, 11) trả về Ø. Tập kết quả của các hoạt động được chọn là{a1, a4, a8, a11}. GREEDY-ACTIVITY-SELECTOR(s,f) 1 n ← length[s] 2 A ← {a1} 3 i ← 1 4 for m ← 2 to n 5 do if sm≥fi 6 Then A ← A ∪ {am} 7 i ← m 8 Return A Giải thuật thực hiện như sau. Biến i đánh số các phần tử thêm vào A gần nhất, tương ứng đối với hoạt động ai trong phiên bản đệ quy. Giả sử các hoạt động được sắp xếp theo thứ tự tăng dần của thời điểm kết thúc, fi luôn là thời điểm kết thúc lớn nhất của hoạt động nào đó trong A. Điều đó là: fi = max{fk : ak ∈A} (16.4) Dòng 2-3 chọn hoạt động ai, ban đầu A chỉ chứa chỉ một hoạt động này, và khởi đầu i là chỉ số hoạt động này. Vòng lặp for ở các dòng 4-7 tìm thấy hoạt động kết thúc sớm nhất trong Si,n+1. Vòng lặp xem xét mỗi hoạt động am trong vòng lặp và thêm am vào A
13. lam http://www.ebook.edu.vn Trang 12 nếu nó tương thích với tất cả các hoạt động được chọn trước đó. Một hoạt động như vậy là hoạt động kết thúc sớm nhất trong Si,n+1. Để thấy nếu hoạt động am là tương thích với mỗi hoạt động hiện tại trong A, nó đáp ứng bởi phương trình (16.4) để kiểm tra (dòng 5) rằng thời điểm bắt đầu của nó Sm thì không sớm hơn thời điểm kết thúc fi của hoạt động thêm vào A gần đây nhất. nếu hoạt động am tương thích, thì các dòng 6-7 thêm hoạt động am vào A và thiết lập i đến m. Tập A quay lại bởi lời gọi GREEDY-ACTIVITY- SELECTOR(s,f) là chính xác tập được quay lại bởi lời gọi RECURSIVE-ACTIVITY- SELECTOR(s,f, 0, n ). Giống như phiên bản đệ quy, GREEDY-ACTIVITY-SELECTOR lập lịch một tập của n hoạt động với độ phức tạp là O(n) thời gian, giả sử rằng các hoạt động ban đầu đã được sắp xếp theo thời điểm kết thúc của chúng.
14. lam http://www.ebook.edu.vn Trang 13 PHẦN 2: CÁC THÀNH PHẦN CỦA CHIẾN LƯỢC THAM LAM Thuật toán tham lam có được một giải pháp tối ưu cho một bài toán bằng cách thực hiện một chuỗi các lựa chọn. Đối với mỗi quyết định chỉ ra trong thuật toán, sự lựa chọn này dường như tốt nhất tại thời điểm được chọn. Chiến lược phỏng đoán này không luôn tạo ra giải pháp tối ưu, nhưng như ta đã thấy trong bài toán chọn hoạt động, thỉnh thoảng nó giải quyết được. Phần này thảo luận một số tính chất tổng quát của phương pháp tham lam. Quy trình mà ta đã thực hiện trong phần 16.1 để phát triển thuật toán tham lam là bao hàm nhiều hơn là điển hình. Ta đi qua từng bước như sau: 1. Xác định cấu trúc bên trong tối ưu của bài toán. 2. Xây dựng một giải pháp đệ quy. 3. Chứng minh rằng tại mỗi bước của giải thuật đệ quy, lựa chọn tham lam là một trong những lựa chọn sẽ dẫn đến kết quả tối ưu. 4. Chỉ ra rằng sau mỗi lần chọn tham lam thì một trong những bài toán con sẽ rỗng. 5. Xây dựng giải thuật đệ quy cho chiến lược tham lam. 6. Biến đổi giải thuật đệ quy thành giải thuật lặp. Qua các bước này, ta đã thấy chi tiết cơ bản nguồn gốc quy hoạch động của thuật toán tham lam. Trong thực tế, tuy nhiên, ta thường tổ chức hiệu quả các bước trên khi thiết kế giải thuật tham lam. Ta phát triển cấu trúc con với một cái nhìn hướng đến thực hiện lựa chọn tham lam mà để lại một bài toán con được giải quyết một cách tối ưu. Ví dụ, trong bài toán chọn hoạt động, ta trước tiên định nghĩa bài toán con Sij, mà cả hai i và j khác nhau. Ta đã thấy rằng nếu ta luôn thực hiện lựa chọn tham lam, ta có thể giới hạn các bài toán con được thành lập bởi Si,n+1 Như một sự lựa chọn, ta có thể tạo nên cấu trúc con tối ưu với một lựa chọn tham lam có nghĩa. Điều đó là, ta có thể bỏ qua chỉ số dưới thứ hai và định nghĩa các bài toán con của công thức Si = {ak ∈S : fi ≤ Sk}. Sau đó, ta có thể chứng minh rằng một lựa chọn tham lam (hoạt động đầu tiên am để kết thúc Si ), kết hợp với một giải pháp tối ưu để đi đến tập
15. lam http://www.ebook.edu.vn Trang 14 còn lại Sm của các hoạt động tương thích, mang lại một giải pháp tối ưu đối với Si. Tổng quát hơn, ta thiết kế thuật toán tham lam theo chuỗi các bước: 1. Tìm lựa chọn sao cho bước tiếp theo chỉ việc giải quyết một bài toán con 2. Chứng minh rằng với sự lựa chọn tham lam tại mỗi bước ta luôn tìm được một giải pháp tối ưu của 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. Ta sẽ sử dụng điều này nhiều hơn nhằm xử lý trong những phần sau của chương này. Tuy nhiên, dưới mỗi thuật toán tham lam, hầu như luôn có một giải thuật quy hoạch động cồng kềnh. Có thể nói một cách như thế nào nếu một giải thuật tham lam sẽ giải quyết được một bài toán tối ưu riêng biệt? Không có cách tổng quát, nhưng chiến lược lựa chọn tham lam và cấu trúc con tối ưu là hai thành phần then chốt. Nếu ta có thể chứng minh rằng bài toán có các thuộc tính này, sau đó ta thuận lợi trong cách xây dựng một thuật toán tham lam cho nó. 2.1. Tính lựa chọn tham lam Thành phần then chốt trước tiên là tính lựa chọn tham lam: một giải pháp tôi ưu toàn cục có thể đạt được bằng cách lựa chọn tối ưu cục bộ (tham lam). Nói một cách khác, khi có nhiều sự lựa chọn thì ta lựa chọn phương án nào tốt nhất ở hiện tại trong bài toán hiện tại, mà không cần quan tâm đến kết quả các bài toán con của nó. Đây là chỗ khác nhau giữa các thuật toán tham lam và quy hoạch động. Trong quy hoạch động tại mỗi bước ta thực hiện một lựa chọn, nhưng sự lựa chọn phụ thuộc vào các giải pháp cho các bài toán con. Do đó, ta giải quyết một cách tiêu biểu các bài toán quy hoạch động theo kiểu từ dưới lên, nghĩa là lần lượt xử lý những bài toán con nhỏ hơn đến những bài toán con lớn hơn. Trong giải thuật tham lam, ta thực hiện cách chọn bất kỳ dường như tốt nhất ngay lập tức và sau đó giải quyết bài toán con xuất hiện sau khi lựa chọn được thực hiện. Lựa chọn được thực hiện bởi một thuật toán tham lam có lẽ phụ
16. lam http://www.ebook.edu.vn Trang 15 thuộc vào các lựa chọn cho đến giờ, nhưng nó không thể phụ thuộc vào những lựa chọn bất kỳ trong tương lai hay những giải pháp cho các bài toán con. Vì vậy, không giống quy hoạch động, nó giải quyết các bài toán con từ dưới lên, một chiến lược tham lam thường giải quyết theo kiểu từ trên xuống, thực hiện một lựa chọn tham lam sau một chọn lựa khác, liên tục rút gọn từng trường hợp bài toán đã cho thành một bài toán nhỏ hơn. Dĩ nhiên, ta phải chứng minh rằng một lựa chọn tham lam tại mỗi bước đưa ra một giải pháp tối ưu toàn cục, và đây là nơi cần có sự thông minh. Điển hình, như trong trường hợp của định lý 16.1, sự chứng minh kiểm tra một giải thuật tối ưu toàn cục đối với một bài toán con nào đó. Rồi nó chỉ ra rằng giải thuật có thể được sửa đổi để sử dụng lựa chọn tham lam, kết quả trong một bài toán tương tự nhưng bài toán con nhỏ hơn. Thuộc tính lựa chọn tham lam thường đạt được hiệu lực trong việc thực hiện lựa chọn của ta trong bài toán con. Ví dụ, trong bài toán chọn hoạt động, giả sử rằng ta có các hoạt động được sắp xếp sẵn theo thứ tự tăng dần của thời điểm kết thúc, ta cần kiểm tra mỗi một hoạt động. Nó thường là trường hợp mà được xử lý trước khi đưa vào hay sử dụng một cấu trúc dữ liệu thích hợp (thường một hàng đợi ưu thế), ta có thể thực hiện các lựa chọn tham lam nhanh chóng, vì vậy đưa ra một thuật toán hiệu quả. 2.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 trong nó các giải pháp tối ưu cho các bài toán con. Thuộc tính này là điểm để quyết định ta có thể giải quyết bài toán bằng phương pháp quy hoạch động cũng như tham lam được hay không. Như một ví dụ của cấu trúc con tối ưu, quay về cách ta chứng minh trong phần 16.1 rằng nếu một giải pháp tối ưu đối với bài toán con Sij có chứa một hoạt động ak, sau đó nó cũng phải chứa các giải pháp tối ưu đối với các bài toán Sik và Skj. Cấu trúc con tối ưu này được đưa ra, ta nói rằng nếu biết hoạt động nào sử dụng như ak, ta có thể xây dựng một giải pháp tối ưu đối với Sij bằng việc lựa chọn cùng với tất cả hoạt động của các giải pháp tối ưu đối với các bài toán con Sik và Skj. Dựa trên sự quan sát này của cấu trúc con tối ưu, ta có thể đưa ra công thức đệ quy (16.3) mà nó định rõ giá trị của một giải pháp tối ưu.
17. lam http://www.ebook.edu.vn Trang 16 Ta thường sử dụng thêm cấu trúc con tối ưu gần như trực tiếp, khi áp dụng nó đối với các giải thuật tham lam. Như sự chú ý ở trên, ta không cần thiết cho rằng đi đến một bài toán con bằng cách thực hiện lựa chọn tham lam trong bài toán tối ưu. Tất cả ta thật sự cần làm là cho rằng một giải pháp tối ưu đối với bài toán con, kết hợp với lựa chọn tham lam vừa được thực hiện, mang lại một giải pháp tối ưu đối với bài toán ban đầu. Sự phối hợp hoàn toàn sử dụng phương pháp quy nạp đối với các bài toán con để chứng minh rằng việc sử dụng lựa chọn tham lam tại mỗi bước tạo ra một giải pháp tối ưu. 2.3. Thuật toán tham lam mâu thuẫn với quy hoạch động Bởi vì thuộc tính cấu trúc con tối ưu được khai thác cả trong chiến lược tham lam và quy hoạch động. Một mặt ta có thể có khuynh hướng phát sinh một giải thuật quy hoạch động cho một bài toán khi chỉ một giải thuật tham lam là đủ, hoặc ta có thể lầm lẫn khi nghĩ rằng giải thuật tham lam sẽ làm việc khi thực tế lại cần một giải pháp quy hoạch động. Minh hoạ cho sự tinh tế giữa hai phương pháp, ta hãy khám phá hai biến thể của một bài toán tối ưu hoá cổ điển. Bài toán chiếc ba lô 0-1 được đưa ra như sau. Một tên trộm lấy trộm tại một cửa hiệu với n đồ vật, đồ vật thứ i có giá trị vi dollar và có trọng lượng wi pound, vi và wi là các số nguyên. Hắn ta muốn lấy một tải trọng càng có giá trị càng tốt, nhưng hắn ta chỉ mang được nhiều nhất là W pound trong chiếc ba lô cho m của mình cho vài số nguyên W. Những món hàng nào hắn ta phải lấy? (Đây được gọi là bài toán chiếc ba lô 0-1 bởi vì mỗi một món hàng hoặc là được lấy hoặc để lại; tên trộm không thể lấy một phần trong một món hàng hay lấy một món hàng nhiều hơn một lần). Trong bài toán chiếc ba lô phân số, thiết lập giống như vậy, nhưng tên trộm có thể lấy một số phần trong các món hàng; Hơn là thực hiện cách chọn lựa nhị phân (0-1) cho mỗi món hàng. Bạn có thể nghĩ mỗi một món hàng trong bài toán chiếc ba lô (0-1) giống như một thỏi vàng, trong khi đó mỗi món hàng trong bài toán chiếc ba lô phân số thì giống bụi vàng hơn. Cả hai bài toán chiếc ba lô thể hiện thuộc tính cấu trúc con tối ưu. Trong bài toán 0-1, xem như tải trọng có giá trị lớn nhất cân nặng nhiều nhất là W pouds. Nếu ta bỏ món hàng j ra khỏi tải trọng này, tải trọng còn lại phải là tải trọng có giá trị nhất cân nặng nhiều nhất
18. lam http://www.ebook.edu.vn Trang 17 là W–wj mà tên trộm có thể lấy từ n-1 món hàng ban đầu loại ra món hàng j. Trong bài toán chiếc ba lô phân số tương thích, giả sử rằng nếu ta bỏ lại trọng lượng w của một món hàng j khỏi tải trọng tối ưu, tải trọng còn lại phải là tải trọng có giá trị nhất cân nặng nhiều nhất là W-w mà tên trộm có thể lấy từ n-1 món hàng ban đầu cộng với wj-w pound của món hàng j. Mặc dù các bài toán là tương tự nhau, bài toán chiếc ba lô phân số có thể được giải quyết bằng chiến lược tham lam, nhưng ngược lại bài toán 0-1 thì không. Để giải quyết bài toán phân số, ta trước tiên tính toán đơn giá của mỗi pound vi /wi cho mỗi món hàng. Tuân theo chiến lược tham lam, tên trộm bắt đầu lấy càng nhiều càng tốt món hàng với đơn giá cao nhất. Nếu sự cung cấp của món hàng đó đã hết và hắn ta có thể mang thêm nữa, hắn ta lấy càng nhiều càng tốt như món hàng với đơn giá cao nhất tiếp theo, tiếp tục cho đến khi hắn ta không thể mang được nữa. Vì vậy, việc sắp xếp các món hàng theo đơn giá, thuật toán tham lam chạy với độ phức tạp O(nlogn) thời gian. Sự chứng minh rằng bài toán chiếc ba lô phân số có chiến lược lựa chọn tham lam được để lại cho bài tập 16.2-1. Hình 16.2: Chiến lược tham lam không thực hiện trong bài toán chiếc ba lô 0-1. (a) tên trộm phải chọn một tập con của ba món hàng mà khối lượng của chúng không vượt quá 50 pound. (b) Tập con tối ưu bao gồm món hàng 2 và 3. Giải pháp bất kỳ có món hàng 1 là không tối ưu, mặc dù món hàng 1 có đơn giá lớn nhất. (c) trong bài toán chiếc ba lô phân số, lấy các món hàng theo thứ tự sắp xếp đơn giá lớn nhất của mỗi pound của các món hàng đưa lại một giải pháp tối ưu. Để thấy rằng chiến lược tham lam này không thực hiện cho bài toán chiếc ba lô 0-1, xem trường hợp của bài toán được minh hoạ trong hình 16.2(a). Có 3 món hàng, và cái ba
19. lam http://www.ebook.edu.vn Trang 18 lô có thể chứa 50 pound. Món hàng 1 nặng 10 pound có giá tri 60 dollar. Món hàng 2 nặng 20 pound và có giá trị 100 dollar. Món hàng 3 nặng 30 pound và có giá trị 120 dollar. Vì vậy, đơn giá của món hàng 1 là 6 dollar mỗi pound, nó lớn hơn đơn giá của món hàng 2 (5 dollar mỗi pound) hay cả món hàng 3 (4 dollar mỗi pound). Chiến lược tham lam, bởi vậy, sẽ lấy món hàng 1 trước tiên. Như có thể thấy từ sự phân tích ở hình 16.2(b). Tuy nhiên, giải thuật tối ưu lấy món hàng 2 và 3, để lại 1. Hai giải thuật có khả năng mà bao gồm món hàng 1 là đều không tối ưu. Tuy nhiên, trong bài toán phân số tương ứng, chiến lược tham lam, lấy món hàng 1 trước tiên, mang lại một giải thuật tối ưu, như biểu diễn ở hình 16.2(c). Việc lấy món hàng 1 không thực hiện trong bài toán 0-1 bởi vì tên trộm không thể làm đầy ba lô của hắn đối với sức chứa, và khoảng trống hạ thấp giá trị hiệu qủa của mỗi pound của tải trọng của hắn. Trong bài toán 0-1, khi ta xem một món hàng cho vào chiếc ba lô, ta phải so sánh giải thuật đối với bài toán con trong đó món hàng được tính đến với giải thuật đối với bài toán con trong đó món hàng được tính đến trước khi ta có thể thực hiện lựa chọn. Bài toán được thành lập theo cách này làm tăng lên đối với nhiều bài toán con phủ chồng - một dấu chất lượng của quy hoạch động,và thực vậy, quy hoạch động có thể được sử dụng để giải quyết bài toán 0-1.(Xem bài tập 16.2-2)
20. lam http://www.ebook.edu.vn Trang 19 PHẦN 3: MÃ HUFFMAN Các mã Hufman là phương pháp hiệu quả và được sử dụng một cách rộng rãi trong việc nén dữ liệu, thường tiết kiệm từ 20% đến 90%, phụ thuộc vào đặc tính của tập tin được nén. Ta xem như dữ liệu đó là một chuỗi các ký tự. Giải pháp tham lam của Huffman sử dụng một bảng gồm các tần số xuất hiện của các ký tự để xây dựng nên một cách biểu diễn tối ưu mỗi ký tự dưới dạng một chuỗi nhị phân. Giả sử ta có tập tin dữ liệu gồm 100,000 ký tự mà ta muốn lưu trữ ở dạng nén. Ta nhận thấy rằng những ký tự trong tập tin đó xuất hiện với tần số được cho bởi minh hoạ 16.3. Tức là, chỉ có 6 ký tự khác nhau xuất hiện, và ký tự a xuất hiện 45,000 lần. Có rất nhiều cách để biểu diễn thông tin của một tập tin nào đó. Ta xét bài toán thiết kế mã ký tự nhị phân (hoặc gọi tắt là mã) ở khía cạnh nào đó mỗi ký tự được biểu diễn bởi một chuỗi nhị phân duy nhất. Nếu ta sử dụng mã có chiều dài cố định, ta cần 3 bit để biểu diễn 6 ký tự: a = 000, b = 001,..., f = 101. Phương pháp này yêu cầu có 300,000 bit để mã hoá toàn bộ tập tin đó. Ta có thể làm điều này tốt hơn không? Mã có chiều dài bất định có thể thực hiện tốt hơn đáng kể so với mã có chiều dài cố định, bằng cách cho những từ mã ký tự ngắn thường xuyên và những từ mã ký tự dài không thường xuyên. Minh hoạ 16.3 chỉ ra một cách mã hoá như thế; ở đây chuỗi 1 bit 0 biểu diễn a, và chuỗi 4 bit 1100 biểu diễn f. Cách mã hoá này cần: (45.1 + 13.3 + 12.3 + 16.3 + 9.4 + 5.4).1,000 = 224,000 bit để biểu diễn tập tin đó, tiết kiệm khoảng chừng 25%. Thật vậy, đây là cách mã hoá tối ưu cho tập tin này, như ta thấy. 3.1. Mã tiền tố Ở đây ta chỉ xét những mã trong đó không có từ mã nào là tiền tố của vài từ mã khác. Những mã này được gọi là mã tiền tố. Điều này có thể chỉ ra rằng việc nén dữ liệu tối ưu có thể thực hiện được bằng việc mã hoá ký tự có thể luôn luôn được hoàn thành với một mã tiền tố, vì vậy không mất tính tổng quát trong việc giới hạn sự chú ý đến mã tiền tố. Việc giải mã luôn luôn đơn giản đối với bất cứ mã ký tự nhị phận nào; ta chỉ việc ghép nối các từ mã biểu diễn mỗi ký tự của tập tin đó với nhau. Ví dụ, với mã tiền tố có
21. lam http://www.ebook.edu.vn Trang 20 độ dài bất định của minh hoạ 16.3, ta mã hoá tập tin gồm 3 ký tự abc là 0.101.100 = 0101100, những chỗ mà ta sử dụng dấu “.” biểu diễn phép ghép nối. A b c d e f Tần số (ngàn) 45 13 12 16 9 5 Từ mã có chiều dài cố định 000 001 010 011 100 101 Từ mã có chiều dài bất định 0 101 100 111 1101 1100 Minh hoạ 16.3 Bài toán mã hoá ký tự. Một tập tin dữ liệu gồm 100,000 ký tự chỉ chứa các ký tự a-f, với tần số được cho trước. Nếu mỗi ký tự được chỉ định một từ mã 3 bit, tập tin đó có thể được mã hoá với 300,000 bit. Sử dụng mã có chiều dài bất định cho thấy tập tin đó có thể được mã hoá với 224,000 bit. Mã tiền tố cần thiết bởi vì chúng làm đơn giản hoá việc giải mã. Vì rằng không có từ mã nào là tiền tố của bất kỳ từ mã khác, nên từ mã bắt đầu một tập tin được mã hoá là rất rõ ràng. Ta có thể nhận biết một cách đơn giản từ mã lúc đầu, dịch nó trở lại ký tự gốc ban đầu, và lặp lại quy trình giải mã đối với phần còn lại của tập tin đã mã hoá. Ta có ví dụ, chuỗi 001011101 phân ra một cách duy nhất là 0.0.101.1101, đây là dạng giải mã đối với aabe. Quá trình giải mã cần có sự biểu diễn thích hợp cho mã tiền tố sao cho có thể dễ dàng chọn ra từ mã ban đầu. Một cây nhị phân mà các lá của nó là các ký tự cho trước quy định một cách biểu diễn như vậy. Ta diễn dịch từ mã nhị phân của một ký tự chính là đường đi từ gốc đến ký tự đó, ở đó 0 có nghĩa là “đi đến con trái” và 1 có nghĩa là “đi đến con phải”. Minh hoạ 16.4 chỉ ra các cây có 2 mã của ví dụ. Lưu ý rằng những cây này không là cây nhị phân tìm kiếm, những lá không cần xuất hiện trong thứ tự sắp xếp và những nút trong không chứa khoá ký tự.
22. lam http://www.ebook.edu.vn Trang 21 Minh hoạ 16.4: Cây tương ứng với biểu đồ mã hoá ở minh hoạ 16.3. Mỗi lá được gán nhãn là một ký tự và tần số xuất hiện của nó. Mỗi nút trong được gán nhãn là tổng của tần số các lá trên cây con của nó. (a) Cây tương ứng với mã có chiều dài cố định a = 000,..., f = 101. (b) Cây tương ứng với mã tiền tố tối ưu a = 0, b = 101,..., f= 1100. Một mã tối ưu cho một tập tin luôn luôn được biểu diễn bằng một cây nhị phân đầy đủ, trong đó mọi nút không là lá đều có 2 con (xem bài tập 16.3-1). Mã có chiều dài cố định trong ví dụ của ta là không tối ưu vì rằng cây của nó thể hiện ở minh hoạ 16.4(a) không phải là cây nhị phân đầy đủ: có những từ mã bắt đầu 10… nhưng không bắt đầu 11…Vì rằng bây giờ ta có thể hạn chế chú ý vào các cây nhị phân đầy đủ, nên có thể nói rằng nếu C là bảng chữ cái từ những ký tự được cho trước và tất cả tần số ký tự là xác định, thì cây cho một mã tiền tố tối ưu có chính xác là C lá, mỗi lá cho một ký tự của bảng chữ cái, và có đúng 1 C − nút trong (xem Bài tập B.5-3). Cho một cây T tương ứng với một mã tiền tố, dễ dàng để tính được số bit yêu cầu để mã hoá một tập tin. Với mỗi ký tự c trong bảng chữ cái C, đặt f(c) là tần số của c trong tập tin đó và đặt dT(c) là độ sâu của lá chứa ký tự c trên cây. Lưu ý rằng dT(c) cũng là chiều dài của từ mã của ký tự c. Số bit cần có để mã hoá một tập tin là như sau: B(T)= ( ) ( ) T c C f c d c ∈ ∑ (16.5) điều này ta định nghĩa là mức phí của cây T.
23. lam http://www.ebook.edu.vn Trang 22 3.2. Xây dựng mã Huffman Huffman phát minh ra giải thuật tham lam nhằm xây dựng mã tiền tố tối ưu gọi là giải thuật mã hoá Huffman. Đúng với nhận xét của ta ở phần 16.2, sự kiểm chứng về độ tin cậy đúng đắn trên thuộc tính lựa chọn tham lam và cấu trúc con tối ưu. Hơn nữa chứng minh rằng hiểu được những thuộc tính này và rồi phát triển dạng giả mã, đầu tiên ta biểu diễn dưới dạng giả mã. Làm như thế sẽ giúp làm rõ giải thuật chọn những chọn lựa tham lam như thế nào. Trong dạng giả mã sau đây, ta giả sử rằng C là một tập hợp gồm n ký tự và mỗi ký tự c∈C là phần tử với tần số xác định f[c]. Giải thuật xây dựng cây T tương ứng với mã tối ưu theo cách từ trên xuống. Nó bắt đầu với một tập gồm C lá và thực hiện một chuỗi gồm 1 C − phép “kết hợp” để tạo ra cây cuối cùng. Một hàng đợi ưu tiên nhỏ nhất Q, được lập trên khoá f, được sử dụng để nhận biết 2 đối tượng có tần số nhỏ nhất để kết hợp với nhau. Kết quả của sự kết hợp 2 phần tử đó là một phần tử mới mà tần số của nó là tổng của các tần số của 2 phần tử được kết hợp. Chẳng hạn, giải thuật Huffman được chỉ ra như ở minh hoạ 16.5. Vì rằng có 6 mẫu tự trong bảng chữ cái, kích thước chuỗi ban đầu là 6, và 5 bước kết nối được yêu cầu để xây dựng cây. Cây cuối cùng biểu diễn mã tiền tố tối ưu. Từ mã đối với mẫu tự là một chuỗi các nhãn dọc theo đường đi từ gốc đến mẫu tự đó. HUFFMAN(C) 1 n← |C| 2 Q←C 3 fori 1 ton - 1 4 do allocate a new node z 5 left[z] ←x← EXTRACT-MIN (Q) 6 right[z] ←y← EXTRACT-MIN (Q) 7 f [z] ←f [x] + f [y] 8 INSERT(Q, z) 9 return EXTRACT-MIN(Q) ▹Return the root of the tree.
24. lam http://www.ebook.edu.vn Trang 23 Minh hoạ 16.5: Các bước của giải thuật Huffman với tần số được cho trong minh hoạ 16.3 mỗi đường đi chỉ ra nội dung của chuỗi được sắp xếp theo thứ tự tăng dần của tần số. Ở mỗi bước, 2 cây với tần số thấp nhất được kết hợp với nhau. Các lá được thể hiện bởi các hình chữ nhật chứa một ký tự và tần số của nó. Những nút trong được thể hiện bởi các vòng tròn chứa tổng các tần số của các nút con của nó. Nút ngoài cùng kết nối với nút trong bởi các con của nó có nhãn là 0 nếu đó là cạnh đi đến nút con trái và 1 nếu đó là cạnh đi đến nút con phải. Từ mã cho một mẫu tự là một dãy các nhãn trên những cạnh kết nối gốc với lá biểu diễn cho mẫu tự đó. (a) Tập hợp ban đầu của n=6 nút, mỗi nút là một mẫu tự. (b)-(e) các giai đoạn trung gian. (f) Cây cuối cùng Dòng 2 khởi tạo hàng đợi ưu tiên nhỏ nhất Q với các ký tự trong C. Vòng For ở dòng 3-8 lặp lại nhiều lần động tác trích ra 2 nút x và y có tần số thấp nhất trong hàng đợi, và thay thế chúng trong hàng đợi với một nút mới z thực hiện kết hợp chúng với nhau. Tần số của z được tính là tổng của các tần số của x và y ở dòng 7. Nút z có x là nút con trái và y là nút con phải. (Thứ tự này là tuỳ ý; đổi vị trí cây con trái và phải đều mang lại một mã khác có mức hao phí tương đương). Sau n-1 phép kết hợp, nút thứ nhất trái được để lại trong hàng đợi - gốc của cây mã hoá - được trả về giá trị ở dòng 9.
25. lam http://www.ebook.edu.vn Trang 24 Phân tích thời gian chạy giải thuật Huffman cho thấy rằng Q được thực hiện như một đống nhị phân (xem Chương 6). Cho một tập hợp C gồm n ký tự, giá trị ban đầu của Q ở dòng 2 có thể được thực hiện trong O(n) thời gian dùng cho thủ tục BUILD_MIN_HEAP trong phần 6.3. Vòng For ở dòng 3-8 được thực hiện chính xác là n-1 lần, và bởi vì mỗi phép toán đống yêu cầu thời gian là O(lgn), nên vòng lặp đóng góp O(nlgn) vào thời gian chạy thuật toán. Vì vậy, tổng thời gian chạy của giải thuật Huffman trên tập hợp gồm n ký tự là O(nlgn). 3.3. Tính đúng đắn của giải thuật Huffman Để chứng minh thuật toán tham lam 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 và những tính chất cấu trúc con. Bổ đề tiếp theo chỉ ra thuộc tính lựa chọn tham lam có. a. Bổ đề 16.2 Cho C là một bảng chữ cái mà mỗi ký tự c C ∈ có tần số là f[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ó cùng chiều dài và chỉ khác duy nhất ở bit cuối cùng. Chứng minh: Ý tưởng của phần chứng minh đó là chọn một cây T biểu diễn mã tiền tố tối ưu tuỳ ý và sửa đổi nó để tạo thành một cây biểu diễn mã tiền tố tối ưu khác sao cho các ký tự x và y xuất hiện như những lá anh em ruột có chiều sâu cực đại trên một cây mới. Nếu ta có thể thực hiện điều này, thì các từ mã của chúng sẽ có cùng chiều dài và chỉ khác nhau ở bit cuối cùng. Cho a và b là hai ký tự là các lá anh em ruột có chiều sâu cực đại trong T. Không mất tính tổng quát, ta mặc nhận rằng [a] f[b] f ≤ và [x] f[y] f ≤ . Vì rằng f[x] và f[y] là hai tần số của lá thấp nhất, theo thứ tự và f[a] và f[b] là các tần số tuỳ ý, theo thứ thự, nên ta có [x] f[a] f ≤ và [y] f[b] f ≤ . Như đã có ở minh hoạ 16.6, ta tráo đổi các vị trí trong T của a và x để tạo ra một cây mới T’, và sau đó ta tráo đổi các vị trí trên câu T’ của b và y để tạo ra cây mới T”. Qua phương trình (16.5), sự khác biệt đáng kể về mức hao phí giữa T và T’ là:
26. lam http://www.ebook.edu.vn Trang 25 Minh hoạ 16.6: Hình ảnh minh hoạ bước mấu chốt trong chứng minh của Bổ đề 16.2. Trong cây tối ưu T, các lá a và b là hai lá sâu nhất và là anh em ruột với nhau. Các lá x và y là hai lá mà giải thuật Huffman kết hợp với nhau đầu tiên; chúng xuất hiện ở các vị trí tuỳ ý trên T. Các lá a và x được trao đổi để thu được cây T’. Sau đó, các lá b và y được trao đổi để thu được cây T”. Bởi vì mỗi lần trao đổi không làm tăng mức phí, kết quả cây T” cũng như cây tối ưu. bởi vì cả f[a]-f[x] và dT(a)-dT(x) là không âm. Đặc biệt hơn, f[a]-f[x] là không âm bởi vì x là lá có tần số cực tiểu và dT(a)-dT(x) là không âm bởi vì a là lá có chiều sâu cực đại trên T. Tương tự, tráo đổi a và b mà không là tăng mức hao phí, và B(T’)-B(T”) là không âm. Bởi vậy, ( ") ( ) B T B T ≤ , và vì rằng T là tối ưu, ( ) ( ") B T B T ≤ , suy ra B(T)=B(T”). Vì vậy, T” là cây tối ưu trong đó x và y xuất hiện như những lá anh em ruột có chiều sâu cực đại, mà bổ đề theo. Bổ đề 16.2 hàm ý rằng quá trình xây dựng một cây tối ưu bởi các phép kết hợp có thể, không mất tính tổng quát, bắt đầu với một lựa chọn tham lam của tiến kết hợp hai ký tự có tần số thấp nhất với nhau . Tại sao điều này là một lựa chọn tham lam? Ta có thể xem mức hao phí của phép kết hợp đơn lẻ dưới dạng tổng của các tần số của hai phần tử được kết hợp. Bài tập 16.3-3 chỉ ra rằng tổng mức hao phí các phép hợp của nó. Đối với tất cả phép kết hợp có thể ở mỗi bước, Huffman chọn ra một phép kết hợp mang giá trị nhỏ nhất. Bổ đề tiếp theo sau đây chỉ ra rằng bài toán xây dựng mã tiền tố tối ưu có tính chất cấu trúc con - tối ưu.
27. lam http://www.ebook.edu.vn Trang 26 b. Bổ đề 16.3 Cho C là một bảng chữ cái cho trước với tần số f[c] xác định với mỗi ký tự c C ∈ . Cho x và y là hai ký tự trong C với tần số nhỏ nhất. Cho C’ là bảng chữ cái 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, với f[z]=f[x]+f[y]. Cho T’ là cây bất kỳ biểu diễn mã tiền tố tối ưu của bảng chữ cái 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 chữ cái C. Chứng minh: Đầu tiên ta chỉ ra rằng giá trị B(T) của cây T có thể được thể hiện dưới dạng mức hao phí B(T’) của cây T’ bằng cách xét các mức hao phí thành phần trong phương trình (16.5). Với mỗi {x,y} c C ∈ − , ta có dT(c)=dT’(c), và do đó: f[c]dT(c)=f[c]dT’(c) Vì rằng dT(x)=dT(y)=dT’(z)+1, ta có: f[x]dT(x) + f[y]dT(y) = (f[x] + f[y])(dT’(z) + 1) = f[z]dT’(z) + (f[x] + f[y]) từ đó ta kết luận rằng: B(T) = B(T’) + f[x] + f[y] Hoặc, ta có tương đương: B(T’) = B(T) - f[x] - f[y] Bây giờ, ta chứng minh bổ đề bằng phản chứng. Giả sử rằng T biểu diễn mã tiền tố không tối ưu cho C. Thì tồn tại một cây T“ sao cho B(T“)<B(T). Không mất tính tổng quát (bởi Bổ đề 16.2), T“ có x và y là anh em ruột. Cho T’“ là cây T“ với cha mẹ chung của x và y được thay thế bởi một lá z có tần số f[z]= f[x] + f[y]. Thì: B(T’’’)=B(T’’)-f[x]-f[y] <B(T)-f[x]-f[y] = B(T’) Dẫn đến mâu thuẫn đối với giả thiết cho rằngT’ biểu diễn mã tiền tố tối ưu cho C’. Vì vậy, T phải biểu diễn mã tiền tố tối ưu cho bảng chữ cái C. c. Bổ đề 16.4 Thủ tục Huffman hình thành nên mã tiền tố tối ưu. Chứng minh từ Bổ đề 16.2 và 16.3 3.4 Cài đặt thuật toán (xem phần phụ lục)
28. lam http://www.ebook.edu.vn Trang 27 PHẦN 4: CƠ SỞ LÝ THUYẾT CỦA PHƯƠNG PHÁP THAM LAM Có một lý thuyết rất hay về giải thuật tham lam mà ta sẽ tóm tắt trong phần này. Lý thuyết này rất hữu ích trong việc xác định khi phương pháp tham lam dẫn đến những giải pháp tối ưu. Nó liên quan đến cấu trúc tổ hợp đã biết như “matroids”. Mặc dù lý thuyết này không áp dụng cho tất cả các trường hợp mà phương pháp tham lam đã áp dụng (ví dụ, không áp dụng cho bài toán lựa chọn hoạt động ở phần 16.1 hoặc bài toán mã Huffman ở phần 16.3), nó áp dụng cho nhiều trường hợp quan trọng thiết thực. Hơn nữa, lý thuyết này đang được phát triển nhanh chóng và mở rộng để áp dụng cho nhiều ứng dụng hơn nữa; hãy đọc mục lục ở cuối chương để tham khảo. 4.1. Matroid Một matroid là một cặp có thứ thự M=(S,l ) thoả mãn những điều kiện sau đây: 1. S là một tập không rỗng hữu hạn 2. l là một họ các tập con khác rỗng của S, được gọi là các tập con độc lập của S, sao cho nếu B∈l và A⊆ B thì A∈l . Ta nói rằng l là di truyền nếu nó thoả mãn tính chất này. Lưu ý rằng tập rỗng nhất thiết là một phần tử của l 3. Nếu A∈l , B∈l và A B < thì có một phần tử x A B ∈ − sao cho {x} A∪ ∈l . Ta nói rằng M thoả mãn tính chất trao đổi. Từ “matroid” là do Hassler Whitney đặt. Ông nghiên cứu về matroid ma trận, trong đó các phần tử của S là các dòng của ma trận cho trước và một tập hợp các dòng độc lập nếu chúng phụ thuộc tuyến tính theo nghĩa thông thường. Dễ dàng thấy rằng cấu trúc này định nghĩa một matroid (xem Bài tập 16.4-2). Với ví dụ khác của matroid, cho rằng matroid đồ thị MG=(SG,G) xác định dưới dạng đồ thị vô hướng G=(V,E) như sau. • Tập SG được định nghĩa là tập E, là tập các cạnh của G. • Nếu A là một tập con của E thì A G ∈l nếu và chỉ nếu A là không có chu trình. Tức là, một tập gồm các cạnh A là độc lập nếu và chỉ nếu đồ thị con GA=(V,E) hình thành nên rừng.
29. lam http://www.ebook.edu.vn Trang 28 Matroid đồ thị MG có liên quan mật thiết với bài toán tìm cây khung nhỏ nhất, sẽ được trình bày ở Chương 23. a. Định lý 16.5: Nếu G=(V,E) là đồ thị vô hướng thì MG=(SG,G) là một matroid. Chứng minh: Rõ ràng, SG =E là một tập hợp hữu hạn. Ngoài ra, G l là di truyền, vì rằng một tập con của rừng là một rừng. Nói cách khác, xoá các cạnh từ chu trình ra khỏi tập các cạnh thì không thể tạo chu trình. Do đó, ta chỉ cần chứng tỏ rằng MG thoả mãn tính chất trao đổi. Giả sử rằng GA=(V,A) và GB=(V,B) là những rừng của G và B A > . Tức là, A và B tập hợp các cạnh không tạo chu trình, và B chứa nhiều cạnh hơn A. Từ định lý B.2 suy ra rằng một rừng có k cạnh có chính xác là V k − cây. (Để chứng minh điều này bằng cách khác, bắt đầu từ V cây, mỗi cây bao gồm nhiều đỉnh và không có cạnh nào. Sau đó, mỗi cạnh được thêm vào rừng sẽ làm giảm số lượng cây là một). Do đó, rừng GA chứa V A − cây, và rừng GB chứa V B − cây. Vì rằng rừng GB có một số cây nhiều hơn rừng GA, rừng GB có chứa một cây T mà đỉnh của nó là ở hai cây khác nhau trong rừng GA. Ngoài ra, bởi vì T liên thông nên nó phải chứa cạnh (u,v) sao cho đỉnh u và v nằm ở những cây khác nhau của rừng GA. Vì rằng cạnh (u,v) có thể được thêm vào rừng GA mà không tạo chu trình. Vì vậy, MG thoả mãn tính chất trao đổi, hoàn tất việc chứng minh rằng MG là matroid. Cho một matroid M=(S,l ), ta gọi một phần tử x∉A là phần tử mở rộng của A∈l nếu x có thể được thêm vào A trong khi vẫn đảm bảo tính độc lập; Do đó, x là phần tử mở rộng của A nếu A {x} ∪ ∈l. Ví dụ, cho một matroid đồ thị MG. Nếu A là tập hợp các cạnh độc lập thì cạnh e là phần tử mở rộng của A nếu và chỉ nếu e không thuộc A và khi thêm e vào A thì không tạo chu trình. Nếu A là một tập con độc lập trong matroid M, ta nói rằng A là lớn nhất nếu không có phần tử mở rộng. Tức là, A là lớn nhất nếu nó không được chứa trong bất kỳ tập con độc lập lớn hơn của M. Tính chất sau thường hữu ích. b. Định lý 16.6: Mọi tập con độc lập lớn nhất trong matroid đều có cùng lực lượng.
30. lam http://www.ebook.edu.vn Trang 29 Chứng minh: Giả sử điều mâu thuẫn rằng A là tập con độc lập lớn nhất của M và tồn tại một tập con độc lập lớn nhất B của M. Thì tính chất trao đổi chỉ ra rằng A được mở rộng thành một tập độc lập lớn hơn A {x} ∪ với x B A ∈ − , điều này mâu thuẫn với giả thiết A là lớn nhất. Để minh hoạ định lý này, cho một matroid đồ thị MG của đồ thị liên thông, vô hướng G. Mỗi tập con độc lập lớn nhất của MG phải là một cây với 1 V − cạnh nối đến tất cả các đỉnh của G. Cây như thế được gọi là cây khung của G. Ta nói rằng một matroid M=(S,l ) là có trọng số nếu có một hàm liên quan đến trọng lượng ω nhận một trọng số hoàn toàn dương ( ) x ω đối với mỗi phần tử x S ∈ . Hàm trọng số ω mở rộng với những tập con của S bằng công thức: ( ) ( ) x A A x ω ω ∈ = ∑ với bất kỳ tập A S ⊆ . Ví dụ, nếu ta đặt ( ) e ω là độ dài của cạnh e trong matroid đồ thị MG, thì ( ) A ω là tổng độ dài của các cạnh trong tập cạnh A. 4.2. Giải thuật tham lam trên một matroid trọng số Nhiều bài toán mà cách tiếp cận tham lam đưa ra những giải pháp tối ưu có thể được trình bày rõ ràng bởi việc tìm ra tập con độc lập có trọng số lớn nhất trong matroid trọng số. Tức là, ta được cho một matroid trọng số M=(S,l ) và ta muốn tìm ra một tập A∈l độc lập sao cho ( ) A ω được cực đại hoá. Ta gọi tập con độc lập và có trọng số lớn nhất là tập con tối ưu của matroid. Bởi vì trọng số ( ) x ω của bất kỳ phần tử x S ∈ là số dương, một tập con tối ưu luôn là tập con độc lập lớn nhất. Ví dụ, trong bài toán tìm cây khung nhỏ nhất, ta có một đồ thị vô hướng, liên thông G=(V,E) và hàm tính độ dài ω sao cho ( ) e ω là độ dài của cạnh e. (Ta sử dụng đại lượng “độ dài” để chỉ trọng số của cạnh ban đầu trong đồ thị, “trọng lượng” để chỉ trọng số trong matroid). Ta cần tìm ra tập con của các cạnh mà kết nối tất cả các đỉnh với nhau và có tổng độ dài nhỏ nhất. Để xem ví dụ này như là một bài toán tìm một tập con tối ưu của matroid, cho một matroid trọng số MG với hàm trọng số ' ω , trong đó '( ) e ω = (0) ( ) e ω ω − và 0 ω thì lớn hơn độ dài tối đa của một cạnh bất kỳ. Trong matroid trọng số này, tất cả trọng số là số dương và một tập con tối ưu là một cây khung có tổng độ dài nhỏ nhất
31. lam http://www.ebook.edu.vn Trang 30 trong đồ thị ban đầu. Cụ thể hơn, mỗi tập con độc lập lớn nhất A tương ứng với một cây khung và bởi vì: 0 '( ) ( 1) ( ) A V A ω ω ω = − − Trong một tập con độc lập lớn nhất bất kỳ, một tập con độc lập đạt cực đại về '( ) A ω thì phải cực tiểu ( ) A ω . Vì vậy, một thuật toán bất kỳ có thể tìm ra một tập con tối ưu A trong matroid tuỳ ý có thể giải quyết bài toán cây khung nhỏ nhất Chương 23 đưa ra thuật toán cho bài toán cây khung nhỏ nhất, nhưng ở đây ta có một thuật toán tham lam thực hiện trên matroid trọng số bất kỳ. Giải thuật trên nhận dữ liệu vào là một matroid trọng số M=(S,l ) với một hàm trọng số dương và nó trả về một tập con tối ưu A. Trong phần giả mã, ta biểu diễn những thành phần của M bởi S[M] và [M] l và hàm trọng số bởi ω . Thuật toán là tham lam bởi vì nó xem mỗi phần tử x S ∈ lần lượt được sắp xếp theo trọng số giảm dần đều và trực tiếp cộng nó vào tập A đang được tích luỹ nếu {x} A∪ là độc lập. GREEDY(M,w) 1. A←∅ 2. Sắp xếp S[M] theo thứ tự giảm dần bởi trọng lượng w 3. for mỗi x∈S[M] lấy ra từ tập được sắp xếp giảm dần theo trọng lượng w(x) 4. do if A∪{x}∈l[M] 5. then A←A∪{x} 6. return A Những phần tử thuộc S được sắp xếp giảm dần theo trọng lượng. Nếu phần tử x được xem có thể thêm vào A trong khi vẫn duy trì sự độc lập của A, thì đúng là nó. Bằng không, x bị loại bỏ. Bởi vì tập rỗng là độc lập bởi định nghĩa về matroid và x được thêm vào A với điều kiện A ∪ {x} là độc lập, nên tập con A luôn luôn độc lập bằng phương pháp qui nạp. Vì vậy, GREEDY luôn trả về một tập con độc lập A. Như sẽ thấy dưới dây A là tập con trọng số khả dĩ lớn nhất, vì vậy A một tập con tối ưu.
32. lam http://www.ebook.edu.vn Trang 31 Thật dễ dàng để phân tích thời gian thực hiện của thuật toán tham lam. Cho n biểu diễn cho S . Giai đoạn sắp xếp mất thời gian là O(nlogn). Dòng 4 thực hiện chính xác là n lần, mỗi lần là một phần tử của S. Mỗi lần thực hiện dòng 4 yêu cầu là tập A {x} ∪ có độc lập không. Nếu mỗi lần kiểm tra như thế chiếm O(f(n)), thì một giải thuật hoàn chỉnh chạy trong thời gian O(nlgn + nf(n)) Ta chứng minh rằng GREEDY trả về một tập con tối ưu. a. Bổ đề 16.7: (Matroid có tính chất lựa chọn tham lam) Giả sử rằng M=(S,l ) là một matroid trọng số với hàm trọng số là ω và S được sắp xếp theo thứ tự giảm dần theo trọng lượng. Cho x là phần tử đầu tiên của S sao cho {x} là độc lập. Nếu x tồn tại thì tồn tại một tập con tối ưu A của S chứa x. Chứng minh: Nếu không tồn tại x như thế thì tập con độc lập duy nhất là tập rỗng. Nói cách khác, cho B là một tập con tối ưu khác rỗng bất kỳ. Giả sử x B ∉ , mặt khác ta cho A=B. Không có phần tử nào của B có trọng số lớn hơn ( ) x ω . Để thấy điều này, ta có y B ∈ dẫn đến {y} là độc lập, vì rằng B∈l và l là di truyền. Vì vậy việc chọn x đảm bảo rằng ( ) ( ) x y ω ω ≥ với bất kỳ y B ∈ . Xây dựng tập A như sau. Bắt đầu với A={x}. Do cách chọn x nên A độc lập. Áp dụng tính chất trao đổi, lặp lại việc tìm một phần tử mới của B sao cho có thể thêm vào A cho đến khi A B = trong khi vẫn giữ được tính độc lập của A. Lúc đó, A= B - {y}∪ {x} với mọi y B ∈ , và vì vậy: ( ) ( ) ( ) ( ) A B y x ω ω ω ω = − + ( ) B ω ≥ Bởi vì B là tối ưu, A cũng phải tối ưu và bởi vì x A ∈ nên bổ đề được chứng minh. Tiếp theo ta chỉ ra rằng nếu một phần tử không được lựa chọn lúc đầu thì nó không thể được lựa chọn sau đó. b. Bổ đề 16.8 Cho M=(S,l ) là một matroid bất kỳ. Nếu x, một phần tử của S, là một mở rộng của tập con độc lập A nào đó của S thì x cũng là mở rộng của tập ∅.
33. lam http://www.ebook.edu.vn Trang 32 Chứng minh: Bởi vì x là một mở rộng của A, ta có A∪ {x} là độc lập. Vì rằng l là di truyền, {x} phải là độc lập. Vì vậy, x là một mở rộng của tập ∅. c. Hệ quả 16.9 Cho M=(S,l ) là một matroid bất kỳ. Nếu x là phần tử của S sao cho x không là mở rộng của ∅ thì x không là tử mở rộng của bất kỳ tập con A độc lập nàp của S. Chứng minh: Hệ quả quả này là hoàn toàn trái ngược với Bổ đề 16.8 Hệ quả 16.9 cho rằng bất kỳ phần tử nào không được dùng ngay tức thì thì có thể không bao giờ được sử dụng. Vì vậy, GREEDY không thể gây ra lỗi bởi việc bỏ qua những phần tử ban đầu bất kỳ trong S mà không là một mở rộng của ∅, vì rằng chúng không bao giờ được sử dụng. d. Bổ đề 16.10: Matrroid có tính chất cấu trúc con tối ưu Cho x là phần tử đầu tiên của S được chọn bởi GREEDY đối với matroid M=(S,l ). Vấn đề còn lại của việc tìm ra một tập con độc lập có trọng số cực đại chứa x là tìm một tập con độc lập có trọng số cực đại của matroid có trọng số M’=(S’, ' l ), với điều kiện: • ' {y S:{x,y} } S = ∈ ∈l • ' {B S-{x}:B {x} } = ⊆ ∪ ∈ l l • Hàm trọng số đối với M’ là hàm trọng số đối với M nhưng bị giới hạn bởi S’. (ta gọi M’ rút gọn của M bởi phần tử x). Chứng minh: Nếu A là một tập con độc lập có trọng số cực đại của M chứa x, thì A’=A-{x} là một tập con độc lập của M’. Ngược lại, bất kỳ tập con độc lập A’ nào của M’ dẫn đến một tập con độc lập A=A’∪ {x} của M. Bởi vì ta có cả hai trường hợp là ( ) ( ') ( ) A A x ω ω ω = + , một giải pháp có trọng số cực đại trong M chứa x dẫn đến một giải pháp có trọng số cực đại của M’, và ngược lại. e. Định lý 16.11: (Tính đúng đắn của giải thuật tham lam trên matroid) Nếu M=(S,l ) là một matroid trọng số với hàm trọng số ω thì GREEDY(M,ω ) trả lại một tập con tối ưu.
34. lam http://www.ebook.edu.vn Trang 33 Chứng minh: Với hệ quả 16.9, bất cứ phần tử nào mà được bỏ qua lúc đầu bởi vì chúng không phải là mở rộng của ∅ không hữu dụng nên không bao giờ xét lại nữa. Mỗi lần phần tử đầu tiên x được chọn, Bổ đề 16.7 chỉ ra rằng GREEDY đúng khi thêm x vào A, vì luôn tồn tại một tập con tối ưu chứa x. Cuối cùng, Bổ đề 16.10 chỉ ra rằng bài toán còn lại là tìm ra tập con tối ưu trong matroid M’ mà là rút gọn của M bởi x. Sau khi GREEDY đặt A là {x}, tất cả các bước còn lại có thể được làm sáng tỏ như hoạt động trong matroid M’=(S’, ' l ), bởi vì B là độc lập trong M’ nếu và chỉ nếu B∪ {x} là độc lập trong M, đối với tất cả các tập B ' ∈l . Vì vậy, phép tính tiếp theo của GREEDY sẽ tìm ra tập con độc lập có trọng số lớn nhất của M’, và phép tính toàn diện của GREEDY sẽ tìm ra một tập con độc lập có trọng số cực đại của M.
35. lam http://www.ebook.edu.vn Trang 34 PHẦN 5: BÀI TOÁN LẬP LỊCH LÀM VIỆC Một bài toán thú vị mà có thể được giải quyết bằng cách dùng matroid là bài toán lập lịch làm việc tối ưu trên một bộ xử lý đơn lẻ, với điều kiện mỗi nhiệm vụ đều được giới hạn trong một thời gian nhất định, cùng với số tiền phạt phải trả nếu thời hạn kết thúc không đúng. Bài toán này trông có vẻ phức tạp nhưng nó có thể được giải quyết một cách đơn giản bằng cách dùng thuật toán tham lam. Một nhiệm vụ trong một đơn vị thời gian là một công việc, có thể xem như là một chương trình có thể được chạy trên một máy tính với yêu cầu chính xác một đơn vị thời gian để hoàn thành. Cho một tập hữu hạn S gồm các công việc, mỗi lịch đối với S là một hoán vị của S chỉ ra thứ tự thực hiện của các công việc. Công việc đầu tiên trong lịch bắt đầu tại thời điểm 0 và kết thúc tại thời điểm 1, công việc thứ hai bắt đầu tại thời điểm 1 và kết thúc tại thời điểm 2, và tiếp tục như thế. Bài toán lập lịch với thời hạn kết thúc và số tiền phạt cho một bộ xử lý đơn lẻ có dữ liệu vào như sau: • Một tập S={a1,a2,…,an} của n công việc • Một tập gồm n thời hạn kết thúc d1, d2,…,dn nguyên, sao cho mỗi di thoả 1 i d n ≤ ≤ và nhiệm vụ ai được giả sử kết thúc trước thời hạn di với i = 1..n • Một tập gồm n trọng số không âm hoặc các phạt số tiền w1, w2,…,wn sao cho ta phải chịu một số tiền phạt wi nếu nhiệm vụ ai không hoàn thành trước thời hạn di và ta không phải chịu số tiền phạt nào nếu một nhiệm vụ hoàn thành đúng với thời hạn kết thúc của nó. Ta được yêu cầu tìm ra một lịch của S sao cho giảm đến mức tối thiểu tổng số tiền phạt phải chịu do không đúng thời hạn. Giả sử có một lịch cho trước. Ta nói rằng công việc là “trễ” trong lịch này nếu nó hoàn thành sau thời hạn kết thúc. Mặt khác, công việc đó được gọi là “sớm”. Một lịch tuỳ ý có thể luôn được đưa về dưới dạng sớm-trước trong đó công-việc-sớm hoàn thành trước công-việc-trễ. Để thấy được điều này, lưu ý rằng nếu một công việc ai nào đó theo sau một công việc trễ aj, thì ta thay đổi vị trí của ai và aj và ai sẽ vẫn là sớm và aj sẽ vẫn là trễ.
36. lam http://www.ebook.edu.vn Trang 35 Tương tự ta khẳng định rằng một lịch tuỳ ý luôn được đưa về dưới dạng chuẩn trong đó những công việc sớm hoàn thành trước những công việc trễ và những công việc sớm này là được sắp xếp theo thứ tự tăng dần về thời hạn kết thúc. Để làm được điều này, ta đưa bài toán lập lịch làm việc về dạng sớm-trước. Sau đó, với điều kiện là có hai công việc sớm ai và aj hoàn thành với thời hạn tương ứng k và k+1 trong lịch sao cho di ≤ dj, ta hoán đổi vị trí của ai và aj. Vì rằng aj là công việc sớm trước khi hoán đổi, k+1≤ dj. Bởi vậy, k+1< di và vì vậy ai vẫn là công việc sớm sau khi hoán đổi. Công việc aj là trở nên sớm hơn trong lịch, vì thế nó cũng vẫn là sớm sau khi hoán đổi. Bài toán tìm một lịch tối ưu được đưa về bài toán tìm một tập A các công việc sớm trong lịch tối ưu này. Một khi A được xác định, ta có thể tạo ra một lịch làm việc bằng việc sắp xếp các phần tử của A theo thứ tự tăng dần về thời hạn, rồi liệt kê những công việc trễ (ví dụ: S-A) theo thứ tự bất kỳ, đưa ra một thứ tự chuẩn của lịch làm việc tối ưu. Ta nói rằng tập A gồm các công việc độc lập nếu tồn tại một lịch làm việc gồm những công việc này sao cho không có công việc nào là trễ. Rõ ràng, tập các công việc sớm trong một lịch làm việc là tập các công việc độc lập. Gọi l là tập của tất cả các tập công việc độc lập. Xét bài toán xác định một tập con A gồm các công việc cho trước có độc lập hay không. Với t= 0,1,2,…, n, đặt Nt(A) là số công việc có trong A mà thời hạn kết thúc là t hoặc sớm hơn. Lưu ý rằng N0(A)=0 đối với tập A bất kỳ. 5.1. Bổ đề 16.12 Với một tập A bất kỳ gồm các công việc, các mệnh đề sau là tương đương. 1. Tập A là độc lập 2. Với t=0,1,2,…, n, ta có Nt(A)≤ t 3. Nếu các công việc trong A được sắp xếp theo thứ tự tăng dần về thời hạn kết thúc thì không có công việc nào trễ. Chứng minh: Rõ ràng, nếu Nt(A) >t với t nào đó, thì không có cách nào để lập lịch làm việc mà không có một công việc trễ nào đối với A, bởi vì có nhiều hơn t công việc hoàn thành trước thời gian t. Vì vậy, (1) suy ra (2). Nếu (2) có giá trị thì (3) xảy ra: không có cách nào để “get stuck” khi việc lên lịch các công việc theo thứ tự tăng dần về thời hạn
37. lam http://www.ebook.edu.vn Trang 36 kết thúc, vì rằng (2) suy ra rằng thời hạn kết thúc lớn nhất thứ i hầu hết đều là i. Cuối cùng, (3) thông thường suy ra (1). Sử dụng tính chất 2 của Bổ đề 16.12, ta có thể dễ dàng tính toán được liệu có hay không một tập cho trước gồm các công việc là độc lập (xem 16.5-2) Bài toán tối thiểu hoá tổng số tiền phạt của những công việc trễ giống như bài toán cực đại hoá tổng số tiền phạt của những công việc sớm. Định lý sau đây đảm bảo rằng ta có thể sử dụng thuật toán tham lam để tìm ra một tập độc lập. Một tập các công việc với tối đa số tiền phạt. 5.2. Định lý 16.13 Nếu S là một tập các công việc với các thời hạn kết thúc tương ứng và l là tập của tất cả các tập độc lập thì hệ thống tương ứng (S,l ) là một matroid. Chứng minh: Mọi tập con của một tập các công việc độc lập đều là độc lập. Để chứng minh tính chất trao đổi, giả sử B và A là những tập công việc độc lập và B A > . Gọi k là giá trị t lớn nhất sao cho Nt(B)≤ Nt(A). (Ví dụ một giá trị t tồn tại vì rằng N0(B)=0). Bởi vì Nn(B)= B và Nn(A)= A , nhưng B A > , ta ắt hẳn có k<n và Nj(B)>Nj(A) đối với tất cả các j trong khoảng k+1≤ j≤ n. Vì vậy, B chứa nhiều công việc với thời hạn kết thúc k+1 hơn A. Đặt ai là một công việc trong B-A với thời hạn kết thúc là k+1. Đặt A’=A∪ {ai}. Bây giờ ta chỉ ra rằng A’ phải là độc lập bởi tính chất 2 của bổ đề 16.12. Với 0≤ t≤ k, ta có Nt(A’) = Nt(A)≤ t, vì rằng A là độc lập. Với k<t=n, ta có Nt(A’)≤ Nt(B)≤ t vì rằng B là độc lập. Vì vậy, A’ là độc lập, ta hoàn thành việc chứng minh rằng (S,l ) là một matroid. Bằng định lý 16.11, ta có thể sử dụng thuật toán tham lam để tìm ra một tập các nhiệm vụ A độc lập có trọng số cực đại. Sau đó ta có thể lập nên một làm việc tối ưu gồm các công việc trong A như là những công việc sớm của nó. Phương thức này là một thuật toán lập lịch các công việc hiệu quả với các thời hạn kết thúc và số tiền phạt đối với bộ xử lý đơn. Thời gian chạy thuật toán là O(n2 ) bằng cách sử dụng GREEDY, vì rằng có O(n) lần kiểm tra tính độc lập mà mỗi lần tốn O(n) đơn vị thời gian (xem Bài tập 15.5-2).
38. lam http://www.ebook.edu.vn Trang 37 Minh hoạ 16.7 đưa ra một ví dụ về bài toán lập lịch các công việc với các thời hạn kết thúc và số tiền phạt đối với bộ xử lý đơn. Trong ví dụ này, thuật toán tham lam chọn các công việc a1, a2, a3 và a4, sau đó loại bỏ a5 và a6, và cuối cùng nhận a7. Lịch làm việc tối ưu cuối cùng là: a2, a4, a1, a3, a7, a5, a6 có tổng số tiền phạt là w5 + w6 = 50 Công việc ai 1 2 3 4 5 6 7 di 4 2 4 3 1 4 6 wi 70 60 50 40 30 20 10 Minh hoạ 16.7: Một ví dụ của bài toán lập lịch các công việc với các thời hạn kết thúc và các số tiền phạt cho bộ xử lý đơn. Từ định lý 16.13 ta có cách sắp lịch như sau: • Sắp xếp W theo thứ tự không tăng, và thay đổi S, D tương ứng theo W. • Xét mảng B[i]=-1, i=1..n • For i=1 to n do if B[D[i]] =-1 then B[D[i]]=D[i] else for j=D[i] downto 1 do if B[j]= -1 then B[j]=D[i] exit for • Dồn các phần tử # -1 lên trước • Các ô sau ta điền các công việc trể vào • Î B là tập cần tìm.
39. lam http://www.ebook.edu.vn Trang 38 Phụ lục: CÁC BÀI TẬP TỔNG HỢP 1. Bài toán cái ba lô a. Phát biểu bài toán Có n vật, mỗi vật i, i∈{1,..,n} được đặc trưng bởi trọng lượng wi(kg) và giá trị vi(US). Có một chiếc túi xách có khả năng mang m(kg). Giả sử wi, vi, m ∈N* ∀i∈{1,..,n} Hãy chọn vật xếp vào ba lô sao cho ba lô thu được có giá trị nhất. b. Phân tích bài toán Các wi của n vật có thể được biểu diễn bằng mảng: w=(w1, w2,…,wn) Giá trị vi của n vật: v=(v1, v2,…,vn) Các vật được chọn lưu trữ trong mảng c với quy ước: c[i]=1 nếu vật i được chọn. Bài toán trở thành: { } ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ = ∀ ∈ ≤ → ∑ ∑ = = n i c m w c v c i n i i i n i i i , 1 1 , 0 max 1 1 c. Thiết kế thuật toán Thuật toán tham lam cho bài toán chọn n vật có giá trị giảm dần (theo đơn giá). Input: w=(w1, w2,…,wn) v=(v1, v2,…,vn) m=sức chứa của túi xách Output: c[1..n] đánh dấu các vật được chọn Vmax: giá trị lớn nhất của chiếc túi xách Mô tả: 1. Tính đơn giá cho các loại đồ vật. 2. Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ.
40. lam http://www.ebook.edu.vn Trang 39 3. Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép. 4. Xác định trọng luợng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa. Ví dụ minh họa: Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng: Loại đồ vật Trọng lượng Giá trị B 10 25 A 15 30 D 4 6 C 2 2 Từ bảng đã cho ta tính đơn giá cho các loại đồ vật và sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng: Loại đồ vật Trọng lượng Giá trị Đơn giá B 10 25 2.5 A 15 30 2.0 D 4 6 1.5 C 2 2 1.0 Theo đó thì thứ tự ưu tiên để chọn đồ vật là: B, A, D và cuối cùng là C. Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vât loại B, trọng lượng còn lại trong ba lô là 37 - 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của ba lô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C. Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và 1 cái loại C. Tổng trọng lượng là 3*10 + 1*4 + 1*2 = 36 và tổng giá trị là 3*25+1*6+1*2 = 83.
41. lam http://www.ebook.edu.vn Trang 40 Cài đặt chương trình: Program balo; type hang = record ten : string[10]; tluong,gtri: integer; dgia: real; end; nhan = record ten: string[10]; sluong: byte; end; t_hang = array[1..20] of hang; var sp:t_hang; tui: integer; f: text; xd: array[1..20] of nhan; n,i,j: integer; procedure init; var g: integer; t: string; tg:hang; begin write('Trong luong cua tui la '); readln(tui); write('So luong loai hang hoa<=20 '); readln(n); for i:= 1 to n do begin write('san pham thu ', i); readln(t); sp[i].ten:=t; write('co trong luong '); readln(g); sp[i].tluong:=g; write('co gia tri la '); readln(g);
42. lam http://www.ebook.edu.vn Trang 41 sp[i].gtri:=g; sp[i].dgia:=sp[i].gtri/sp[i].tluong; end; writeln('stt | ten | Tluong | Gtri'); writeln('|-||-'); for i:=1 to n do writeln(' ',i,' ',sp[i].ten,' ',sp[i].tluong,' ',sp[i].gtri); {sắp xếp sản phẩm cần lấy giảm dần theo đơn giá} for i:=1 to n-1 do for j:=i+1 to n do if (sp[i].dgia<sp[j].dgia) then begin tg:=sp[i]; sp[i]:=sp[j]; sp[j]:=tg; end; writeln('stt | ten | Tluong | Gtri | Dgia'); for i:=1 to n do writeln('',i,' ',sp[i].ten,' ',sp[i].tluong,' ',sp[i].gtri,' ', sp[i].dgia:3:2); end; procedure xacdinh; var sl, tlduoc,tltui : integer; gtduoc:real; begin i:=1; j:=1; tltui:=tui; gtduoc:=0; tlduoc:=0; while i<=n do begin writeln('So: ',i,' Spham: ',sp[i].ten,' Tluong: ', sp[i].tluong); if sp[i].tluong <= tltui then
43. lam http://www.ebook.edu.vn Trang 42 begin sl:= tltui div sp[i].tluong; tlduoc:=tlduoc+sl*sp[i].tluong; gtduoc:=gtduoc+ sl* sp[i].gtri; tltui:=tltui - sl*sp[i].tluong; xd[j].ten:=sp[i].ten; xd[j].sluong:=sl; j:=j+1; writeln(' so luong lay la: ',sl); writeln(' trong luong hien co :',tlduoc); writeln(' trong luong con lai :', tltui); readln; end else begin writeln(' so luong lay la: 0'); readln; end; i:=i+1; end; writeln(' trong luong tui la ', tui); writeln(' trong luong lay duoc la ', tlduoc); writeln(' gia tri thu duoc la ',gtduoc:3:3); i:=1; writeln(' san pham co duoc la '); while i<j do begin writeln(' san pham : ',xd[i].ten, ' co so luong: ', xd[i].sluong); i:=i+1; end; end;
44. lam http://www.ebook.edu.vn Trang 43 BEGIN init; xacdinh; readln; END. 2. Giải thuật xây dựng cây mã hóa Huffman a. Phát biểu bài toán Giả sử ta có một thông báo 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 suấ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 này thành một chuỗi các ký tự 0, 1. b. Phân tích bài toán Cho trước một tập hợp các ký tự: c1, c2, ..., cn mà xác xuất xuất hiện trong thông báo lần lượt là w1, w2, ..., wn. Ta sẽ mã hóa mỗi ký tự trong chuỗi thông báo đã cho, sao cho: • Không có ký tự nào được mã hóa thành chuỗi là tiền tố của chuỗi mã hóa ký tự khác (tính chất này được gọi là tính chất tiền tố). • Ðộ dài của bộ mã là ngắn nhất. 3. Thiết kế thuật toán Input: tập hợp các ký tự: c1, c2, ..., cn∈C và w1, w2, ..., wn. Output: mã nhị phân của thông báo C Mô tả: Bước 1: đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá. Bước 2: tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các nút. Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con là các nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theo hai nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tao ra theo cách trên. Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một cây duy nhất.
45. lam http://www.ebook.edu.vn Trang 44 Cài đặt chương trình: program huffman; uses crt; const max=255; type str=string[1]; btree=^{node; node= record info:longint; ch:str; left,right:btree; end; mang=array[0..max] of btree; maso=array[1..max] of '0'..'1'; var n:-1..max; c:maso; a:mang; freq:array[0..max] of longint; codech:array[0..max] of string[16]; f:text; procedure deletetree(var t:btree); begin if t<> nil then begin deletetree(t}.left); deletetree(t^.right); dispose(t); end; end;
46. lam http://www.ebook.edu.vn Trang 45 function extract_min(q:mang):btree; begin extract_min:=q[n]; n:=n-1; end; procedure insertq(var q:mang;z:btree); var d,g,c:-1..max; stop:boolean; i:byte; begin if q[0]=nil then q[0]:=z else begin d:=0; c:=n; stop:=false; while not(stop) do begin g:=(d+c) div 2; if (q[g]^.info>z.info) then d:=g+1 else c:=g-1; if (d>=c) then stop:=true; end; for i:=n downto c do q[i+1]:=q[i]; q[c]:=z; end; n:=n+1; end;
47. lam http://www.ebook.edu.vn Trang 46 procedure assigncode(var t:btree;k:byte); var i:byte; begin if (t^.left=nil) and (t^.right=nil) then begin write(f,t^.ch,':'); for i:=1 to k do begin write(f,c[i]); codech[ord(t^.ch[1])]:=codech[ord(t^.ch[1])]+c[i]; end; writeln(f); end else begin inc(k); c[k]:='0'; assigncode(t^.left,k); c[k]:='1'; assigncode(t^.right,k); end; end; procedure createarr; var i:byte;z:btree; begin n:=-1; for i:=0 to max do if (freq[i]<>0) then begin new(z); z^.info:=freq[i];
48. lam http://www.ebook.edu.vn Trang 47 z^.ch:=chr(i); insertq(a,z); end; end; procedure createHuffmancode; var z:btree; i:byte; begin f or i:=1 to n - 1 do begin new(z); z^.left:=EXTRACT_MIN(a); z^.right:=EXTRACT_MIN(a); z^.info:=z^.left^.info + z^.right^.info; INSERTq(a,z); end; end; procedure count; var f1:text; i:byte; st:string; begin assign(f1,'vanban.txt'); reset(f1); for i:=0 to max do freq[i]:=0; while (not eof(f1)) do begin readln(f1,st); for i:=1 to length(st) do inc(freq[ord(st[i])]); end; close(f1); end;
49. lam http://www.ebook.edu.vn Trang 48 procedure inkq1; begin assign(f,'cayhman.txt'); rewrite(f); assigncode(a[0],0); close(f) end; procedure inkq2; var f1,f2:text; st1:string; i,j:byte; st2:string[16]; begin assign(f1,'vanban.txt'); reset(f1); assign(f2,'mahoa.txt'); rewrite(f2); while (not eof(f1)) do begin read(f1,st1); for i:=1 to length(st1) do begin st2:=codech[ord(st1[i])]; for j:=1 to length(st2) do write(f2,st2[j]); end; end; close(f1); close(f2); end;
50. lam http://www.ebook.edu.vn Trang 49 BEGIN clrscr; {đếm tần suất các kí tự} count; {tạo hàng đợi cho các ký tự dựa trên tần suất dược sắp xếp không giảm dần} createarr; {xây dựng cây mã hóa Huffman} createhuffmancode; {in cây Huffman} inkq1; {in bảng mã hóa của thông báo} inkq2; write('Da xu ly xong!...'); readln; deletetree(a[0]); END. 3. Bài toán cây khung nhỏ nhất – Thuật toán Kruskal a. Phát biểu bài toán Cho đồ thị G=(V,E), trong đó: tập đỉnh V={ n v v v ,..., , 2 1 } và tập cạnh E={ m e e e ,..., , 2 1 }. Một cây khung của một đồ thị liên thông G là một đồ thị con (của G) không chứa chu trình, chứa tất cả các đỉnh của G. Một cây khung nhỏ nhất của một đồ thị liên thông có trọng số G là cây khung có tổng trọng số của các cạnh là bé nhất (trong số các cây khung của G). b. Phân tích bài toán Gọi V={ n v v v ,..., , 2 1 } la tập các đỉnh của đồ thị và E={ m e e e ,..., , 2 1 } là tập các cạnh của đồ thị G=(V,E). Tại mỗi bước ta them một cạnh có trọng số nhỏ nhất lên cây T mà không tạo thành chu trình trong T. Thuật toán dừng khi T có (n-1) cạnh.
51. lam http://www.ebook.edu.vn Trang 50 Mô tả: Giải thuật tham lam cho bài toán trên là: Bước 1: (khởi tạo) Giả sử T là một đồ thị có n đỉnh và không có cạnh nào. Bước 2: (sắp xếp) Sắp xếp thứ tự các cạnh của đồ thị G theo thứ tự tang dần. Bước 3: (them cạnh) Thêm cạnh trong danh sách các cạnh đã được sắp xếp vào cây T sao cho không tạo thành chu trình trong T (cạnh them vào giọ là chấp nhận được) Bước 4: (kết thúc) Nếu T có n-1 cạnh thì thuật toán dừng; T là cây bao trùm nhỏ nhất. Ví dụ minh họa: Xét đồ thị sau Sắp xếp các cạnh theo trọng lượng tăng dần (sử dụng 2 mảng tuyến tính A, B) ta được: i 1 2 3 4 5 6 7 8 9 A c A e a c a b c d B d C f e f b d e f Trọng lượng 1 2 2 3 3 4 5 6 6 Các cạnh không tao thành chu trình đước thêm vào cây T là: (c,d); (a,c); (e,f); (a,e); (a,b) T là cây bao trùm nhỏ nhất: c. Cài đặt chương trình program Kruskal; uses crt; const MAX = 100; fn = 'DoThi.inp'; gn = 'CKNN.out'; a 4 b a 4 b 2 5 3 c 1 c 6 3 6 e 2 f a 4 b a 4 b 2 3 c 1 c e 2 f
52. lam http://www.ebook.edu.vn Trang 51 type canh = Record x,y:byte; len:integer; end; var a:array[0..MAX] of canh; p:array[1..MAX] of byte; m:byte; {số đỉnh} n:integer; f,g:text; (* Đọc dữ liệu và sắp các cạnh tăng dần *) Procedure DocDL; var i,j:byte; k:integer; begin n:=0; assign(f,fn);reset(f); read(f,m); for i:=1 to m do for j:=i+1 to m do begin read(f,a[0].len); if a[0].len>0 then begin k:=n; while a[k].len > a[0].len do begin a[k+1]:=a[k]; dec(k); end; with a[k+1] do begin
53. lam http://www.ebook.edu.vn Trang 52 len:=a[0].len; x:=i;y:=j; end; inc(n); end; end; close(f); End; Function Dad(x:byte):byte; begin While x<>p[x] do x:=p[x]; Dad:=x; end; Function creatCycle(x,y:byte):Boolean; var i,j:byte; begin i:=Dad(x);j:=Dad(y); creatCycle:=True; If i=j then exit; creatCycle:=False; if i<j then p[j]:=i else p[i]:=j; end; Procedure CayKhung; var i,d:integer; k:byte; Begin assign(g,gn);rewrite(g); for i:=1 to m do p[i]:=i; k:=1;i:=0;d:=0; while k<m do begin