Link tải luận văn miễn phí cho ae Kết Nối
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)
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 tui 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
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 tui hoàn chỉnh tiểu luận.
Xin chân thành Thank TS. Hoàng Quang đã tận tụy giúp đỡ chúng tui hoàn thành
tiểu luận này.Thuật toán tham lam
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 hay 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
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ủaThuật toán tham lam
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)
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
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 = Ø, hay 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
i k j
ij
c i k c k j if S
if S
c i j max [ , ] [ , ] 1
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.Thuật toán tham lam
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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
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
mi ,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
mi ,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
MỤC LỤC
LỜI NÓI ĐẦU......................................................................................... 01
PHẦN 1: BÀI TOÁN CHỌN HOẠT ĐỘNG........................................ 03
1.2.Giới thiệu bài toán ....................................................................................... 03
1.2. Cấu trúc con tối ưu của bài toán chọn hoạt động........................................ 04
1.3. Giải pháp đệ quy ......................................................................................... 06
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 .... 06
1.5. Giải pháp tham lam đệ quy ......................................................................... 08
1.6. Giải pháp tham lam lặp ............................................................................... 09
PHẦN 2: CÁC THÀNH PHẦN CỦA CHIẾN LƯỢC THAM LAM . 13
2.1. Tính lựa chọn tham lam .............................................................................. 14
2.2. Cấu trúc con tối ưu ...................................................................................... 15
2.3. Thuật toán tham lam mâu thuẫn với quy hoạch động................................. 16
PHẦN 3: MÃ HUFFMAN..................................................................... 19
3.1. Mã tiền tố..................................................................................................... 19
3.2. Xây dựng mã Huffman................................................................................ 22
3.3. Tính đúng đắn của giải thuật Huffman ....................................................... 24
PHẦN 4: CƠ SỞ LÝ THUYẾT CỦA PHƯƠNG PHÁP
THAM LAM ........................................................................ 27
4.1. Matroid ....................................................................................................... 27
4.2. Giải thuật tham lam trên một matroid trọng số........................................... 29
PHẦN 5: BÀI TOÁN LẬP LỊCH LÀM VIỆC..................................... 34
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
Phụ lục: CÁC BÀI TẬP TỔNG HỢP................................................... 38
1. Bài toán cái ba lô............................................................................................ 38
2. Giải thuật xây dựng cây mã hóa Huffman ..................................................... 43
3. Bài toán cây khung nhỏ nhất – Thuật toán Kruskal....................................... 49
4. Bài toán cây khung nhỏ nhất – Thuật toán Prim............................................ 53
CÁC CHÚ Ý TRONG ĐỀ TÀI.............................................................. 58
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
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)
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 tui 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
You must be registered for see links
Trang 2chắ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 tui hoàn chỉnh tiểu luận.
Xin chân thành Thank TS. Hoàng Quang đã tận tụy giúp đỡ chúng tui hoàn thành
tiểu luận này.Thuật toán tham lam
You must be registered for see links
Trang 3PHẦ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 hay 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
You must be registered for see links
Trang 4nà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ủaThuật toán tham lam
You must be registered for see links
Trang 5cá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)
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
You must be registered for see links
Trang 6Giả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 = Ø, hay 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
i k j
ij
c i k c k j if S
if S
c i j max [ , ] [ , ] 1
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.Thuật toán tham lam
You must be registered for see links
Trang 72. 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
You must be registered for see links
Trang 8giả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
mi ,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
mi ,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
MỤC LỤC
LỜI NÓI ĐẦU......................................................................................... 01
PHẦN 1: BÀI TOÁN CHỌN HOẠT ĐỘNG........................................ 03
1.2.Giới thiệu bài toán ....................................................................................... 03
1.2. Cấu trúc con tối ưu của bài toán chọn hoạt động........................................ 04
1.3. Giải pháp đệ quy ......................................................................................... 06
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 .... 06
1.5. Giải pháp tham lam đệ quy ......................................................................... 08
1.6. Giải pháp tham lam lặp ............................................................................... 09
PHẦN 2: CÁC THÀNH PHẦN CỦA CHIẾN LƯỢC THAM LAM . 13
2.1. Tính lựa chọn tham lam .............................................................................. 14
2.2. Cấu trúc con tối ưu ...................................................................................... 15
2.3. Thuật toán tham lam mâu thuẫn với quy hoạch động................................. 16
PHẦN 3: MÃ HUFFMAN..................................................................... 19
3.1. Mã tiền tố..................................................................................................... 19
3.2. Xây dựng mã Huffman................................................................................ 22
3.3. Tính đúng đắn của giải thuật Huffman ....................................................... 24
PHẦN 4: CƠ SỞ LÝ THUYẾT CỦA PHƯƠNG PHÁP
THAM LAM ........................................................................ 27
4.1. Matroid ....................................................................................................... 27
4.2. Giải thuật tham lam trên một matroid trọng số........................................... 29
PHẦN 5: BÀI TOÁN LẬP LỊCH LÀM VIỆC..................................... 34
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiThuật toán tham lam
You must be registered for see links
Trang 60Phụ lục: CÁC BÀI TẬP TỔNG HỢP................................................... 38
1. Bài toán cái ba lô............................................................................................ 38
2. Giải thuật xây dựng cây mã hóa Huffman ..................................................... 43
3. Bài toán cây khung nhỏ nhất – Thuật toán Kruskal....................................... 49
4. Bài toán cây khung nhỏ nhất – Thuật toán Prim............................................ 53
CÁC CHÚ Ý TRONG ĐỀ TÀI.............................................................. 58
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links