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
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.
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
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
61 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 3411 | Lượt tải: 5
Bạn đang xem trước 20 trang tài liệu 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), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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ự.
Thuật toán tham lam
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 1C − 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.
Thuật toán tham lam
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 1C − 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.
Thuật toán tham lam
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.
Thuật toán tham lam
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à:
Thuật toán tham lam
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.
Thuật toán tham lam
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)
Thuật toán tham lam
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.
Thuật toán tham lam
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, Gl 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.
Thuật toán tham lam
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 1V − 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
Thuật toán tham lam
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.
Thuật toán tham lam
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 ∅ .
Thuật toán tham lam
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.
Thuật toán tham lam
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.
Thuật toán tham lam
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 id 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ễ.
Thuật toán tham lam
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
Thuật toán tham lam
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).
Thuật toán tham lam
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.
Thuật toán tham lam
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:
{ }⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=∀∈
≤
→
∑
∑
=
=
nic
mwc
vc
i
n
i
ii
n
i
ii
,11,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ỏ.
Thuật toán tham lam
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.
Thuật toán tham lam
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);
Thuật toán tham lam
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
Thuật toán tham lam
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;
Thuật toán tham lam
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.
Thuật toán tham lam
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;
Thuật toán tham lam
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;
Thuật toán tham lam
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];
Thuật toán tham lam
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;
Thuật toán tham lam
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;
Thuật toán tham lam
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={ nvvv ,...,, 21 } và tập cạnh
E={ meee ,...,, 21 }.
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={ nvvv ,...,, 21 } la tập các đỉnh của đồ thị và E={ meee ,...,, 21 } 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.
Thuật toán tham lam
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
2 5
3 c 1 c
6 3 6
e 2 f
a 4 b
2
3 c 1 c
e 2 f
Thuật toán tham lam
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
Thuật toán tham lam
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 xp[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
Thuật toán tham lam
Trang 53
inc(i);
with a[i] do
if not creatCycle(x,y) then
begin
writeln(g,'(',x,',',y,')');
d:=d+len;inc(k);
end;
end;
writeln(g,'Tong chieu dai la :',d);
close(g);
End;
BEGIN
clrscr;
DocDL;
CayKhung;
readln;
END.
4. Bài toán cây khung nhỏ nhất – Thuật toán Prim
a. Phát biểu bài toán
Cho đồ thị G=(V,E), trong đó: tập đỉnh V={ nvvv ,...,, 21 } và tập cạnh
E={ meee ,...,, 21 }.
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
Chúng ta minh họa bài toán bằng cách sử dụng ‘ma trận trọng lượng” w=(wij)nxn, trong
đó:
Thuật toán tham lam
Trang 54
Evv
Evv
ji
if
if
if
vvw
w
ji
ji
ji
ij
∈
∉
=
⎪⎩
⎪⎨
⎧
∞+=
),(
),(
),(
0
Thuật toán xây dựng cây T bằng cách thêm liên tiếp các cạnh có trọng lượng nhỏ
nhất với một đỉnh trong cây T đang hình thành và một đỉnh ngoài T sao cho cạnh thêm
vào không tạo thành chu trình trong T, quá trình thêm cạnh kết thúc khi không còn đỉnh
ngoài T, cây T nhận được là cây bao trùm tối thiểu.
Mô tả:
Tổng quát, ta có được thuật toán như sau:
Bước 1: Giả sử T có một đỉnh v1 và không có cạnh.
Bước 2: Nếu T có n đỉnh thì dừng; T là cây bao trùm tối thiểu.
Bước 3: Thêm cạnh (u,v) có trọng số nhỏ nhất vào T sao cho u∈T và v∉T.
Chuyển sang bước 2.
Ví dụ minh họa:
Xét đồ thị sau
Với đỉnh xuất phát v1, ta có các cạnh được lần lượt thêm vào cây T theo thứ tự là:
(v1,v5), (v1,v4), (v4,v2), (v2,v3), (v2,v5)
Và ta thu được cây T như sau:
v1
4 2
v4 9 v5
3 6 5 7
v2 2 v6 v3
1
v1
4 2
v4 v5
3
v2 2 v6 v3
1
Thuật toán tham lam
Trang 55
Cài đặt chương trình
Program Prim
const MAX =100;
fi ='input.txt';
fo ='output.txt';
type canh =record
u,v:integer;
end;
var C :array[1..MAX,1..MAX]of integer;
L,Pre :array[1..MAX]of integer;
T :array[1..MAX-1]of canh;
X,Y :array[1..MAX]of byte;
N :integer;
dem :integer;
procedure docFile;
var f :text; i,j :integer;
begin
assign(f,fi);
reset(f);
read(f,N);
for i:=1 to N do
for j:=1 to N do read(f,C[i,j]);
close(f);
end;
procedure khoiTri;
var k :integer;
begin
{ X[u]=1 thi u thuoc X, X[u]=0 thi u khong thuoc X}
fillchar(X,Sizeof(X),0);
X[1]:=1;
{Y[v]=1 thi v thuoc Y, Y[v]=0 thi v khong thuoc Y}
Thuật toán tham lam
Trang 56
fillchar(Y,Sizeof(Y),1);
Y[1]:=0;
dem:=0; { So canh thuoc T bang 0}
for k:=2 to N do { khoi tri cho 2 mang L,Pre}
begin
L[k]:=C[1,k]; Pre[k]:=1;
end;
end;
procedure lam;
var u,v,k :integer; min :integer;
begin
while dem
begin
{ Chon canh u,v}
min:=MAXINT;
for k:=1 to N do
if (Y[k]=1)and(min>L[k]) then
begin
v:=k;
min:=L[v];
end;
u:=Pre[v];
{ Loai v ra khoi Y}
Y[v]:=0;
{ Them v vao X}
X[v]:=1;
{Them canh (u,v) vao T}
inc(dem);
T[dem].u:=u;
T[dem].v:=v;
{Cap nhat lai mang L, Pre}
Thuật toán tham lam
Trang 57
for k:=1 to N do
if (Y[k]=1)and(L[k]>C[v,k]) then
begin
L[k]:=C[v,k];
Pre[k]:=v;
end;
end;
end;
procedure ghiFileKetQua;
var f :text; k :integer;
begin
assign(f,fo);
rewrite(f);
for k:=1 to dem do writeln(f,T[k].u, #32, T[k].v);
close(f);
end;
BEGIN
docFile;
khoiTri;
lam;
ghiFileKetQua;
END.
Thuật toán tham lam
Trang 58
CÁC CHÚ Ý TRONG ĐỀ TÀI
Nhiều tài liệu về phương pháp tham lam và matroid có thể tìm đọc ở Lawler [196]
và Papadimitriou và Steiglitz [237].
Phương pháp tham lam đầu tiên xuất hiện trong tài liệu tối ưu tổ hợp trong một
bài báo năm 1971 của Edmonds [85], qua lý thuyết về matroids có trong bài báo năm
1935 của Whitney [314].
Chứng minh của ta về sự chính xác của phương pháp tham lam cho bài toán chọn
hoạt động là dựa trên cơ sở của Gavril [112]. Bài toán lập lịch công việc được nghiên
cứu trong Lawler [196], Horowitz và Sahni [157], và Brassard và Bratley [47].
Giải thuật mã hoá Huffman được phát minh năm 1952[162]; Lelewer and
Hirschberg [200] surveys
Kỹ thuật nén dữ liệu được biết đến năm 1987
Lý thuyết mở rộng về matroid trong lý thuyết tham lam được khám phá đầu tiên
bởi Korte và Lovász.
Thuật toán tham lam
Trang 59
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
Thuật toán tham lam
Trang 60
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
Các file đính kèm theo tài liệu này:
- 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).pdf