..

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THƠNG

CÀ THỊ THÙY LINH

THIẾT KẾ THUẬT TỐN DỰA TRÊN Ý
TƯỞNG CỦA PHƯƠNG PHÁP THAM LAM

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Ngun- 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THƠNG

CÀ THỊ THÙY LINH

THIẾT KẾ THUẬT TỐN DỰA TRÊN Ý
TƯỞNG CỦA PHƯƠNG PHÁP THAM LAM

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TSKH. NGUYỄN XUÂN HUY

Thái Nguyên – 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




MỤC LỤC
Trang
Trang phụ bìa ………………………………………………………………………...
Lời cảm ơn…………………………………………………………………………...i
Lời cam đoan ………………………………………………………………………ii
Mục lục …………………………………………………………………………….iii
MỞ ĐẦU ………………………………………………………………………….1
Chƣơng 1
TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM
1.1. Phƣơng pháp tham lam……………………………………………………….4
1.1.1. Ý tưởng phương pháp tham lam………………………………………………4
1.1.2. Đặc trưng của phương pháp tham lam……………………………………….6
1.1.3. Thiết kế thuật toán dựa trên ý tưởng phương pháp tham lam….……………7
1.1.3.1. Các thành phần quyết định tham lam………………………………………7
1.1.3.2. Sơ đồ chung để giải các bài toán bằng giải thuật tham lam….….…………9
1.1.3.3. Lược đồ giải thuật tham lam ……………………………………………….9
1.1.3.4. Thiết kế một thuật tốn dựa trên ý tưởng tham lam….….………………...11

1.1.3.5 Tiến trình thực hiện phương pháp tham lam…………………………...…..11
1.2. Ví dụ…………………………………………………………………………..14
1.2.1. Bài tốn lựa chọn cơng việc.………………………………………………...14
1.2.2. Xác định bài tốn……………………………………………………………14
1.2.3. Tính chất của lời giải ……………………………………………………….14
1.2.4. Các bước của thuật giải tham lam…………………………………………..15
Chƣơng 2
THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA PHƢƠNG PHÁP THAM LAM
2.1. Bài toán ngƣời du lịch ……………………………………………………….18
2.1.1. Phát biểu bài tốn …………………………………………………………..18

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




2.1.2. Phân tích thiết kế thuật tốn ……………………………………………….18
2.1.3. Xác định độ phức tạp của thuật toán ………………………………………20
2.2. Bài toán cây bao trùm ngắn nhất …………………………………………..21
2.2.1. Phát biểu bài toán …………………………………………………………..21
2.2.2. Phân tích thiết kế thuật tốn ………………………………………………..21
2.2.3. Xác định độ phức tạp của thuật tốn ……………………………………….27
2.3. Thuật tốn Dijkstra -Tìm đƣờng đi ngắn nhất trong đồ thị có trọng số…28
2.3.1. Phát biểu bài tốn …………………………………………………………..28
2.3.2. Phân tích thiết kế thuật toán ………………………………………………..28
2.3.3. Xác định độ phức tạp của thuật toán ……………………………………….33
2.4. Bài tốn cái ba lơ …………………………………………………………….33
2.4.1. Phát biểu bài tốn …………………………………………………………..33
2.4.2. Phân tích thiết kế thuật tốn ………………………………………………..33
2.4.3. Xác định độ phức tạp của thuật toán ……………………………………….35

2.5. Bài toán băng nhạc ………………………………………..…………………35
2.5.1. Phát biểu bài tốn …………………………………………………………..35
2.5.2. Phân tích thiết kế thuật toán ………………………………………………..36
2.5.3. Xác định độ phức tạp của thuật toán ……………………………………….38
2.6. Bài toán lập lịch ……………………………………………………………...38
2.6.1. Phát biểu bài tốn ………………………………………………………….38
2.6.2. Phân tích thiết kế thuật tốn ………………………………………………..38
2.6.3. Xác định độ phức tạp của thuật toán ……………………………………….42
2.7. Bài tốn mã hóa Huffman …………………………………………………..43
2.7.1. Phát biểu bài tốn …………………………………………………………..49
2.7.2. Phân tích thiết kế thuật tốn ………………………………………………..49
2.8. Phƣơng pháp tham lam trong tƣơng quan với phƣơng pháp khác ……...50
- Phƣơng pháp quy hoạch động
2.8.1. Phương pháp quy hoạch động ……………………………………………...50
2.8.2. Phương pháp tham lam trong tương quan vớiv PP quy hoạch động ……...51

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




Chƣơng 3
CÀI ĐẶT CHƢƠNG TRÌNH CHO MỘT SỐ BÀI TỐN
3.1. Bài toán ngƣời du lịch ………………………………………………………53
3.2. Bài toán cây bao trùm ngắn nhất Kruskal…………………………………56
3.3. Thuật tốn Dijkstra -Tìm đƣờng đi ngắn nhất trong đồ thị có trọng
số……………………………………………………………………..……………62
3.4. Bài tốn mã hóa huffman……………………………………………………65
KẾT LUẬN ……………………………………………………………………..69
TÀI LIỆU THAM KHẢO ……………………………………………………..70

PHỤ LỤC…………………………………………………………………………..

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




1

MỞ ĐẦU
1. Đặt vấn đề
Có nhiều phƣơng pháp đƣợc dùng để thiết kế thuật toán nhƣ: chia để trị, vét
cạn, quy hoạch động... trong đó, mỗi phƣơng pháp chỉ áp dụng cho những lớp bài
toán phù hợp. Phƣơng pháp tham lam cũng là một trong số các phƣơng pháp phổ
biến thƣờng đƣợc vận dụng trong thiết kế thuật toán.
Phƣơng pháp tham lam gợi ý chúng ta tìm một trật tự hợp lí để duyệt dữ liệu
nhằm đạt đƣợc mục tiêu một cách chắc chắn và nhanh chóng. Thơng thƣờng dữ
liệu đƣợc duyệt theo một trong hai trật tự tăng hay giảm theo một tiêu chí nào đấy.
Phƣơng pháp tham lam xây dựng các thuật toán để giải các bài toán tối ƣu
dựa trên tƣ tƣởng tối ƣu cục bộ theo một chiến lƣợc tƣ duy kiểu con ngƣời, nhằm
nhanh chóng đạt đến một lời giải "tốt". Nếu có thể chứng minh rằng một thuật toán
dựa trên phƣơng pháp tham lam cho ra kết quả tối ƣu toàn cục của một lớp bài tốn
nào đó, thì khi ấy thuật tốn ấy thƣờng sẽ đƣợc lựa chọn, vì nó chạy nhanh hơn các
phƣơng pháp tối ƣu hóa khác nhƣ quy hoạch động.
Một số thuật toán dựa trên tƣ tƣởng phƣơng pháp tham lam đã thực sự tìm ra
đƣợc phƣơng án tối ƣu nhƣ: thuật tốn Kruscal tìm cây khung cực tiểu, thuật toán
Prim dành cho bài toán cây bao trùm nhỏ nhất, thuật toán Dijkstra dành cho bài toán
đƣờng đi ngắn nhất và thuật tốn tìm cây Huffman tối ƣu.
Là một giáo viên giảng dạy bộ môn Tin học ở trƣờng PT, tôi nhận thấy việc
ứng dụng phƣơng pháp tham lam trong thiết kế thuật toán là một mảng kiến thức

rất cần thiết đối với học sinh, đặc biệt là học sinh nhóm chun Tin và đội tuyển. Vì
vậy, tơi mong muốn tìm hiểu về phƣơng pháp tham lam và ứng dụng phƣơng pháp
tham lam trong thiết kế thuật toán cho một nhóm các bài tốn, nhằm tạo ra một
nguồn tƣ liệu quan trọng cho các giáo viên, học sinh và những ngƣời quan tâm đến
phƣơng pháp này.
Từ những lí do trên, tôi quyết định lựa chọn đề tài luận văn tốt nghiệp là
“Thiết kế thuật toán dựa trên ý tƣởng của phƣơng pháp tham lam ”.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




2

2. Đối tƣợng và phạm vi nghiên cứu
- Phƣơng pháp tham lam trong thiết kế thuật toán.
- Một số bài toán đặc trƣng, cơ bản.
3. Hƣớng nghiên cứu của đề tài
- Tổng quan về phƣơng pháp tham lam.
- Thiết kế thuật toán cho một số bài toán dựa trên ý tƣởng tham lam từ đó tìm ra:
+ Các kĩ thuật sử dụng trong phƣơng pháp tham lam
+ Đối sánh phƣơng pháp tham lam với Phƣơng pháp khác
+ Hạn chế của phƣơng pháp tham lam.
- Cài đặt chƣơng trình cho một số bài toán kinh điển.
4. Những nội dung nghiên cứu chính
Chƣơng 1. TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM
(Trong chương này, học viên sẽ tìm hiểu và trình bày phương pháp tham
lam: Ý tưởng, phát biểu phương pháp, nêu ví dụ và phân tích làm rõ về phương
pháp này).

Chƣơng 2. THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA PHƢƠNG
PHÁP THAM LAM
(Dựa vào cơ sở lí thuyết trình bày ở chương I, trong chương này, học viên sẽ
phân tích thiết kế thuật toán bằng phương pháp tham lam cho 7 bài tốn cụ thể (mục 2.1
đến 2.7); Thơng qua các bài tập học viên sẽ rút ra kỹ thuật sử dụng phương pháp tham
lam; Đối sánh phương pháp tham lam với phương pháp khác ; Chỉ ra hạn chế của
phương pháp tham lam). Các bài toán cụ thể:
- Bài toán ngƣời du lịch
- Bài tốn tìm cây khung cực tiểu
- Bài toán cây bao trùm ngắn nhất
- Bài toán cái ba lơ
- Bài tốn băng nhạc
- Bài tốn xếp lịch
- Bài tốn mã hóa Huffman

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




3

Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH CHO MỘT SỐ BÀI TOÁN
(Trong chương này, dựa vào chương II, học viên sẽ xây dựng chương trình và cài
đặt chương trình cho một số bài tốn bằng ngơn ngữ C++, Free Pascal).
5. Phƣơng pháp nghiên cứu: phân tích, liệt kê, so sánh, đối chiếu, trực quan, thực
nghiệm,…
6. Ý nghĩa khoa học của đề tài
- Đƣa ra nội dung phƣơng pháp tham lam
- Ứng dụng phƣơng pháp tham lam trong thiết kế thuật toán cho một nhóm các bài

tốn, nhằm tạo ra một nguồn tƣ liệu quan trọng cho các giáo viên, học sinh và
những ngƣời quan tâm đến phƣơng pháp này.
7. Kết cấu của đề tài
Ngoài phần mở đầu, kết luận, tài liệu tham khảo đề tài gồm 3 chƣơng:
Chƣơng 1. TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM
Chƣơng 2. THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA
PHƢƠNG PHÁP THAM LAM
Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH CHO MỘT SỐ BÀI TỐN

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




4

Chƣơng 1
TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM
Các bài toán trên thực thế có mn hình mn vẻ, khơng thể đƣa ra một cách
thức chung để tìm giải thuật cho mọi bài toán. Các phƣơng pháp vét cạn
(exhaustivesearch), chia để trị (divide and conquer), quy hoạch động (dynamic
programming) và tham lam (greedy) là những “chiến lƣợc” kinh điển để tìm giải
thuật cho các bài toán.
Tham lam (greedy) là một phƣơng pháp giải các bài toán tối ƣu. Các thuật
toán tham lam dựa vào sự đánh giá tối ƣu cục bộ địa phƣơng để đƣa ra quyết định
tức thì tại mỗi bƣớc lựa chọn, với hy vọng cuối cùng sẽ tìm ra đƣợc phƣơng án tối
ƣu tổng thể.
Chƣơng I trình bày về phƣơng pháp tham lam: Ý tưởng phương pháp tham
lam, nêu ví dụ và phân tích làm rõ về phương pháp này.
1.1. Phƣơng pháp tham lam

1.1.1. Ý tưởng phương pháp tham lam
Các bài tốn tối ƣu thƣờng là có một số rất lớn nghiệm, việc tìm ra nghiệm
tối ƣu (nghiệm có giá thấp nhất) địi hỏi rất nhiều thời gian.
Một cách tiếp cận để giải quyết các bài toán tối ƣu là chiến lƣợc tham lam.
Trong hầu hết các bài toán tối ƣu, để nhận đƣợc nghiệm tối ƣu chúng ta có
thể đƣa về sự thực hiện một dãy quyết định. Ý tƣởng của chiến lƣợc tham lam là, tại
mỗi bƣớc ta sẽ lựa chọn quyết định để thực hiện quyết định đƣợc xem là tốt nhất
trong ngữ cảnh nào đó đƣợc xác định bởi bài tốn. Tức là, quyết định đƣợc lựa chọn
ở mỗi bƣớc là quyết định tối ƣu địa phƣơng. Tùy theo từng bài toán mà ta đƣa ra
tiêu chuẩn lựa chọn quyết định cho thích hợp.
Các thuật tốn tham lam nói chung là đơn giản và hiệu quả (vì các tính tốn
để tìm ra quyết định tối ƣu địa phƣơng thƣờng là đơn giản). Tuy nhiên, các thuật
tốn tham lam có thể khơng tìm đƣợc nghiệm tối ƣu, nói chung nó chỉ cho ra

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




5

nghiệm gần tối ƣu, nghiệm tƣơng đối tốt. Nhƣng cũng có nhiều thuật tốn đƣợc
thiết kế theo kỹ thuật tham lam cho ta nghiệm tối ƣu, chẳng hạn thuật toán Dijkstra
tìm đƣờng đi ngắn nhất từ một đỉnh tới các đỉnh cịn lại trong đồ thị định hƣớng, các
thuật tốn Prim và Kruskal tìm cây bao chùm ngắn nhất trong đồ thị vơ hƣớng.
Ví dụ - Bài tốn trả tiền của máy rút tiền tự động ATM:
Trong máy ATM, có sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000
đồng, 20.000 đồng và 10.000 đồng.
Giả sử mỗi loại tiền đều có số lƣợng khơng hạn chế.
Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10.000

đồng, tức là n chia hết cho 10.000).
Hãy tìm một phƣơng án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải
trả là ít nhất.
Ý tưởng phương pháp tham lam để giải quyết bài toán trả tiền của máy rút
tiền tự động ATM:
Gọi X = (X1, X2, X3, X4) là một phƣơng án trả tiền.
X1 là số tờ giấy bạc 100.000 đồng,
X2 là số tờ giấy bạc 50.000 đồng,
X3 là số tờ giấy bạc 20.000 đồng,
X4 là số tờ giấy bạc 10.000 đồng.
Theo yêu cầu ta phải có X1 + X2 + X3 + X4 nhỏ nhất
X1*100.000+X2*50.000+X3*20.000+X4*10.000 = n.
Để có số lƣợng tờ tiền nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải đƣợc
chọn nhiều nhất.
Trƣớc hết ta chọn tối đa các tờ giấy bạc 100.000 đồng, nghĩa là X1 là số
nguyên lớn nhất sao cho X1 * 100.000  n.
Tức là X1 = n DIV 100.000.
Xác định số tiền cần rút còn lại là hiệu n – X1 * 100000
Chuyển sang chọn loại giấy bạc 50.000 đồng, và cứ tiếp tục nhƣ thế cho các
loại mệnh giá khác.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




6

Giả sử n = 1290000, phƣơng án trả tiền nhƣ sau:
X1 = 1290000 DIV 100000 = 12

Số tiền còn lại là 1290000 – 12 * 100000 = 90000
X2 = 90000 DIV 50000 = 1
Số tiền còn lại là 90000 – 1 * 50000 = 40000
X3 = 40000 DIV 20000 = 2
Số tiền còn lại là 40000 – 2 * 20000 = 0
X4 = 0 DIV 10000 = 0
Ta có X = (X1, X2, X3, X4) = (12, 1, 2, 0)
Đây là một phƣơng án tối ƣu.
Tuy nhiên giả sử trong máy ATM có các loại tiền mệnh giá 50.000đ, 80.000
đồng, 10.000đ thì khi đó để rút 100.000đ theo ý tƣởng tham lam sẽ có phƣơng án
rút một tờ mệnh giá 80.000đ và hai tờ mệnh giá 10.000đ. Đây chƣa phải là phƣơng
án tối ƣu vì phƣơng án tối ƣu nhất là rút hai tờ mệnh giá 50.000đ. Song, cách lựa
chọn theo ý tƣởng tham lam cũng là một phƣơng án tốt, có thể chấp nhận đƣợc
trong thực tế.
1.1.2. Đặc trưng của phương pháp tham lam
Phƣơng pháp tham lam gợi ý chúng ta tìm một trật tự hợp lí để duyệt dữ liệu
nhằm đạt đƣợc mục tiêu một cách chắc chắn và nhanh chóng. Thơng thƣờng, dữ
liệu đƣợc duyệt theo một trong hai trật tự là tăng hoặc giảm dần theo một chỉ tiêu
nào đó. Một số bài tốn địi hỏi những dạng thức cải biên của hai dạng nói trên.
Thuật tốn tham lam có trƣờng hợp ln tìm ra đúng phƣơng án tối ƣu, có
trƣờng hợp khơng. Nhƣng trong trƣờng hợp thuật tốn tham lam khơng tìm ra đúng
phƣơng án tối ƣu, chúng ta thƣờng thu đƣợc một phƣơng án khả dĩ chấp nhận đƣợc.
Với một bài tốn có nhiều thuật tốn để giải quyết, thơng thƣờng thuật tốn
tham lam có tốc độ tốt hơn hẳn so với các thuật toán tối ƣu tổng thể.
Đặc trƣng của thuật toán tham lam thƣờng thể hiện bởi: trong mỗi bƣớc, việc
xử lí sẽ tuân theo một sự lựa chọn trƣớc, không kể đến tình trạng khơng tốt có thể
xảy ra khi thực hiện lựa chọn lúc đầu.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





7

1.1.3. Thiết kế thuật toán dựa trên ý tưởng phương pháp tham lam
Khác với các kỹ thuật thiết kế thuật toán nhƣ chia để trị, liệt kê, quy hoạch
động mà chúng ta đã biết, rất khó để đƣa ra một quy trình chung để tiếp cận bài
tốn, tìm thuật tốn cũng nhƣ cài đặt thuật toán tham lam.
Giải thuật tham lam (Greedy algorithm) là một thuật toán giải quyết một bài
tốn theo kiểu metaheuristic để tìm kiếm lựa chọn tối ƣu địa phƣơng ở mỗi bƣớc đi
với hi vọng tìm đƣợc tối ƣu toàn cục. Chẳng hạn áp dụng giải thuật tham lam với
bài tốn hành trình của ngƣời bán hàng ta có giải thuật sau: “Ở mỗi bước hãy tìm
đến thành phố gần thành phố hiện tại nhất”.
Nói chung, giải thuật tham lam thƣờng có 5 thành phần:
1. Một tập các ứng viên để từ đó tạo ra lời giải
2. Một hàm lựa chọn để theo đó chọn ứng viên tốt nhất để bổ sung vào lời
giải.
3. Một hàm khả thi dùng để quyết định nếu một ứng viên có thể đƣợc dùng
để xây dựng lời giải.
4. Một hàm mục tiêu ấn định giá trị của lời giải hoặc một lời giải chƣa hoàn
chỉnh.
5. Một hàm đánh giá chỉ ra khi nào ta tìm ra một lời giải hồn chỉnh.
1.1.3.1. Các thành phần quyết định tham lam
Tính chất 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 tốn con của 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 tốn con. Ví dụ, trong bài tố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ế),

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




8

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
tốn hiệu quả.
Chúng ta có thể lựa chọn giải pháp nào đƣợc cho là tốt nhất ở thời điểm hiện
tại và sau đó giải bài toán con nảy sinh từ việc lựa chọn vừa rồi. Lựa chọn của thuật
tốn tham lam có thể phụ thuộc vào các lựa chọn trƣớc đó. Nhƣng nó không thể phụ
thuộc vào một lựa chọn nào trong tƣơng lai hay phụ thuộc vào lời giải của các bài
toán con. Thuật toán tiến triển theo kiểu thực hiện các lựa chọn theo một vịng lặp,
cùng lúc đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Giải thuật tham
lam quyết định sớm và thay đổi đƣờng đi của thuật tốn theo quyết định đó, và
khơng bao giờ xét lại các quyết định cũ. Đối với một số bài tốn, đây có thể là một
thuật tốn khơng chính xác.
Cấu trúc con tối ưu
Một bài tốn có cấu trúc con tối ƣu nếu giải pháp tối ƣu cho bài tốn
này chứa trong nó các giải pháp tối ƣu cho các bài tốn con. Thuộc tính này là điểm
để quyết định ta có thể giải quyết bài tố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 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 mà nó định rõ giá trị của một giải pháp tối ƣu.
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. 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. Ta 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 tốn ban đầu. Sự phối hợp
hồn tồn sử dụng phƣơng pháp quy nạp đối với các bài tốn con để chứng minh

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




9

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
Một bài toán đƣợc gọi là có cấu trúc tối ƣu nếu một lời giải tối ƣu của bài
toán con chứa lời giải tối ƣu của bài toán lớn hơn.
1.1.3.2. Sơ đồ chung để giải các bài toán bằng giải thuật tham lam
Dạng các bài toán giải bằng phương pháp tham lam
Giả sử phải chọn một tập con R của các phần tử của một tập S =(s1,s2,…,sn)
sao cho tập R thỏa mãn một điều kiện ràng buộc W(R) nào đó, và một hàm mục tiêu
Z(R) đạt giá trị tối ƣu.
Ví dụ bài toán tối ƣu tổ hợp:
Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) đƣợc
gọi là hàm mục tiêu.

Mỗi phần tử X  D có dạng X = (x1, x2, .. ,xn) đƣợc gọi là một phƣơng án.
Cần tìm một phƣơng án X* D sao cho f(X*) đạt min(max). Phƣơng án X*
nhƣ thế đƣợc gọi là phƣơng án tối ƣu.
Sơ đồ chung để giải các bài toán bằng giải thuật tham lam
Bƣớc 1: Chọn một phần tử s có lợi nhất cho lời giải trong bƣớc đó sao cho
phần tử này cùng với lời giải tối ƣu của bài toán con với tập con S – {s} với ràng
buộc W(R-{s}) là lời giải tối ƣu cho bài tốn.
Bƣớc 2: Tiếp tục tìm phần tử tiếp theo có lợi nhất với tập con S=S-{s} với
ràng buộc W(R-{s}) và hàm mục tiêu Z = Z (R-{s}). Cho đến khi khơng tìm đƣợc
phần tử nhƣ vậy hoặc tập S = .
1.1.3.3. Lƣợc đồ giải thuật tham lam
Tư tưởng của phương pháp tham lam
Ta xây dựng tập S dần từng bƣớc, bắt đầu từ tập rỗng. Tại mỗi bƣớc ta sẽ
chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đƣa vào S. Việc lựa
chọn một phần tử nhƣ thế ở mỗi bƣớc đƣợc hƣớng dẫn bởi hàm chọn. Phần tử đƣợc
chọn sẽ đƣợc loại khỏi tập A. Nếu khi thêm phần tử đƣợc chọn vào tập S mà S vẫn
còn thỏa mãn các điều kiện của bài tốn thì ta mở rộng S bằng cách thêm vào phần
tử đƣợc chọn.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




10

Mơ hình:
Chọn S từ tập A;
Tính chất tham lam của thuật toán đƣợc định hƣớng bởi hàm Chọn
-


Khởi động S = 

-

Trong khi A ≠ :
+ Chọn phần tử tốt nhất của A gán vào x: x= Chọn(A)
+ Cập nhật các đối tƣợng để chọn A: A = A –{x}
+ Nếu S  {x} thỏa mãn yêu cầu bài toán thì:
Cập nhật lời giải S = S  {x}
Lược đồ tổng quát như sau:
Greedy(A, S) // A là một tập các ứng cử viên, S là tập quyết định –

Procedure

nghiệm
Begin
S  ∅;
While A <> ∅ do
Begin
x  select(A);
AA-{x};
if S  {x} đƣợc thừa nhận then SS {x};
end;
end;
Trong lƣợc đồ tổng quát trên, Select là hàm chọn, nó cho phép ta chọn từ tập A một
phần tử đƣợc xem là tốt nhất, nhiều hứa hẹn nhất là thành viên của tập nghiệm.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





11

1.1.3.4. Thiết kế một thuật toán dựa trên ý tƣởng tham lam
Khi tiếp cận bài tốn và tìm thuật tốn tham lam thì cần khảo sát kĩ bài tốn
để tìm ra các tính chất đặc biệt mà ở đó ta có thể đƣa ra quyết định tức thời tại từng
bƣớc dựa vào sự đánh giá tối ƣu cục bộ địa phƣơng.
Ý tƣởng của phƣơng pháp tham lam trong thiết kế thuật toán đƣợc tiến hành
là: Xác định trật tự xử lí để có lợi nhất, sắp xếp dữ liệu theo trật tự đó, xử lí dữ liệu
theo trật tự đã nêu.
1.1.3.5 Tiến trình thực hiện phƣơng pháp tham lam
Thuật tố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 đốn
này khơng ln tạo ra giải pháp tối ƣu, nhƣng thỉnh thoảng nó giải quyết đƣợc.
Quy trình thực hiện để phát triển thuật tốn tham lam đi qua từng bƣớc nhƣ sau:
1. Xác định cấu trúc con tối ƣu
2. Xây dựng giải pháp đệ quy
3. Chứng minh: tại mỗi bƣớc đệ qui, lựa chọn tham lam là một trong những lựa
chọn cho kết quả tối ƣu
4. Chỉ ra: sau mỗi lựa chọn tham lam, một trong những bài toán con sẽ rỗng
5. Xây dựng giải pháp đệ quy cho chiến lƣợc tham lam
6. Khử đệ quy
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ế, 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 tốn con đƣợc giải quyết một cách
tối ƣu.


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




12

Ví dụ - bài tốn chọn hoạt động:
Bài tố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. 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 tốn này trong đó ta tổng hợp

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




13

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 tốn con, một bài tốn con
cịn lại sẽ rỗng.
Dựa trên những nhận xét 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ẽ hồn thành q 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.
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 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 ln 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
tố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 tốn ban đầu.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




14

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 qt, 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 tố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 tốn tham lam cho nó.

1.2. Ví dụ
1.2.1. Bài tốn lựa chọn cơng việc
Giả sử rằng ta có một tập S = { 1,2,..., n} của n công việc sử dụng cùng một
tài ngun, ví dụ nhƣ một phịng họp, tại một thời điểm chỉ có một cơng việc đƣợc
tiến hành. Các công việc i đƣợc bắt đầu tại thời điểm si và kết thúc tại thời điểm f

i

với s ≤ f . Nếu đƣợc chọn, công việc i sẽ chiếm khoảng thời gian là [s , f )
i

i

i

i

Hãy lựa chọn các công việc không mâu thuẫn nhau (nghĩa là hoạt động i và j
là tƣơng thích nếu khoảng thời gian [s , f ] và [s , f ] không phủ lấp lên nhau(tức là i
i

i

j

j

và j là tƣơng thích nếu s >= f hay s >= f ) sao cho số các công việc đƣợc chọn là
i


j

j

i

nhiều nhất.
1.2.2. Xác định bài toán
INPUT: Thời gian khởi đầu s[1..n]; Thời gian kết thúc f[1..n]
OUTPUT: Lựa chọn các công việc không mâu thuẫn nhau sao cho số công việc
đƣợc chọn là nhiều nhất.
1.2.3. Tính chất của lời giải
Giả sử dãy cơng việc đƣợc sắp xếp tăng dần theo thời điểm kết thúc :
f  f  ...  f
1

2

n

1. Luôn tồn tại một lời giải tối ƣu chứa công việc thứ nhất
2. Nếu A  S là lời giải tối của bài tốn có chứa việc 1 thì

A – {1} là lời

giải tối ƣu của bài toán với tập S’ gồm các cơng việc bắt đầu từ thời điểm f

1

trở đi.


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




15

1.2.4. Các bước của thuật giải tham lam
1. Xác định cấu trúc tối ƣu của bài tốn
Tìm cấu trúc tối ƣu để xây dựng một lời giải tối ƣu cho bài toán từ những lời
giải tối ƣu của các bài toán con.
Gọi Sij là tập con của các hoạt động trong S có thể bắt đầu sau khi hoạt động
a kết thúc và trƣớc khi hoạt động a bắt đầu
i

j

Sij chứa 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 kết thúc không muộn hơn và bắt đầu không sớm hơn bắt đầu của aj.

Giả sử các hoạt động đƣợc sắp xếp theo thứ tự tăng thời gian kết thúc của các
hoạt động

Để tìm cấu trúc con cho bài tốn xếp lịch, khảo sát các bài toán con Sij khác
rỗng và giả thuyết lời giải Sij chứa một số hoạt động ak sao cho:
f i

k

k

j

Từ ak có thể chia thành hai bài toán con: S và S , mỗi bài toán con chứa một
ik

kj

tập con các hoạt động Sij. Lời giải cho Sij là tổ hợp của lời giải S và S cùng với
ik

kj

chính hoạt động a .
k

Giả sử có một lời giải tối ƣu Aij cho tập Sij (có chứa hoạt động a ). Khi đó các
k

lời giải a của tập Sik và a của tập S mà đƣợc dùng cho lời giải tối ƣu cho tập Sij
ik

kj

kj

cũng phải tối ƣu.
2. Xây dựng lời giải đệ qui

Tìm các tập con kích cỡ tối đa Aik và Akj chứa các hoạt động tƣơng thích
nhau cho mỗi bài tốn con.
Tạo tập kích cỡ tối đa Aij chứa các hoạt động tƣơng thích

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




16

A = A  {a }  A
ij

ik

k

kj

Đặt c[i,j] là số hoạt động của một tập con kích cỡ tối đa chứa các hoạt động
tƣơng thích trong Sij:

Ta có cơng thức đệ qui để tìm c[i, j]

Chọn hoạt động am trong Sij có thời gian hồn thành sớm nhất, rồi tìm lời giải
cho bài tốn con Smj. Hoạt động đƣợc chọn theo cách tham lam nghĩa là nó làm tối
đa thời gian còn lại chƣa đƣợc xếp lịch để đƣợc xếp lịch cho nhiều hoạt động khác.
Loại bỏ những hoạt động chƣa đƣợc xếp lịch (bị trùng lặp).
Lặp lại quá trình trên

3. Chứng minh với bất kỳ lời gọi đệ qui, một lựa chọn tối ƣu là một lựa chọn
tham lam. Vì vậy nó ln đảm bảo để tạo một lựa chọn tham lam.
Chứng minh giải thuật sử dụng hai thuộc tính sau:
Bài tốn có cấu trúc tối ƣu
Thuật giải thỏa mãn thuộc tính chọn tham lam
Một bài tốn thể hiện cấu trúc tối ƣu nếu lời giải tối ƣu của bài tốn lớn ln
chứa trong nó những lời giải tối ƣu của bài toán con.
Nếu A  S là lời giải tối của bài tốn có chứa việc một thì A’ = A – {1} là lời
giải tối ƣu của bài tốn với tập S’ gồm các cơng việc bắt đầu từ thời điểm f trở đi
1

(nghĩa là

S’={i S: s  f })
i

1

Tạo lựa chọn tốt nhất tại một thời điểm, giải các bài toán con đƣợc phát sinh
từ lựa chọn đó.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




17

Lựa chọn đƣợc tạo ra bởi giải thuật tham lam có thể phụ thuộc vào những lựa
chọn ở xa nhƣng nó khơng thể phụ thuộc vào bất kỳ lựa chọn sẽ đƣợc phát sinh hay

những lời giải của bài toán con.
4. Chỉ ra rằng duy nhất một bài toán con sau khi chọn tham lam là khác rỗng.
5. Phát triển lời giải đệ qui để thực hiện giải thuật tham lam.

Giải thuật tham lam giải bài tốn lựa chọn cơng việc

Procedure Greedy_Selector(s,f)
1. Sắp xếp tăng dần theo thời gian kết thúc các công việc
f[1] ≤ f[2] ≤ … ≤ f[n]
2. A:={1}
K:=1;
For i:=2 to n do
If si ≥ fk then
Begin
A:= A{i};
K:= i;
End;
Return A

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




18

Chƣơng 2
THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA PHƢƠNG PHÁP
THAM LAM
Dựa vào cơ sở lí thuyết trình bày ở chƣơng 1 trong chƣơng này, học viên sẽ đi

sâu phân tích thiết kế thuật tốn dựa trên ý tƣởng phƣơng pháp tham lam cho 7 bài toán
cụ thể (mục 2.1 đến 2.7); Đối sánh phƣơng pháp tham lam với phƣơng pháp khác ;
Chỉ ra hạn chế của phƣơng pháp tham lam.
2.1. Bài toán ngƣời du lịch
2.1.1. Phát biểu bài toán
Một ngƣời du lịch muốn tham quan n thành phố T1, T2,…,Tn. Xuất phát từ
một thành phố nào đó ngƣời du lịch muốn đi qua tất cả các thành phố còn lại, mỗi
thành phố đi qua đúng một lần rồi quay lại đúng thành phố xuất phát. Giả thiết ln
có đƣờng đi giữa hai thành phố bất kì .
Gọi CP(i,j) là chi phí đi từ thành phố Ti đến Tj. Hãy tìm hành trình thỏa mãn
u cầu bài tốn sao cho chi phí là nhỏ nhất.
2.1.2. Phân tích thiết kế thuật toán
2.1.2.1. Xác định bài toán
INPUT: n thành phố, CP(i,j) _ chi phí đi từ thành phố Ti đến Tj
OUTPUT: Hành trình tối ƣu và chi phí tƣơng ứng.
2.1.2.2. Ý tƣởng
Đây là bài tốn tìm chu trình có trọng số nhỏ nhất trong một đơn đồ thị vơ
hƣớng có trọng số.
Thuật toán tham lam cho bài toán là chọn thành phố có chi phí nhỏ nhất tính
từ thành phố hiện thời đến thành phố chưa qua.
2.1.2.3. Xây dựng thuật toán
Input:

n thành phố, C= (Cij)

Output:

TOUR //Hành trình tối ƣu,
COST;//Chi phí tƣơng ứng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




19

Mô tả :

Bƣớc 1: Khởi tạo : TOUR := 0; COST := 0; v := u;
Bước 2: ∀k := 1 → n ://Thăm tất cả các thành phố
// Chọn cạnh kế )
- Chọn <v, w> là đoạn nối 2 thành phố có chi phí nhỏ nhất tính từ thành
phố v đến các thành phố chƣa qua.
- TOUR := TOUR + <v, w>; //Cập nhật hành trình
- COST := COST + Cvw ;//Cập nhật chi phí
// Chuyến đi hồn thành - khi hành trình trở về thành phố xuất phát
ban đầu.
TOUR := TOUR + <v, u>;
COST := COST + Cvu ;
Bƣớc 3: Đƣa ra kết quả TOUR và COST
Minh hoạ :
Giả sử có 5 thành phố đƣợc đánh số từ 1 đến 5. Và chi phí đƣợc cho bởi ma
trận sau:

C =

Mơ tả nhƣ hình dƣới đây:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

20

1. TOUR := 0; COST := 0; u := 1;
⇒ w = 2;
2. TOUR := <1,2>; COST := 1; u := 2;
=> w = 3
3. TOUR := {<1,2>, <2,3>}; COST := 3; u := 3;
=> w = 5
4. TOUR := {<1,2>, <2,3>,<3,5>}; COST :=4 ; u := 5;
=> w = 4
5. TOUR := {<1,2>, <2,3>,<3,5>, <5,4>}; COST :=8 ; u := 4;
=> w = 1

Kết quả:
TOUR := {<1,2>, <2,3>,<3,5>, <5,4>,<4,1>};
COST :=11 ;

2.1.3. Xác định độ phức tạp của thuật toán
Thao tác chọn đỉnh thích hợp trong n đỉnh đƣợc tổ chức bằng một vịng lặp để
duyệt. Nên chi phí cho thuật tốn xác định bởi hai vịng lặp lồng nhau, do vậy T(n)
∈ O(n2).

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên