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 5