ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN
----------

PHẠM LÊ HOA

GIẢI THUẬT THAM LAM

KHÓA LUẬN TỐT NGHIỆP


MỤC LỤC
PHẦN MỞ ĐẦU ............................................................................................................1
1. Lý do chọn đề tài........................................................................................................1
2. Mục đích nghiên cứu. ................................................................................................1
3. Nhiệm vụ nghiên cứu.................................................................................................2
4. Đối tượng nghiên cứu. ...............................................................................................2
5. Phương pháp nghiên cứu. .........................................................................................2
CHƯƠNG I CƠ SỞ LÝ THUYẾT ..............................................................................3
1.1. Thuật toán (Algorithm). ........................................................................................3
1.1.1. Định nghĩa thuật toán. ........................................................................................3
1.1.2 Đặc trưng của thuật toán. ....................................................................................3
1.1.3. Thiết kế thuật tốn..............................................................................................3
1.1.4. Phân tích thuật tốn ............................................................................................4
1.1.5. Biểu diễn thuật toán ...........................................................................................4
1.2. Thời gian thực hiện của chương trình ..................................................................5
1.3. Đơn vị đo thời gian thực hiện ................................................................................5
1.4. Độ phức tạp của thuật toán ...................................................................................5
1.4.1. Khái niệm về độ phức tạp của một thuật tốn....................................................5
1.4.2. Cách tính độ phức tạp ........................................................................................5

1.5. Giải thuật tham lam là gì? .....................................................................................6
1.6. Bài toán tối ưu tổ hợp .............................................................................................6
1.7. Đặc trưng của chiến lược tham lam ......................................................................6
1.7.1. Nội dung kĩ thuật tham lam................................................................................6
1.7.2. Tính lựa chọn tham lam .....................................................................................7
1.7.3. Cấu trúc con tối ưu. ............................................................................................7
1.7.4.Đặc điểm chung của thuật toán tham lam ...........................................................8
CHƯƠNG II: BÀI TOÁN ỨNG DỤNG ......................................................................9
2.1. Cây mã Huffman. ...................................................................................................9
2.1.1. Mã huffman. .......................................................................................................9
2.1.2. Mã tiền tố .........................................................................................................10


2.1.3. Phát biểu bài tốn xây dựng mã hóa Huffman. ................................................11
2.1.4. Phân tích bài tốn xây dựng mã hóa Huffman. ................................................11
2.1.5. Thiết kế thuật tốn xây dựng mã hóa Huffman. ..............................................12
2.2. Bài toán cái balo. ...................................................................................................16
2.2.1. Phát biểu bài toán cái balo. ..............................................................................16
2.2.2. Phân tích bài tốn cái balo. ..............................................................................16
2.2.3. Thiết kế bài toán cái balo. ................................................................................16
2.3. Bài toán cây khung nhỏ nhất – thuật toán Kruskal. .........................................18
2.3.1.Phát biểu bài tốn cây khung nhỏ nhất. ............................................................18
2.3.2. Phân tích bài tốn cây khung nhỏ nhất ............................................................18
2.3.3. Thiết kế bài toán cây khung nhỏ nhất. .............................................................18
2.4. Bài toán cây khung nhỏ nhất – thuật toán Prim. ..............................................21
2.4.1. Phát biểu bài toán cây khung nhỏ nhất- bằng thuật tốn Prim.........................21
2.4.2. Phân tích bài toán cây khung nhỏ nhất. ...........................................................21
2.4.3. Thiết kế bài toán cây khung nhỏ nhất. .............................................................21
2.5. Bài toán trả tiền của máy rút tiền tự động ATM. .............................................23
2.5.1. Phát biểu bài tốn trả tiền máy rút tiền tự đơng ATM. ...................................23

2.5.2. Phân tích bài tốn trả tiền của máy rút tiền tự động ATM. ............................24
2.5.3. Thiết kế bài toán trả tiền của máy rút tiền tự động ATM. ...............................24
CHƯƠNG III: CÀI ĐẶT VÀ THỰC NGHIỆM .....................................................26
3.1. Bài toán Cây mã Huffman ...................................................................................26
3.1.1 Cài đặt chương trình ..........................................................................................26
3.1.2. Đánh giá độ phức tạp .......................................................................................30
3.1.3. Chạy chương trình xây dựng cây mã hóa. .......................................................30
3.2. Bài toán balo .........................................................................................................30
3.2.1 Cài đặt ...............................................................................................................30
3.2.2. Đánh giá độ phức tap .......................................................................................35
3.2.3. Chạy chương trình ............................................................................................35
3.3. Bài tốn cây khung nhỏ nhất (thuật toán Kruskal). ........................................35
3.3.1. Cài đặt chương trình .........................................................................................35
3.3.2. Đánh giá độ phức tạp .......................................................................................38
3.3.3. Chạy chương trình ............................................................................................38
3.4. Bài tốn tìm cây khung nhỏ nhất (thuật tốn Prim) .........................................39
3.4.1. Cài đặt chương trình .........................................................................................39
3.4.2. Đánh giá độ phức tạp .......................................................................................42


3.4.3. Chạy chương trình ............................................................................................42
3.5. Bài tốn trả tiền của máy rút tiền tự động ATM. .............................................42
3.5.1. Cài đặt chương trình .........................................................................................42
3.5.2. Đánh giá độ phức tạp ......................................................................................44
3.5.3. Chạy chương trình ............................................................................................44
KẾT LUẬN ..................................................................................................................45
1. Kết quả đạt được .....................................................................................................45
2. Hạn chế .....................................................................................................................45
3. Hướng phát triển của đề tài ....................................................................................45
TÀI LIỆU THAM KHẢO...........................................................................................46



PHẦN MỞ ĐẦU
1. Lý do chọn đề tài
Khoa học kỹ thuật ngày càng phát triển, luôn gắn liền với thực tiễn, để đáp ứng
cho cuộc sống của con người thì khoa học cần phải đưa ra những phương pháp tốt nhất
nhằm giải quyết các bài tốn trên máy tính một cách nhanh chóng và hiệu quả ít tốn bộ
nhớ và độ phức tạp nhỏ nhất, để từ đó vận dụng vào thực tiễn đưa ra kết quả như mong
muốn.
Lý thuyết tối ưu là một ngành toán học đang phát triển mạnh, và ngày càng có
nhiều ứng dụng trong các hoạt động trên mọi lĩnh vực như kinh tế, kỹ thuật, tổ chức.
Bên cạnh đó nó cịn được ứng dụng trong lĩnh vực khoa học kỹ thuật như trong y học
về chẩn đốn bệnh một cách chính xác và nhanh chóng mà ít dùng đến những phương
pháp vật lý nặng nề, tốn kém hay nhiều vấn đề khác nữa… Cuộc cách mạng thơng tin
tạo điều kiện thuận lợi chưa từng có để ứng dụng tối ưu hóa một cách rộng rãi và thiết
thực.
Những ngành khoa học về các phương pháp tối ưu đã có những bước phát triển
mạnh, đặc biệt từ khi máy vi tính được phổ biến rộng rãi và có tính năng ngày càng
mạnh. Nếu như giữa những năm 60 các bài tốn phi tuyến khoảng mười biến cịn được
gọi là cỡ q lớn, bài tốn khó thì ngày nay nhiều bài tốn đến hàng trăm, hàng nghìn
biến có thể được xử lý nhanh chóng và dễ dàng.
Những điều đó cho thấy sự nhạy cảm của giới cơng nghệ trên thế giới đối với
từng thành tựu nhỏ của các phương pháp tối ưu và vai trò ngày càng tăng của phương
pháp này trong thời đại ngày nay.
Để giải bài tốn tối ưu có rất nhiều phương pháp, phương pháp giải bài tốn tối
ưu hóa thường bao gồm một dãy các bước, ở mỗi bước có rất nhiều cách lựa chọn sao
cho tìm ra kết quả thỏa mãn điều kiện cụ thể nào đó mà kết quả đó là tốt nhất. Các
phương pháp dùng để giải quyết bài toán tối ưu như nhánh cận, giải thuật tham lam,
chia để trị, kỹ thuật quy hoạch động… Nhưng trong phần này ta chỉ sử dụng giải thuật
tham lam để giải quyết bài tốn tối ưu.

2. Mục đích nghiên cứu.
Nghiên cứu “GIẢI THUẬT THAM LAM” nhằm thấy được tầm quan trọng khi
sử dụng thuật toán tham lam vào những bài toán để đưa đến kết quả tối ưu nhất.
-1-


3. Nhiệm vụ nghiên cứu
Phân tích và thiết kế “GIẢI THUẬT THAM LAM”. Đưa ra những bài toán ứng
dụng để có thể thấy rõ được sự tối ưu của phương pháp.
4. Đối tượng nghiên cứu.
Nghiên cứu về nội dung của kỹ thuật tham lam trong “Phân tích và thiết kế giải
thuật” và trong “lý thuyết đồ thị”.
Các bài toán ứng dụng của giải thuật tham lam.
5. Phương pháp nghiên cứu.
Lý thuyết : Thu thập, phân tích, tổng hợp những tài liệu cần thiết liên quan đến
“Giải thuật tham lam “ để hồn thành đề tài.
Thực nghiệm : Tìm hiểu các ứng dụng thực tế, từ đó xây dựng chương trình cho
đề tài.

-2-


CHƯƠNG I CƠ SỞ LÝ THUYẾT
1.1. Thuật toán (Algorithm).
1.1.1. Định nghĩa thuật tốn.
Có rất nhiều định nghĩa cũng như cách phát biểu khác nhau về định nghĩa thuật
toán. Theo như cuốn sách nổi tiếng “Introduction to Algorithm” của Thomas
H.Cormen, Charles E. Leisersion, Ronadl L.Livest, Clifford Stein thì thuật tốn được
định nghĩa như sau “ một thuật toán là một thủ tục tính tốn xác định, nhận các giá trị
hoặc là một tập các giá trị được gọi là Input, và sinh ra một vài giá trị hoặc một tập giá

trị gọi là Output”.
Nói một cách khác thuật tốn giống như là các cách thức, quy trình để hồn
thành một cơng việc cụ thể xác định nào đó. Vì thế một hàm đơn giản để cộng hai số
cũng là một thuật tốn hồn chỉnh mặc dù đó là thuật tốn đơn giản.
1.1.2 Đặc trưng của thuật tốn.
+ Tính đúng đắn : Thuật toán cần phải đảm bảo cho một kết quả đúng sau khi
thực hiện đối với bộ dữ liệu đầu vào. Đây có thể nói là đặc trưng quan trọng nhất đối
với một thuật tốn.
+ Tính dừng : Thuật tốn cần phải đảm bảo tính dừng sau một số hữu hạn bước.
+ Tính xác định: Các bước của thuật tốn phải được phát biểu rõ ràng và cụ thể,
tránh gây nhập nhằng đối với người đọc, hiểu, và cài đặt thuật toán.
+ Hiệu quả: Thuật toán được xem là hiệu quả nếu như nó có khả năng giải quyết
bài tốn hiệu quả đặt ra trong thời gian hoặc các điều kiện cho phép trên thực tế đáp
ứng nhu cầu người dùng.
+Tính phổ qt: Thuật tốn được gọi là có tính phổ quát nếu nó có thể giải quyết
được một lớp bài tốn tương tự.
Ngồi ra các thuật tốn theo định nghĩa đều nhận các giá trị đầu vào được gọi
chung là các giá trị Input và kết quả của bài tốn tùy theo bài tốn và thuật tốn thì cho
kết quả cụ thể nào đó được gọi là Output.
1.1.3. Thiết kế thuật tốn
Để giải một bài tốn trên máy tính điện tử, trước tiên là ta phải có một thuật toán.
Một câu hỏi đặt ra là làm thế nào để tìm được thuật tốn cho một bài tốn đã đặt ra.
Lớp các bài toán được đặt ra từ ngành khoa học kỹ thuật, từ lĩnh vực hoạt động của
-3-


con người là hết sức phong phú và đa dạng, các thuật toán giải các bài toán khác nhau
cũng rất khác nhau. Tuy nhiên có một số kỹ thuật thiết kế thuật toán chung như chia để
trị ( Divide- and- conque), thuật toán tham lam ( Greedy method), quy hoạch động (
Dynamic programming)…việc nắm được thiết kế thuật toán này là hết sức quan trọng

và cần thiết vì nó giúp cho ta dễ tìm ra thuật tốn mới cho các bài tốn mới được đưa
ra.
1.1.4. Phân tích thuật tốn
Giả sử với một số bài tốn nào đó chúng ta có một số thuật toán giải, một câu hỏi
mới xuất hiện là chúng ta cần chọn thuật toán nào trong số thuật tốn đó để áp dụng.
Vì vậy việc phân tích thuật toán là điều rất cần thiết để đánh giá thuật toán.
* Đánh giá hiệu quả của thuật toán
Khi giải một vấn đề, chúng ta cần chọn trong số các thuật toán, một thuật toán
mà ta cho là “tốt” nhất. Vậy ta cần lựa chọn thuật toán trên cơ sở nào? Thông thường
ta dựa trên hai tiêu chuẩn sau đây:
+ Thuật toán đơn giản, dễ hiểu, dễ cài đặt.
+ Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính và đặc
biệt chạy nhanh nhất có thể được.
1.1.5. Biểu diễn thuật tốn
Có rất nhiều phương pháp biểu diễn thuật tốn. Có thể biểu diễn bằng danh sách
các bước, các bước được biểu diễn bằng ngôn ngữ thông thường và các ký hiệu tốn
học, có thể biểu diễn bằng sơ đồ khối. Tuy nhiên để đảm bảo được tính xác định của
thuật tốn thì thuật tốn được viết trên ngơn ngữ lập trình. Một chương trình là sự biểu
diễn của một thuật tốn trong ngơn ngữ lập trình đã chọn thơng thường ta sử dụng
ngơn ngữ lập trình Pascal, một ngơn ngữ được sử dụng để trình bày trong sách báo.
Ngơn ngữ thuật tốn là ngơn ngữ được dùng để miêu tả thuật tốn, thơng thường
ngơn ngữ thuật tốn gồm có ba loại:
+ Ngơn ngữ liệt kê từng bước.
+ Sơ đồ khối.
+ Ngơn ngữ lập trình.

-4-


1.2. Thời gian thực hiện của chương trình

Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký
hiệu T(n) trong đó n là kích thước của dữ liệu vào.
1.3. Đơn vị đo thời gian thực hiện
Đơn vị đo thời gian thực hiện không phải là đơn vị đo thời gian bình thường như
giờ, phút, giây… mà thường được xác định bởi số các lệnh được thực hiện trong một
máy tính lý tưởng.
1.4. Độ phức tạp của thuật toán
1.4.1. Khái niệm về độ phức tạp của một thuật toán
Thước đo hiệu quả của một thuật tốn là thời gian mà máy tính sử dụng để giải
bài toán theo thuật toán đang xét, khi các giá trị đầu vào có một kích thước xác định.
Các vấn đề như thế liên quan đến độ phức tạp tính tốn của một thuật tốn. Sự phân
tích thời gian cần thiết để giải một bài tốn có kích thước đặc biệt nào đó có liên quan
đến độ phức tạp thời gian của thuật toán. Việc xem xét độ phức tạp thời gian của một
thuật toán là một vấn đề rất thiết yếu khi các thuật toán thực hiện.
Độ phức tạp của thời gian của một thuật tốn có thể biểu diễn qua số các phép
toán được dùng bởi thuật toán đó khi các giá trị đầu vào có một kích thước xác định.
Sở dĩ độ phức tạp thời gian được mơ tả thơng qua các phép tốn địi hỏi thay vì thời
gian thực của máy tính bởi vì các máy tính khác nhau sẽ thực hiện các phép tính sơ cấp
trong những khoảng thời gian khác nhau, hơn nữa phân tích tất cả các phép tốn thành
các phép tính bít sơ cấp mà máy tính sử dụng là điều rất phức tạp.
Khi nói đến độ phức tạp của thuật tốn là ta muốn nói đến hiệu quả của thời gian
thực hiện chương trình nên ta có thể xem việc xác định thời gian thực hiện của chương
trình chính là xác định độ phức tạp.
1.4.2. Cách tính độ phức tạp
* Quy tắc cộng
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2 và
T1(n) =O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của hai đoạn chương trình đó nối
tiếp nhau là T(n)= O(max(f(n),g(n))).
* Quy tắc nhân
-5-



Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2 và
T1(n) =O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của hai đoạn chương trình đó là
lồng nhau là T(n)= O(f(n),g(n)).
* Quy tắc tổng quát để phân tích một đoạn chương trình
Thời gian thực hiện của mỗi lệnh gán READ, WRITE là O(1).
Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng quy tắc
cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi
lệnh.
Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN
hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là
O(1).
Thời gian thực hiện vòng lặp là tổng thời gian thưc hiện thân vòng lặp. Nếu thời
gian thực hiện thân vịng lặp khơng đổi thì thời gian thực hiện vịng lặp là tích của số
lần lặp với thời gian thực hiện thân vòng lặp.
1.5. Giải thuật tham lam là gì?
Là một thuật tốn dùng để giải quyết bài tốn để tìm kiếm lựa chọn tối ưu địa
phương ở mỗi bước với hy vọng tìm được tối ưu tồn cục.
1.6. Bài tốn tối ưu tổ hợp
Là một dạng bài tốn tối ưu, nó có dạng tổng qt như sau:
- 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 hàm f(X) đạt min( max). Phương án X
như thế gọi là phương án tối ưu.
1.7. Đặc trưng của chiến lược tham lam
1.7.1. Nội dung kĩ thuật tham lam.
Tham lam theo cách hiểu dân gian là trong một mâm có nhiều món ăn, món nào
ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại

ăn hết món ngon thứ hai này chuyển sang món ngon thứ ba…

-6-


Kỹ thuật tham ăn thường được vận dụng giải bài toán tối ưu tổ hợp bằng cách
xây dựng một phương án X. Phương án X được xây dựng bằng cách lựa chọn từng
thành phần Xi của X cho đến khi hoàn chỉnh tức là đủ n thành phần. Với mỗi Xi, ta sẽ
chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta khơng cịn gì để chọn mà
phải chấp nhận giá trị cuối cùng còn lại.
1.7.2. Tính lựa chọn tham lam
Thành phần then chốt trước tiên là tính lựa chọn tham lam, một giải pháp tối ưu
toàn cục bằng cách lựa chọn tối ưu cục bộ khi có nhiều sự lựa chọn thì ta có thể lựa
chọn phương án nào tốt nhất trong thời điểm hiện tại của bài tốn hiện tại mà khơng
cần quan tâm đến kết quả của giai đoạn sau.
Đây là chỗ khác nhau giữa các thuật toán tham lam và quy hoạch động. Trong
quy hoạch động tại mỗi bước ta thực hiện một lựa chọn, nhưng sự lựa chọn phụ thuộc
vào giải pháp cho bài tốn con, do đó ta xử lý bài toán quy hoạch động từ dưới lên
(Bottom - Up ), nghĩa là xử lý những bài toán nhỏ hơn đến bài toán con lớn hơn. Đối
với giải thuật tham lam ta lựa chọn phương án tốt nhất ngay lúc đó và giải quyết bài
tốn con sau khi lựa chọn được thực hiện. Việc lựa chọn bởi một thuật toán tham lam
lựa chọn cho đến thời điểm hiện tại đó, nhưng nó khơng thể phụ thuộc bất kỳ trong
tương lai hay những giải pháp cho các bài toán con. Vì vậy khơng giống như thuật
tốn quy hoạch giải quyết bài toán từ dưới lên, mà một thuật toán tham lam giải quyết
bài toán từ trên xuống.
Thuật toán tham lam thường đạt hiệu lực khi ta thực hiện lựa chọn 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 một thời điểm kết thúc, ta cần kiểm tra mỗi một hoạt
động. Thường là nó đươ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 là một hàng đợi ưu thế ) nên ta có thể thực hiện lựa chọn tham lam

một cách nhanh chóng . Vì vậy với việc lựa chọn đó sẽ đưa ra một thuật toán hiệu quả.
1.7.3. Cấu trúc con tối ưu.
Một bài tố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. Thuộc tính này là điểm quyết định ta có
thể giải quyết bài toán bằng phương pháp quy hoạch động cũng như tham lam được
hay không.

-7-


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 giải thuật tham lam. Và điều mà ta cần làm ở đây là cho ra giải pháp tối ưu cho bài
toán con, kết hợp với sự lựa chọn tham lam vừa thực hiện mang lại một giải pháp tối
ưu cho bài toán ban đầu.
1.7.4.Đặc điểm chung của thuật toán tham lam
Mục đích xây dựng bài tốn giải nhiều lớp bài tốn khác nhau, đưa ra quyết định
dựa ngay vào thuật toán đang có, và trong tương lai sẽ khơng xem xét lại quyết định
trong q khứ. Vì vậy thuật tốn dễ đề xuất, thời gian tính nhanh nhưng có một số bài
tốn khơng cho kết quả tối ưu.
Giải thuật tham lam có năm phần:
- Một tập hợp các ứng viên để từ đó tạo ra lời giải.
- Một hàm lựa chọn, theo đó để lựa chọn các ứng viên tốt nhất bổ sung vào lời
giải.
- 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.
- 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.
- 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.

-8-



CHƯƠNG II: BÀI TOÁN ỨNG DỤNG
2.1. Cây mã Huffman.
2.1.1. Mã huffman.
Thuật toán được đề xuất bởi David A. Hunman khi ông còn là sinh viên tại MIT
và được công bố 1952 trong bài báo “A Method for the Construction of MinimumRedundancy Code”. Thuật toán này được sử dụng rộng rãi trong việc nén dữ liệu,
thường tiết kiệm từ 20% đến 90 % phụ thuộc vào đặc tính của tập tin được nén. Ta
xem như dữ liệu đó là một chuỗi ký tự. Giải pháp tham lam của Huffman sử dụng một
bảng gồm các tần suất xuất hiện của các ký tự để xây dựng nên một cách biểu diễn tối
ưu mỗi ký tự dưới dạng một chuỗi nhị phân.
Phương pháp biểu diễn ký hiệu trong máy tính phổ biến nhất là sử dụng chuỗi
các bit có độ dài cố định. Chẳng hạn ASCII biểu diễn mỗi ký hiệu bằng xâu 8 bít, ví dụ
A biểu diễn bằng xâu 01000001. Như vậy một bản tin có N ký hiệu sẽ phải mã hóa bởi
8*N bít. Vậy có phương pháp mã hóa nào tiết kiệm hơn không?
Giả sử một bản tin gồm các dãy kí hiệu lấy trong một tập hữu hạn X. Biết rằng
mỗi ký hiệu x trong bản tin xuất hiện theo một xác suất cho trước p(x). Ta muốn mã
hóa các ký hiệu này thành các chuỗi bit nhị phân sao cho chiều dài chuỗi mã của bản
tin là ngắn nhất.
Ví dụ: Xét bản tin gồm 1010 ký hiệu lấy từ trong tập X={a, b, c, d, e, f}. Tần suất
xuất hiện các ký hiệu trong bản tin như sau:
Ký hiệu

:

a

b

c


d

Tần suất (%)

:

40 10 15 5

e

f

20 10

Ta có thể dùng xâu bit cố định để mã hóa các ký tự. Chẳng hạn
Ký hiệu

:

Mã I

:

a

b

c


d

000 001 010 011

e

f

100 101

Nếu dùng cách này thì cho chiều dài bản tin mã hóa là 3* 1010 bit.
Cách mã hóa thứ hai là
Ký hiệu

:

a

b

c

d

e

f

Mã II


:

0

01

00

11

1 10

Cách này cho chiều dài bản tin mã hóa là
1010(1*40+2*10+2*15+2*5+1*20+2*10)/100 =1.4 *1010 ( bit)
-9-


Cách mã II rút ngắn bản tin hơn một nữa so với cách mã I. Tuy nhiên cách này dễ
dẫn đến nhầm lẫn, chẳng hạn dãy aa và ký tự e cùng một mã là 00.
Ta xét cách mã sau:
Ký hiệu

:

a

b

Mã III


:

1 010

c

d

011 0010

e

f

000 0011

Cách mã hóa này cho chiều dài bản tin mã hóa là
1010(1*40+3*10+3*15+4*5+3*20+4*10)/ 100 =2.35*1010 (bit)
Cách mã III dài hơn mã II nhưng các ký tự mã hóa khơng giống nhau. Cách mã
III ngắn hơn cách mã I và các ký tự mã hóa khơng giống nhau.
Vậy ta thấy rằng khi biểu diễn các tập tin đó theo cách mã III tiết kiệm khoảng
25%. Thật vậy đây là cách mã hóa tối ưu.
2.1.2. Mã tiền tố
Khơng có chuỗi mã của ký hiệu nào là tiền tố ( tức là dãy con đầu ) của chuỗi mã
của ký hiệu khác. Vậy mã nhị phân thỏa mãn tính chất này thì gọi là mã tiền tố.
Mã tiền tố cần thiết bởi vì chúng làm đơn giản hóa việc giải mã. Vì rằng khơng
có mã nào là tiền tố của bất kỳ mã khác, nên từ mã bắt đầu một tập tin được mã hóa là
rất rõ ràng. Ta có thể nhận biết một cách đơn giản từ mã lúc đầu, dịch nó trở lại ký
hiệu gốc ban đầu. Ta có ví dụ chuỗi 00101010011 theo cách mã III phân ra một cách
duy nhất là dabc.

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 dễ dàng
chọn ra từ mã ban đầu. Một cây nhị phân mà 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à 1có nghĩa là “đi đến con
phải”.
Ví dụ Cây nhị phân của mã tiền tố III ở ví dụ trên

-10-


Hình 1
Xét cây nhị phân T, trên đó mỗi lá được gán nhãn là một ký hiệu trong X. Khi đó
cây T sẽ xác định một mã tiền tố. Với mỗi lá x, mức h(x) của x chính là chiều dài của
chuỗi mã của x. Gọi f(x) là tần suất xuất hiện của ký hiệu x thì chiều dài của chuỗi mã
bản tin là
L*∑𝐱∈𝐗 𝐡(𝐱) ∗ 𝐟(𝐱)
Trong đó L là số ký hiệu của bản tin. Đại lượng
E(T)= ∑𝐱∈𝐗 𝐡(𝐱) ∗ 𝐟(𝐱) gọi là hệ số mã hóa.
Độ dài chuỗi mã bản tin ngắn nhất khi và chỉ khi cây T có hệ số mã hóa nhỏ nhất.
Cây T như vậy gọi là cây mã tối ưu.
2.1.3. Phát biểu bài tốn xây dựng mã hóa Huffman.
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 xuất tại bất kỳ vị trí nào trong thơng báo. 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.
2.1.4. Phân tích bài tốn xây dựng mã hóa Huffman.
Cho trước một tập hợp các ký tự X và bảng tần suất f(x) với mọi x∈ 𝑋
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ã ký tự
khác.
+ Độ dài của bộ mã là ngắn nhất.

-11-


2.1.5. Thiết kế thuật tốn xây dựng mã hóa Huffman.
Giải thuật Huffman
Các bước thực hiện:
Bước 1: T là rừng có n =|X| cây, mỗi cây có đúng 1 đỉnh tương ứng với một ký tự
trong C. Gán mỗi gốc x một nhãn f(x).
Bước 2: Nếu T là cây thì dừng : T là cây mã tối ưu, ngược lại sang bước 3.
Bước 3: Tìm hai cây trong T với nhãn gốc nhỏ nhất. Gọi các gốc là u và v. Nối u
và v với đỉnh w ta được cây mới gốc w (các cây u và v trở thành cây con của w). Nhãn
gán cho w là tổng nhãn của u và v. Quay trở lại bước 2.
Bổ đề: Gọi x và y là hai ký hiệu có tần suất xuất hiện f(x) và f(y) nhỏ nhất trong
X. Khi đó tồn tại cây mã tối ưu T của X sao cho x và y là hai nút anh em trong T.
Chứng minh:
Gọi T0 là một cây mã tối ưu của X.
Giả sử x, y không là lá anh em. Gọi u là lá có mức lớn nhất trong T0. Khi đó u
phải có lá anh em v, vì nếu khơng ta có thể xóa nút u và gán ký hiệu u cho cha của u
và ta có mã mới tốt hơn T0, mâu thuẫn với T0 là cây mã tối ưu.
Nếu x không cùng mức với u, tức h(x) < h(u), ta hoán đổi ký hiệu x và u và nhận
được cây mới T1. Ta có
E(T1) = E(T0) – h(x).f(x)-h(u).f(u)+h(x).f(u)+h(u).f(x)
= E(T0) – [h(u)-h(x)].[f(u)-f(x)]

<

E(T0)

Điều này mâu thuẫn với tính tối ưu của T0. Vậy x và tương tự y có cùng mức với
u, v. Bằng cách hoán đổi x với u và y với v ta nhận được cây T có E(T) =E(T0), nghĩa

là T cũng là cây tối ưu.
Định lý: Giải thuật Huffman cho cây mã tối ưu.
Chứng minh:
Quy nạp theo số ký hiệu n của X.

Bước cơ sở : n=2 Giả sử hai ký hiệu trong X là x và y thì giải thuật cho cây mã
Và hiển nhiên đây là cây mã tối ưu.
-12-


Bước quy nạp: Giả sử X có n ký hiệu, x và y là hai ký hiệu có tần suất nhỏ nhất.
Gọi X’ là tập có n -1 ký hiệu nhận được từ X bằng cách thay ký hiệu x và y bằng
1 ký hiệu z với tần suất f(z) = f(x) +f(y).
Theo bổ đề tồn tại cây mã tối ưu T sao cho x và y là anh em. Từ T bỏ hai nút lá x
và y và gán cho nút cha của x và y ta nhận được cây mã T’ của X’.
Bây giờ cho H là cây nhận được từ giải thuật Huffman của X với x và y là anh
em. Từ H bỏ hai nút lá x và y và gán z cho nút cha của x và y ta nhận được cây mã
Huffman H’ của X’. Theo giả thiết quy nạp H’ là cây mã tối ưu. Vì vậy ta có
E(H) = E(H’) +f(x) +f(y) ≤ E(T’) +f(x) +f(y) =E(T)
Mặt khác vì T là cây tối ưu nên từ đó suy ra E(H) = E(T), tức là H tối ưu.
Ví dụ minh họa
Xét ví dụ với bảng ký hiệu và tần suất như sau:
Ký hiệu

: a

b

c


d

Tần suất (%) : 40 10 15 5

e

f

20 10

Cây nhị phân của mã Huffman được xây dựng qua các bước:
Khởi tạo : Rừng T có 6 cây có gốc là a, b, c, d, e. f với các nhãn được ghi trong
ngoặc.

Bước 1: Gốc d và b có nhãn nhỏ nhất, nối chúng vào gốc db. Rừng T có 5 cây có
gốc là a, e, db, c,f

-13-


Bước 2 : Gốc f và c có nhãn nhỏ nhất, nối chúng vào gốc fc. Rừng T có 4 cây có
gốc là a, e, db, fc

Bước 3: Gốc db vào e có nhãn nhỏ nhất, nối chúng vào gốc dbe. Rừng T có 3 cây
có gốc là a, dbe, fc.

Bước 4: Gốc fc và dbe có nhãn nhỏ nhất, nối chúng vào gốc fcdbe. Rừng T có 2
cây có gốc là a, fc, fcdbe.

-14-



Bước 5: Nối a và fcdbe vào gốc afcdbe. T là cây mã tối ưu:

-15-


Mã Huffman tương ứng như sau:
Ký hiệu

:a

Mã Huffman : 1

b
0010

c
010

d
0011

e
000

f
011

Cách mã hóa này cho chiều dài bản tin là

1010(1*40 + 4*10 +3 *15 +4 *5 +3 *20 +3 *10)/ 100 = 2.35 * 1010
2.2. Bài toán cái balo.
2.2.1. Phát biểu bài tốn cái balo.
Cho một cái balo có thể đựng trọng lượng W và n loại đồ vật, mỗi đồ vật i có một
trọng lượng là gi và một giá trị là vi. Tất cả các loại đồ vật đều có số lượng khơng hạn
chế. Tìm một cách lựa chọn các đồ vật đựng vào balo, chọn các loại đồ vật nào, mỗi
loại lấy bao nhiêu sao cho tổng trọng lượng khơng vượt q W và có tổng giá trị lớn
nhất.
Một số biến thể của bài toán cái balo:
Mỗi đồ vật i chỉ có một số lượng là si. Mỗi bài tốn này khi lựa chọn vật i ta
khơng được lấy một số lượng vượt quá si.
Với bài toán này thì ta chỉ có thể chọn hoặc khơng chọn đồ vật.
2.2.2. Phân tích bài tốn cái balo.
Input:
Nhập trọng lượng của túi và số lượng loại hàng.
Nhập thông tin của từng loại sản phẩm bao gồm: Thứ tự sản phẩm, tên sản phẩm,
trọng lượng, giá trị và đơn giá.
Output:
Trả về số lượng sản phẩm được chọn sao cho tổng trọng lượng các sản phẩm
được chọn không lớn hơn trọng lượng trong túi.
2.2.3. Thiết kế bài toán cái balo.
Theo như yêu cầu của bài tốn ta cần phải chọn những vật có giá trị cao nhưng
trọng lượng phải nhỏ để có thể mang được nhiều đồ quý, sẽ là hợp lý khi ta quan tâm
đến yếu tố “đơn giá” của từng loại đồ vật tức là tỷ lệ giá trị/trọng lượng. Đơn giá càng
cao thì đồ vật càng q. Từ đó ta có kĩ thuật tham lam áp dụng cho bài tốn này là:
 Tính đơn giá các lồi đồ vật.
 Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ.
-16-



 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
balo cho phép.
 Xác định trọng lượng còn lại của balo và quay lại bước ba cho đến khi khơng
cịn có thể chọn đồ vật nào nữa.
Ví dụ minh họa
Ta có một balo có trọng lượng là 37kg và 4 loại đồ vật với trọng lượng tương
ứng cho bên dưới.

Loại đồ vật

Trọng lượng

Giá trị

A

15

30

B

10

25

C

2


2

D

4

6

Cách giải : Áp dụng kĩ thuật tham lam. Ta có :
Từ bảng đã cho ta tính đơn giá cho các loại đồ vật bằng công thức : đơn giá = tỷ
lệ giá trị/ trọng lượng. Sau đó 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 sau:
Loại đồ vật

Trọng
lượng(kg)

Giá trị

Đơn giá

B

10

25

2.5

A


15

30

2.0

D

4

6

1.5

C

2

2

1.0

-17-


Vậy ta có thứ tự ưu tiên của việc chọn đồ vật là B, A, D và cuối cùng là C.
Giải thích :
Vật B được xét đầu tiên và ta chọn tối đa 3 cái, vì mỗi cái trọng lượng là 10kg và
balo có trọng lượng là 37kg. Tức là ta có 37 Div 10 = 3.

Sau khi ta đã chọn 3 vật B, thì trọng lượng cịn lại trong balo là
37kg - 3*10kg = 7 kg.
Tiếp theo, ta xét đến vật A vì vật A có trọng lượng là 15kg mà trọng lượng còn
lại của balo chỉ còn 7kg nên ta khơng chọn vật A.
Xét đến vật D vì trọng lượng của vật D là 4kg nên ta có thể chọn một vật D
( 7 Div 4 =1) và khi đó trọng lượng cịn lại là 7kg – 1*4kg = 3 kg.
Cuối cùng, ta chọn được một vật C và trọng lượng còn lại là 3 kg – 1*2 kg =1 kg.
Như vậy ta đã chọn được 3 vật B, 1 vật D, và 1 vật C.
Tổng trọng lượng là (3*10 kg + 1*4 kg +1*2 kg) = 36 kg
Tổng giá trị là (3*25 +1*6+1*2)= 83.
2.3. Bài toán cây khung nhỏ nhất – thuật toán Kruskal.
2.3.1.Phát biểu bài toán cây khung nhỏ nhất.
Cho đồ thị G=(V,E), mỗi cạnh có trọng số. Một cây khung của một đồ thị liên
thông G là một đồ thị con 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.
2.3.2. Phân tích bài tốn cây khung nhỏ nhất
Input: Đồ thị G=(V,E) với trọng số.
Các đỉnh ký hiệu là

1, 2, … , n

Trọng số của cạnh (i,j),(i,j) ký hiệu là cij
Output : cây phủ nhỏ nhất T, hoặc kết luận đồ thị không liên thông.
2.3.3. Thiết kế bài toán cây khung nhỏ nhất.
Bước 1: khởi tạo:
T:=(V, ∅ ) là đồ thị gồm các đỉnh của G và không có cạnh .
Bước 2: Kiểm tra điều kiện kết thúc :
Nếu T có n-1 cạnh, kết thúc. Kết luận : T là cây phủ nhỏ nhất. Ngược lại sang
bước 3.

-18-


Bước 3: Thêm cạnh: Chọn cạnh có trọng số nhỏ nhất không thuộc T sao cho khi
thêm cạnh này vào T thì khơng tạo ra chu trình trong T. Quay lại bước 2. Ngược lại,
nếu không chọn được cạnh thêm vào T thì kết thúc. Kết luận đồ thị G khơng liên
thơng.
Ví dụ minh họa

a

4

b
5

2
3

1
c
6

d
3
6

e
2


f
Hình 2

(1). Khởi tạo: T:=({abcdef},∅) khơng có cạnh, số cạnh e:=0, trọng số d(T):=0;
(2). Kiểm tra : Số cạnh của T: e=0, sang bước 3.
(3). Thêm cạnh : Trong các cạnh không thuộc T cạnh (c,d) có độ dài nhỏ nhất là 1.
Thêm cạnh (c,d) vào T. Ta có:
T=({abcdef}, {(c,d)}) , d(T):= d(T)+1 =1 và số cạnh e=1.
(2). Kiểm tra : Số cạnh của T là 1, sang bước 3
(3). Thêm cạnh : Trong các cạnh khơng thuộc T cạnh (a,c) có độ dài nhỏ nhất là 2 và
không cùng các cạnh của T tạo thành chu trình.
Thêm cạnh (a,c) vào T. Ta có:
T=({abcdef}, {(c,d),(a,c)}) , d(T):= d(T)+2 =3 và số cạnh e=2.
(2). Kiểm tra : Số cạnh của T là 2, sang bước 3
(3). Thêm cạnh : Trong các cạnh không thuộc T cạnh (e,f) có độ dài nhỏ nhất là 2 và
khơng cùng các cạnh của T tạo thành chu trình.
-19-


Thêm cạnh (e,f) vào T. Ta có:
T=({abcdef},{(c,d),(a,c),(e,f)}) , d(T):= d(T)+2 =5 và số cạnh e=3.
(2). Kiểm tra : Số cạnh của T là 3, sang bước 3.
(3). Thêm cạnh : Trong các cạnh khơng thuộc T cạnh (a,e) có độ dài nhỏ nhất là 3 và
không cùng các cạnh của T tạo thành chu trình.
Thêm cạnh (a,e) vào T. Ta có:
T=({abcdef},{(c,d),(a,c),(e,f),(a,e)}) , d(T):= d(T)+5 = 8 và số cạnh e= 4.
(2). Kiểm tra : Số cạnh của T là 4, sang bước 3.
(3). Thêm cạnh : Trong các cạnh không thuộc T cạnh (a,b) có độ dài nhỏ nhất là 4 và
không cùng các cạnh của T tạo thành chu trình.
Thêm cạnh (a,b) vào T. Ta có:

T=({abcdef},{(c,d),(a,c),(e,f),(a,e),(a,b)}) , d(T):= d(T)+4 = 12 và số cạnh e= 5.
(2). Kiểm tra : Số cạnh của T là 5. Kết thúc
Kết luận : Ta có cây phủ nhỏ nhất gồm các cạnh
(c,d),(a,c),(e,f),(a,e),(a,b)
a

4

b
5

2
3

1
c
6

d
3
6

e

2

f
Hình 3

Với tổng trọng số là d(T)= 12.


-20-


2.4. Bài toán cây khung nhỏ nhất – thuật toán Prim.
2.4.1. Phát biểu bài toán cây khung nhỏ nhất- bằng thuật toán Prim.
Cho đồ thị G=(V,E) với trọng số. Các đỉnh kí hiệu là 1,2,…,n và trọng số của
cạnh là (i,j), (i,j)∈E.
Một cây khung của đồ 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.
2.4.2. Phân tích bài tốn cây khung nhỏ nhất.
Input: Đồ thị G=(V,E) với trọng số.
Các đỉnh ký hiệu là 1,2,….n
Trọng số của cạnh (i,j), (i,j)∈ E, ký hiệu là cij
Output: Cây phủ nhỏ nhất T, hoặc kết luận đồ thị không liên thơng .
2.4.3. Thiết kế bài tốn cây khung nhỏ nhất.
Bước 1: khởi tạo :
Giả sử đồ thị T gồm có một đỉnh và khơng có cạnh.
Bước 2: Kiểm tra điều kiện kết thúc:
Nếu T có n đỉnh hoặc n-1 cạnh thì kết thúc, kết luận: T là cây phủ nhỏ nhất.
Ngược lại sang bước 3.
Bước 3: Thêm cạnh
Ký hiệu M là tập
M={(i,j)∈ E | i∈ T& j  T }
Tìm cạnh (k,h ) ∈ M sao cho
Ckh= min {cij | (i,j) ∈ M}
Nếu ckh < ∞, thêm cạnh (k,h) và đỉnh h vào T, sang bước(2).
Ngược lại, tức M =∅, kết thúc. Kết luận đồ thị G không liên thông.

-21-