BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

---------------------------------------

NGUYỄN DUY HIỆP

ỨNG DỤNG THUẬT TOÁN LAI
GIẢI BÀI TOÁN
CÂY KHUNG TRUYỀN THÔNG TỐI ƯU

LUẬN VĂN THẠC SĨ KHOA HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. NGUYỄN ĐỨC NGHĨA

Hà nội – 2010


Lời cảm ơn
Đầu tiên tôi xin bày tỏ sự biết ơn sâu sắc PGS. TS. Nguyễn Đức Nghĩa, thầy đã tận
tình giảng dạy chúng tôi các môn học chuyên ngành và nhiệt tình hướng dẫn, giúp
đỡ tôi hoàn thành luận văn này.
Tôi cũng muốn bày tỏ lòng biết ơn các thầy cô khoa Công nghệ Thông tin trường
Đại học Bách khoa Hà Nội đã giảng dạy cho chúng tôi các môn học chuyên đề
trong khóa học.
Cuối cùng tôi xin gửi lời cảm ơn sâu sắc đến gia đình, và bạn bè, những người luôn
ở bên cạnh giúp đỡ, động viên tôi trong quá trình hoàn thành đồ án.
Mặc dù đã có nhiều cố gắng, nhưng vì kiến thức và thời gian hạn chế nên chắc chắn
luận văn này còn nhiều thiếu sót. Tôi xin chân thành cảm ơn và rất mong nhận được

những ý kiến đóng góp từ các thầy cô và các bạn. Những góp ý xin gửi về địa chỉ:
Nguyễn Duy Hiệp
Bộ môn Khoa học máy tính, viện Công nghệ thông tin và truyền thông,
trường Đại học Bách Khoa Hà Nội.
Email: hoặc

Hà Nội, ngày 31 tháng 10 năm 2010
Nguyễn Duy Hiệp
Học viên cao học
Lớp Công nghệ thông tin 2008 – 2010
Trường Đại học Bách Khoa Hà Nội

~1~


Lời mở đầu
Việc phát triển các thuật toán hiệu quả để giải các bài toán NP – khó (NP – hard) là
một vấn đề được quan tâm của nhiều nhà khoa học nghiên cứu về máy tính. Bởi vì
chúng thường có rất nhiều ứng dụng trong thực tiễn, ví dụ như bài toán người du
lịch, bài toán đóng thùng, bài toán cây Steiner, bài toán người đưa thư Trung Hoa,
… Đối với các bài toán này các thuật toán giải chính xác thường có thời gian tính
lớn do độ phức tăng rất nhanh khi kích thước bài toán tăng. Do đó hiện nay người ta
thường sử dụng cách tiếp cận giải gần đúng. Các phương pháp giải gần đúng
thường dùng là: các thuật toán xấp xỉ (approximation schemes), tìm kiếm cục bộ
(local search), các phương pháp xác xuất (probabilistic methods), tính toán tiến hóa
(evolutionary computation), thuật toán di truyền (genetic algorithm), …
Luận văn này tập trung vào xây dựng thuật toán di truyền lai để giải bài toán cây
khung truyền thông tối ưu (Optimal Communication Spanning Tree - OCST). Đây
là một trong những bài toán trên đồ thị thuộc lớp NP-khó, và có ứng dụng trong
nhiều lĩnh vực thực tế như thiết kế vi mạch và các mô hình mạng.

Thuật toán đề xuất đã được chạy thử nghiệm trên các bộ dữ liệu thường dùng bởi
các nhà khoa học để đánh giá các thuật toán giải bài toán OCST, và một số bộ dữ
liệu có kích thước lớn được sinh ngẫu nhiên. Kết quả thực nghiệm cho thấy thuật
toán cho kết quả là tốt hơn so với một số một số thuật toán di truyền tốt nhất hiện
biết. Những kết quả đạt được được trình bày thành một bài báo và đã được chấp
nhận đăng trong hội thảo quốc tế lần thứ 26 về tính toán ứng dụng (Symposium On
Applied Computing – SAC) diễn ra vào 21-24/3/2011 tại đại học Tunghai,
TaiChung, Taiwan.
Luận văn được bố cục như sau :
Chƣơng 1 trình bày một số kiến thức cơ sở trong lý thuyết về độ phức tạp tính toán,
lớp bài toán NP-khó làm nền tảng cho các chương tiếp theo.

~2~


Chƣơng 2 trình bày tổng quan về bài toán cây khung truyền thông tối ưu và các
hướng tiếp cận đã được đề xuất để giải quyết bài toán.
Chƣơng 3 trình bày sơ đồ của hai giải thuật meta-heuristic gồm giải thuật di truyền
và giải thuật tối ưu hóa bày đàn.
Chƣơng 4 đề xuất giải thuật di truyền lai dựa trên giải thuật di truyền chuẩn kết hợp
với giải thuật tối ưu hóa bày đàn để giải bài toán cây khung truyền thông tối ưu.
Chƣơng 5 trình bày kết quả thực nghiệm của giải thuật di truyền lai đề xuất trong
chương 4. Giải thuật được thực hiện với sáu loại mã hóa cây khung và hai phương
pháp lai ghép nhằm so sánh hiệu quả so với các giải thuật hiện biết.
Kết luận và hƣớng phát triển
Đánh giá tổng quan lại những kết quả đã thực hiện được, những hạn chế của luận
văn và một số vấn đề mở cần tiếp tục giải quyết.

~3~



Mục lục
Lời cảm ơn ............................................................................................................... 1
Lời mở đầu ............................................................................................................... 2
Danh mục hình vẽ.................................................................................................... 7
Danh mục bảng ...................................................................................................... 10
Danh mục thuật ngữ tiếng Anh ........................................................................... 11
CHƢƠNG 1 CÁC KHÁI NIỆM CƠ BẢN ....................................................... 13
1.1. Thuật toán và đánh giá độ phức tạp của thuật toán ................................................. 13
1.1.1 Khái niệm thuật toán ...........................................................................................13
1.1.2. Đánh giá thuật toán ............................................................................................19
1.2. Độ phức tạp tính toán của bài toán ......................................................................... 24
1.2.1. Khái niệm về độ phức tạp của bài toán ..............................................................24
1.2.2 Các bài toán NP ..................................................................................................27
1.3. Một số cách tiếp cận giải các bài toán NP-khó ....................................................... 36
1.3.1 Phương pháp xấp xỉ ............................................................................................36
1.3.2 Phương pháp xác xuất .........................................................................................37
1.3.3. Phương pháp heuristic .......................................................................................38
1.3.4. Phương pháp tính toán tiến hóa .........................................................................40

CHƢƠNG 2 BÀI TOÁN CÂY KHUNG TRUYỀN THÔNG TỐI ƢU ......... 46
2.1. Bài toán cây khung truyền thông tối ưu .................................................................. 46
2.2 Một số tính chất của các trường hợp đặc biệt của bài toán OCST .......................... 49
2.2.1 Bài toán MRCT ...................................................................................................49
2.2.2. Bài toán cây khung truyền thông tối ưu tích nhu cầu (PROCT) .......................51
2.2.3. Bài toán cây khung truyền thông tối ưu tổng nhu cầu (SROCT) ......................52
2.2.4. Bài toán nhiều nguồn (Multiple Source)............................................................52
2.3. Một số ứng dụng của bài toán cây khung truyền thông .......................................... 54
~4~



2.4. Các phương pháp tiếp cận để giải bài toán OCST .................................................. 57

CHƢƠNG 3 THUẬT TOÁN DI TRUYỀN VÀ TỐI ƢU HÓA BẦY
ĐÀN …………… ................................................................................................... 67
3.1 Tính toán tiến hóa .................................................................................................... 67
3.2 Giải thuật di truyền .................................................................................................. 69
3.3 Giải thuật tối ưu hóa bầy đàn ................................................................................... 74

CHƢƠNG 4 GIẢI THUẬT DI TRUYỀN LAI GIẢI BÀI TOÁN OCST ..... 79
4.1. Mô hình lai ghép đề xuất......................................................................................... 79
4.2. Sơ đồ giải thuật đề xuất ........................................................................................... 80
4.3. Mã hóa cá thể .......................................................................................................... 83
4.3.1. Mã hóa Prufer ....................................................................................................83
4.3.2. Mã hóa NetKeys (Network Random Keys Encoding) ......................................85
4.3.3. Mã hóa CB-TCR ................................................................................................87
4.3.4. Mã hóa NB (Node Biased Encoding) ................................................................90
4.3.5. Mã hóa LB (Link Biased Encoding) ..................................................................91
4.3.6. Mã hóa LNB (Link and Node Biased Encoding) ...............................................92
4.4. Chọn lọc cá thể ........................................................................................................ 94
4.5. Toán tử di truyền ..................................................................................................... 95
4.5.1. Toán tử lai ghép .................................................................................................95
4.5.2. Toán tử đột biến .................................................................................................96

CHƢƠNG 5 KẾT QUẢ THỰC NGHIỆM ....................................................... 97
5.1. Cài đặt thử nghiệm .................................................................................................. 97
5.1.1. Dữ liệu thực nghiệm ..........................................................................................97
5.1.2. Các tham số cho các thử nghiệm .......................................................................99
5.2. Kết quả thực nghiệm ............................................................................................. 100
5.2.1. Kết quả trên các bộ test chuẩn .........................................................................100

5.2.2. Kết quả trên các bộ test ngẫu nhiên .................................................................107
~5~


5.3. So sánh với các thuật toán khác ............................................................................ 108
5.3.1. So sánh với giải thuật tiến hóa (Sang-moon 2006) ..........................................109
5.3.2. So sánh với giải thuật di truyền, mô phỏng tôi luyện, tìm kiếm cục bộ
(Rothlauf 2009) ..........................................................................................................111
5.3.3. So sánh với giải thuật tối ưu hóa bầy đàn (2010) ............................................113

KẾT LUẬN .......................................................................................................... 115
TÀI LIỆU THAM KHẢO .................................................................................. 117

~6~


Danh mục hình vẽ
Hình 1-1 Minh họa thuật toán .................................................................................................. 15
Hình 1-2 Minh họa bài toán chọn lịch xem phim ............................................................. 17
Hình 1-3 Phản ví dụ của thuật toán 1 ................................................................................... 17
Hình 1-4 Phản ví dụ của thuật toán 2 ................................................................................... 17
Hình 1-5 Cận trên và cận dưới để đánh giá cho độ phức tạp của hàm .................. 20
Hình 1-6 Ký hiệu -lớn ............................................................................................................... 21
Hình 1-7 Ký hiệu -lớn ............................................................................................................... 21
Hình 1-8 Ký hiệu -lớn ............................................................................................................... 22
Hình 1-9 Tốc độ tăng theo kích thước đầu vào của một số hàm .............................. 23
Hình 1-10 Mối quan hệ giữa thời gian thực hiện và kích thước đầu vào của một
số lớp hàm ......................................................................................................................................... 24
Hình 1-11 Mối quan hệ giữa 3 lớp bài toán P, NP và Co-NP. ...................................... 32
Hình 1-12 Sơ đồ phép quy dẫn ................................................................................................ 32

Hình 1-13 Minh họa mối quan hệ giữa các lớp bài toán ............................................... 35
Hình 1-14 Danh sách một số bài toán NP-khó và sơ đồ quy dẫn giữa chúng ..... 35
Hình 1-15 Đồ thị vô hướng và đồ thị có hướng ................................................................ 41
Hình 1-16 Danh sách kề và ma trận kề ................................................................................ 44
Hình 2-1 Minh họa cách tính giá cây khung trong bài toán OCST ............................ 47
Hình 2-2 Minh họa bài toán SROCT và PROCT ................................................................. 48
Hình 2-3 Các biến thể của bài toán cây khung truyền thông tối ưu tổng quát ... 49
Hình 2-4 Minh họa cách tính độ trễ của cặp đỉnh ............................................................ 50
Hình 2-5 Một cây khung 3-star, trong đó B,C,E là các nút trong và A,D,E,F,G,H,I
là các nút lá ....................................................................................................................................... 51
Hình 2-6 Cây khung 1-star, với B là nút trong và các nút còn lại là nút lá ........... 51
Hình 2-7 Thiết kế mạng truyền thông .................................................................................. 56
Hình 2-8 Thủ tục xây dựng cây – tree building ................................................................ 60
~7~


Hình 2-9 Thủ tục cải tiến cây – tree improvement ......................................................... 61
Hình 2-10 Cấu trúc của thuật toán Memetic ...................................................................... 64
Hình 3-1 Mô hình một thuật toán tiến hóa ......................................................................... 68
Hình 3-2 Minh họa Allele, Gen và nhiễm sắc thể.............................................................. 69
Hình 3-3 Sơ đồ chung của thuật toán di truyền ............................................................... 71
Hình 3-4 Bài toán tối ưu có thể có rất nhiều cực trị ....................................................... 73
Hình 3-5 Mô tả giải thuật PSO .................................................................................................. 76
Hình 3-6 Mô tả giải thuật PSO .................................................................................................. 78
Hình 4-1 Sơ đồ giải thuật di truyền lai đề xuất ................................................................. 82
Hình 4-2 Giải thuật mã hóa cây khung thành chuỗi Prufer ......................................... 83
Hình 4-3 Cây khung được mã hóa bởi chuỗi Prufer 2565 ........................................... 84
Hình 4-4 Giải thuật giải mã cây khung từ một chuỗi Prufer ....................................... 85
Hình 4-5 Giải thuật xây dựng cây khung từ chuỗi NetKeys ........................................ 86
Hình 4-6 Cây thu được theo mã hóa NetKeys ................................................................... 87

Hình 4-7 Giải thuật xây dựng cây khung từ một chuỗi CB-TCR ................................ 88
Hình 4-8 Đồ thị minh họa cho mã hóa CB-TCR................................................................. 89
Hình 4-9 Cây khung sinh ra từ chuỗi CB-TCR (1,5,2,1,4,3,2,5) ................................. 90
Hình 4-10 Giải thuật Prim .......................................................................................................... 91
Hình 4-11 Cây khung thu được từ mã hóa LNB ............................................................... 94
Hình 4-12 Mô tả phương pháp chọn lọc theo vòng quay Roulette .......................... 94
Hình 4-13 Các bước trong phương pháp chọn lọc theo vòng quay Roulette ...... 95
Hình 4-14 Minh họa phương pháp lai ghép một điểm cắt........................................... 95
Hình 4-15 Minh họa phương pháp lai ghép đồng bộ ..................................................... 96
Hình 5-1 So sánh tốc độ hội tụ khi sử dụng hai mã hóa CB-TCR và NB .............. 105
Hình 5-2 So sánh kết quả tìm được bởi hai toán tử lai ghép trên bộ Raidl100
............................................................................................................................................................. 106

~8~


Hình 5-3 So sánh tốc độ hội tụ của giải thuật với hai loại lai ghép trên bộ
Raidl100 .......................................................................................................................................... 106
Hình 5-4 So sánh tốc độ hội tụ của giải thuật trên bộ test NE-RAND-200 ........ 107
Hình 5-5 So sánh tốc độ hội tụ của giải thuật trên bộ test E-RAND-200 ........... 108

~9~


Danh mục bảng
Bảng 1-1 Mối tương quan giữa quá trình tiến hóa và tính toán tiến hóa ..................40
Bảng 2-1 Các bài toán OCT và tỉ lệ xấp xỉ tốt nhất hiện biết của nó .......................54
Bảng 4-1 Chuỗi NetKeys cùng nhãn của các cạnh trong đồ thị ...............................86
Bảng 5-1 Các bộ test chuẩn .......................................................................................98
Bảng 5-2 Kết quả chạy các bộ test chuẩn sử dụng mã hóa Prufer và CB-TCR......101

Bảng 5-3 Kết quả chạy các bộ test chuẩn sử dụng mã hóa NetKeys và NB ..........102
Bảng 5-4 Kết quả chạy trên các bộ test chuẩn sử dụng mã hóa LNB và LB ..........103
Bảng 5-5 So sánh về độ lệch của kết quả tìm được so với kết quả đã biết .............109
Bảng 5-6 So sánh thời gian tìm ra kết quả tốt nhất .................................................110
Bảng 5-7 So sánh số lượng thế hệ tối thiểu để tìm ra kết quả tốt nhất ..................111
Bảng 5-8 So sánh với một số giải thuật meta-heuristic ..........................................112
Bảng 5-9 So sánh với giải thuật tối ưu hóa bầy đàn ...............................................114

~ 10 ~


Danh mục thuật ngữ tiếng Anh
STT

Thuật ngữ

Viết tắt

Đề nghị dịch tiếng Việt

1

Approximation scheme

Mô hình xấp xỉ

2

Probabilistic method


Phương pháp xác xuất

3

Evolutionary computation

Tính toán tiến hóa

4

Local search

Tìm kiếm cục bộ

5

Genetic algorithm

6

Hybrid GA

7

Bin packing problem

GA

Thuật toán di truyền lai
BPP


Bài toán đóng thùng
Đảm bảo về tỷ số chênh lệch

8
Relative performance ration

tương đối

9

Absolute performance guarantee

10

Polynomial time approximation
schemes

Thuật toán di truyền

Đảm bảo về sai số tuyệt đối
PTAS

Sơ đồ xấp xỉ trong thời gian
đa thức

11

Population


Quần thể

12

Chromosomes

Nhiễm sắc thể

13

Individual

Cá thể

14

Genetic-inspired operators

Toán tử di truyền

15

Selection

Chọn lọc tự nhiên

16

Crossover


Lai ghép

17

Mutation

đột biến

18

Inversion

Đảo chỗ

19

Fitness

Độ thích nghi

20

Object function

Hàm mục tiêu

~ 11 ~


21


Generation

Thế hệ
Cơ chế lựa chọn theo bánh xe

22
Roulette wheel selection

Roulette

23

K-point crossover

Lai ghép k-điểm cắt

24

Uniform crossover

Lai ghép đồng bộ

25

Order-based crossover

Lai ghép theo thứ tự

26


Uniform order-based crossover

Lai ghép đồng bộ theo thứ tự

27

Optimal Communication

OCST

Spanning Tree
28

Minimum Routing Cost Spanning
Tree

29

Optimal Product Requirement
Communication Spanning Tree

30

Optimal Sum Requirement
Communication Spanning Tree

31
p-Source OCT
32


Minimum Average Stretch
Spanning Tree

MRCT

PROCT

SROCT

Cây khung truyền thông tối
ưu
Cây khung định tuyến tối
thiểu
Cây khung truyền thông tích
nhu cầu
Cây khung truyền thông tổng
nhu cầu

p-Source Cây khung truyền thông tối
OCT
MAST

ưu p nguồn
Cây khung tối thiểu khoảng
giãn

33

Particle Swarm Optimization


PSO

Tối ưu hóa bầy đàn

34

Swarm Intelligence

SI

Bầy đàn thông minh

~ 12 ~


CHƢƠNG 1
CÁC KHÁI NIỆM CƠ BẢN
Chương này trình bày tổng quan về các khái niệm và các thuật ngữ cơ sở được sử
dụng trong luận văn. Các khái niệm và thuật ngữ được trình bày dựa trên các tài
liệu [10] [22] [23] [32] [38].

1.1. Thuật toán và đánh giá độ phức tạp của thuật toán
1.1.1 Khái niệm thuật toán
Ngày nay máy tính đã trở thành một công cụ sản xuất quan trọng, một thiết bị
không thể thiếu trong bất cứ lĩnh vực nào. Nó được sử dụng để trực tiếp giải quyết,
hoặc để hỗ trợ con người trong việc giải quyết các vấn đề trong thực tế. Do vậy việc
nghiên cứu lý thuyết về khoa học máy tính và các vấn đề về giải quyết bài toán
bằng máy tính ngày càng quan trọng và được phát triển mạnh mẽ.
Các vấn đề xuất phát từ trong thực tế hằng ngày rất đa dạng, có thể là các vấn đề

đơn giản cũng có thể là các vấn đề mà không thể giải quyết được. Nhưng cho dù
vấn đề là gì đi nữa để giải quyết nó bao giờ cũng vậy, trước hết chúng ta cần phát
biểu lại vấn đề đó một cách chính xác dưới dạng các bài toán. Dưới dạng một bài
toán thì một vấn đề sẽ gồm có đầu vào và đầu ra, trong đó đầu vào mô tả không
gian các giá trị có thể có của bài toán và đầu ra là giá trị mong muốn tương ứng với
đầu vào đó.
Ví dụ: bài toán sắp xếp được định nghĩa như sau
Đầu vào: một dãy gồm

khóa

Đầu ra: một hoán vị của dãy khóa đầu vào thỏa mãn
~ 13 ~


Như vậy dãy đầu vào có thể là dãy số bất kỳ, hoặc có thể là dãy các xâu ký tự, hoặc
là dãy các đối tượng…
Ở đây chúng ta chỉ đề cập đến việc giải quyết bài toán bằng máy tính. Để giải quyết
bài toán bằng máy tính trước hết chúng ta phải biểu diễn được bài toán đó trên máy
tính, tức là biểu diễn được đầu vào và đầu ra của nó. Trong máy tính tất cả các dữ
liệu và câu lệnh đều được biểu diễn dưới dạng mã nhị phân (biểu diễn bằng các
chuỗi nhị phân gồm bit 1 và 0).
Ví dụ:
 Một số nguyên được biểu diễn dưới dạng chuỗi bit sử dụng mã bù 2 (nếu là
kiểu số nguyên có dấu) hoặc là sử dụng số trong hệ nhị phân tương ứng (nếu
là số nguyên không dấu).
 Một số thực được biểu diễn trong máy tính dưới dạng chuỗi bit nhị phân sử
dụng chuẩn IEEE-754.
 Một kí tự được biểu diễn bằng số thứ tự (dưới dạng mã nhị phân) của nó
trong bảng mã nào đó như bảng mã ASCII, Unicode …

 Một xâu kí tự được biểu diễn là ghép nối biểu diễn của các kí tự thành phần
của xâu đó.
 Một vector được biểu diễn là ghép nối biểu diễn nhị phân (mảng – array) của
các thành phần tọa độ của các chiều.
 Một ma trận được biểu diễn bởi ghép nối các biểu diễn của các vector thành
phần hoặc ma trận thành phần cấp thấp hơn nó một đơn vị.
 Một hệ phương trình tuyến tính dạng

có thể biểu diễn dưới dạng

nhị phân là ghép nối của các xâu biểu diễn nhị phân của các thành phần trong
ma trận A và vector b.
 Đa thức một biến dạng
dãy các hệ số

,

,…,

được đặc trưng bởi
và số mũ . Do đó có thể dùng các xâu nhị phân
~ 14 ~


biểu diễn dãy hệ số

và xâu nhị phân biểu diễn

là ta có thể tạo thành một


biểu diễn hợp lệ cho P(x).
 Đồ thị có thể được biểu diễn bằng ma trận kề, hoặc danh sách kề
 Các dữ liệu phức hợp được tổ chức dưới dạng tổ hợp cấu trúc của các dữ liệu
cơ bản, ví dụ như mảng, bản ghi, cây …
Như vậy chúng ta có thể định nghĩa một cách hình thức bài toán tính toán như sau:
Định nghĩa 1.1. Bài toán tính toán F là ánh xạ từ các xâu nhị phân độ dài hữu hạn
vào tập các xâu nhị phân độ dài hữu hạn: F: {0,1}* → {0,1}*.
Các dữ liệu trong bài toán tổng quát có thể không hữu hạn, tuy nhiên khi đã chuyển
vào trong máy tính thì chúng ta phải chuyển nó thành hữu hạn, bởi vì không gian
của máy tính là hữu hạn. Nói một cách khác các xâu nhị phân biểu diễn bài toán có
độ dài là hữu hạn.
Để giải quyết bài toán (vấn đề trong thực tế) chúng ta phải đề xuất ra một phương
án. Trong giải quyết bài toán bằng máy tính phương án được gọi là thuật toán
(algorithm). Một thuật toán để giải quyết bài toán có thể được định nghĩa như sau.
Định nghĩa 1.2. Thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm một
dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước
của bài toán.
Đầu vào
(Input)

Đầu ra
(Output)
Thuật toán
(Algorithm)

Hình 1-1 Minh họa thuật toán
Thuật toán có những đặc trưng sau đây:
 Có đầu vào (Input): là tập các dữ liệu cần cung cấp cho thuật toán để xử lý.

~ 15 ~



 Có đầu ra (Output): với mỗi một bộ dữ liệu vào, thuật toán sẽ cho ra một bộ
các dữ liệu ra tương ứng với lời giải của bài toán cho bộ dữ liệu vào.
 Chính xác (Precision): Các bước của thuật toán cần phải được mô tả chính
xác và rõ ràng để có thể cài đặt được trên máy tính và có thể thực hiện được.
 Hữu hạn (Finiteness): với mọi đầu vào thuật toán phải đưa được đầu ra sau
một số hữu hạn (có thể rất lớn) bước thực hiện.
 Đơn trị (Uniqueness): các kết quả trung gian trong quá trình thực hiện thuật
toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào cũng như
kết quả ở những bước trước.
 Tổng quát (Generality): thuật toán có thể áp dụng để giải mọi bài toán có
dạng đã cho.
Hai tính chất quan trọng nhất của thuật toán là tính chính xác và tính hiệu quả. Tính
chính xác của thuật toán không phải lúc nào cũng dễ thấy
Ví dụ: Bài toán chọn lịch xem phim. Trong một đợt liên hoan phim, có

bộ phim

khác nhau được trình chiếu tại nhiều phòng chiếu khác nhau. Là một người yêu
nghệ thuật thứ 7, một giáo sư muốn xem được nhiều nhất các phim có thể. Đối với
ông các phim có mức độ hấp dẫn là như nhau, và ông muốn xem các bộ phim một
cách đầy đủ (tức là thời gian xem bộ phim này không bị giao với thời gian xem bộ
phim khác của ông). Hãy giúp giáo sư chọn ra danh sách lớn nhất các bộ phim có
thể xem được. Bài toán này có thể được phát biểu lại như sau:
Đầu vào: Một tập L gồm thời gian chiếu (thời điểm bắt đầu và kết thúc) trong ngày
của

bộ phim


Đầu ra: Tập con của L chứa số bộ phim lớn nhất có thể xem (không được giao nhau
về thời gian)
Để đơn giản có thể biểu diễn các bộ phim dưới dạng các đoạn thẳng không giao
nhau như hình bên dưới. Trong đó P1, P2, và P3 là các phòng chiếu

~ 16 ~


P1
P2
P3

Hình 1-2 Minh họa bài toán chọn lịch xem phim
Thuật toán 1. Chọn bộ phim có thời điểm bắt đầu sớm nhất trong L mà có thời gian
không bị giao với các bộ phim đã chọn trước đó. Lặp lại cho đến khi không thể
chọn thêm.
Với thuật toán này ta có thể đưa ra một ví dụ chỉ ra thuật toán (phản ví dụ) sai như
sau
P1
P2

Hình 1-3 Phản ví dụ của thuật toán 1
Thuật toán 2. Chọn bộ phim có thời gian chiếu ngắn nhất trong L mà có thời gian
không bị giao với các bộ phim đã chọn trước. Lặp lại cho đến khi không chọn thêm
được.
Với thuật toán 2 ta có thể chỉ ra một phản ví dụ

P1
P2


Hình 1-4 Phản ví dụ của thuật toán 2
Thuật toán 3. Duyệt toàn bộ: duyệt

tập con của n bộ phim trong L. Chọn ra tập

con nào có số lượng phần tử lớn nhất. Đảm bảo thu được kết quả tối ưu. Thuật toán
chạy rất chậm, vd

số tập con là 220

~ 17 ~


Thuật toán 4. Thuật toán tối ưu: sắp xếp các lịch chiếu phim theo thứ tự không giảm
thời điểm kết thúc. Lần lượt xem xét các phim trong danh sách đã sắp xếp, bổ sung
vào danh sách xem bộ phim đang xét nếu nó không chồng lên các bộ phim đã có
trong danh sách xem.
Để chỉ ra thuật toán là không chính xác ta chỉ cần đưa ra một phản ví dụ của thuật
toán. Tuy nhiên chưa chỉ ra được một phản ví dụ của thuật toán không có nghĩa là
thuật toán chính xác. Để chứng minh một thuật toán là chính xác ta phải chứng
minh bằng toán học. Có những bài toán mà không tồn tại thuật toán chính xác để
giải!
Với một bài toán có thể tồn tại rất nhiều thuật toán để giải, mỗi thuật toán nó cần sử
dụng lượng tài nguyên máy tính khác nhau. Chúng ta đánh giá hiệu quả của thuật
toán thông qua lượng tài nguyên mà nó cần để tìm ra lời giải cho bài toán. Tất nhiên
là chúng ta chỉ đánh giá hiệu quả của những thuật toán chính xác. Các tài nguyên
máy tính mà chúng ta xét đến ở đây là thời gian CPU (để thực hiện thuật toán thì
CPU cần thực hiện lệnh của nó), dung lượng bộ nhớ cần dùng, và các tài nguyên
khác như ổ cứng, mạng,… Trong đó thời gian CPU và bộ nhớ là hai tài nguyên
quan trọng nhất. Ngày nay với sự phát triển mạnh của công nghệ bán dẫn nên giá

thành bộ nhớ máy tính giảm nhanh chóng, vì thế tài nguyên thời gian CPU được
đánh giá quan trọng hơn. Mặc dù công nghệ chế tạo CPU cũng phát triển rất nhanh.
Theo định luật Moore ―máy tính sẽ tăng gấp đôi khả năng tính toán với cùng mức
giá hoặc giảm giá chỉ còn một nửa với cùng khả năng tính toán cứ sau 18 tháng‖.
Tuy nhiên khi thực hiện trên đầu vào với kích thước đủ lớn thì thuật toán hiệu quả
hơn dù được thực hiện trên máy tính tốc độ chậm vẫn luôn chiến thắng thuật toán
tồi hơn nhưng được thực hiện trên máy tính có tốc độ nhanh hơn. Vì thế để đánh giá
hiệu quả của các thuật toán người ta thường căn cứ vào thời gian thực hiện của thuật
toán.

~ 18 ~


1.1.2. Đánh giá thuật toán
Một vấn đề được đặt ra ở đây là thời gian thực hiện thuật toán trên máy tính phụ
thuộc vào rất nhiều yếu tố như tốc độ CPU, bộ nhớ, thời điểm chạy chương trình ...
do đó không thể đánh giá thời gian thực hiện thuật toán bằng thời gian trên máy
tính, và cũng không thể dùng thời gian này để so sánh hiệu quả của các thuật toán
được. Có hai mô hình đánh giá thời gian thuật toán hay sử dụng trong thực tế là mô
hình RAM và O-lớn.
Mô hình RAM: Thực hiện thuật toán trên một máy tính giả định gọi là Random
Access Machine hoặc RAM.
 Mỗi phép tính đơn giản (+, *, –, =, if, call) thực hiện trong 1 đơn vị thời gian
(hoặc 1 bước).
 Vòng lặp, hàm, thủ tục: là kết hợp của nhiều phép tính đơn lẻ
 Mỗi bước truy cập bộ nhớ mất 1 đơn vị thời gian
 Luôn có đủ bộ nhớ cần thiết để thực hiện thuật toán
Thời gian thực hiện của thuật toán phụ thuộc vào đầu vào của bài toán. Các trường
hợp đầu vào khác nhau thời gian thực hiện khác nhau. Khi đánh giá thời gian thực
hiện thuật toán, người ta chia thành 3 loại là

 Độ phức tạp trong trường hợp tồi nhất (worst-case complexity): Là số lượng
bước lớn nhất thuật toán cần thực hiện với bất cứ đầu vào kích thước

nào.

 Độ phức tạp trong trường hợp tốt nhất (best-case complexity): Là số lượng
bước nhỏ nhất thuật toán cần thực hiện với bất cứ đầu vào kích thước

nào.

 Độ phức tạp trong trường hợp trung bình (average-case complexity): Là số
lượng bước trung bình thuật toán cần thực hiện trên tất cả các trường hợp
đầu vào kích thước .
Trong 3 đánh giá độ phức tạp trên đánh giá trong trường hợp tồi nhất là đánh giá
quan trọng nhất.
~ 19 ~


Trong mô hình RAM chúng ta đánh giá thời gian thực hiện thuật toán bằng cách
đếm số đơn vị thời gian cần. Ưu điểm của mô hình này là đơn giản, tuy nhiên việc
đếm số đơn vị thời gian cần không phải lúc nào cũng đơn giản. Trong một số trường
hợp việc này gần như là không thể bởi vì hàm thời gian thực hiện là hàm có rất
nhiều điểm lồi, và để xác định nó một cách chính xác ta cần phân tích rất tỉ mỉ. Hơn
nữa theo mô hình RAM thời gian thực hiện của thuật toán thường có dạng đa thức

Trong đó

là kích thước đầu vào của dữ liệu. Chúng ta nhận thấy là thời gian thực

hiện thuật toán phụ thuộc rất nhiều số hạng, nhưng số hạng có số mũ cao nhất trong

đó là thành phần có yếu tố quan trọng nhất. Nó quyết định chính đến tốc độ tăng
thời gian thực hiện của thuật toán.

Hình 1-5 Cận trên và cận dưới để đánh giá cho độ phức tạp của hàm
Phân tích O-lớn: trong mô hình phân tích này chúng ta đơn giản phân tích trong mô
hình RAM, bỏ bớt những thành phần ít ảnh hưởng đến thời gian thực hiện của thuật
toán khi so sánh các thuật toán với nhau.
~ 20 ~


Ví dụ trong O-lớn thì

là như nhau

và

được dùng để phân tích độ phức tạp của thuật toán

Các ký hiệu tiệm cận
trong thực tế.
 Kí hiệu
số dương

biểu diễn tập các hàm
và

sao cho

cận trên tiệm cận của
 Kí hiệu

số dương

và

 Kí hiệu
số dương

hay

.}. Ta nói

={

là

: tồn tại các hằng

, với mọi

hay

.}. Ta nói

có bậc ít nhất là

biểu diễn tập các hàm

cận

.

={

: tồn tại các hằng

sao cho

, với mọi

là đánh giá tiệm cận đúng của

hay

có bậc là

là các hằng số dương không phụ thuộc vào , và

Hình 1-7 Ký hiệu 𝛰-lớn

Hình 1-6 Ký hiệu 𝛺-lớn

Ví dụ


.}. Ta nói

có bậc không quá

sao cho

và


: tồn tại các hằng

, với mọi

biểu diễn tập các hàm

dưới tiệm cận của

Với

={

vì chọn
~ 21 ~

thì




vì chọn



thì

khi

vì với bất kỳ hằng số c nào thì

khi



vì chọn



vì với bất kỳ giá trị
khi

đủ lớn (

nếu



thì

,

khi

thì
nếu

vì với bất kỳ hằng số c nào thì
khi




vì cả



vì chỉ



vì chỉ

đều đúng
đúng
đúng

Hình 1-8 Ký hiệu -lớn
Như vậy để chứng minh
•

(

cần chỉ ra
)
~ 22 ~

)


•
Các lớp hàm thông dụng:

 Hàm hằng

. Thời gian thực hiện là hằng số VD hàm tính tổng 2 số

 Hàm loga

. VD tìm kiếm nhị phân

 Hàm tuyến tính

. VD Tìm giá trị lớn nhất trong dãy số

 Hàm siêu tuyến tính

. VD QuickSort, MergeSort

 Hàm bậc hai
 Hàm bậc ba
 Hàm mũ

. VD Sắp xếp nổi bọt (bubble sort )
.
, là hằng số >1.

 Hàm giai thừa

Hình 1-9 Tốc độ tăng theo kích thước đầu vào của một số hàm
Hình 1-9 và 1-10 minh họa tốc độ tăng và thời gian thực hiện của một số lớp hàm
thông dụng.
Mối quan hệ giữa các ký hiệu tiệm cận và các mô hình đánh giá:


~ 23 ~


 Thời gian tính là
là

‖. Nghĩa là thời gian tính trong tình huống tồi nhất được xác định

bởi một hàm
 Thời gian tính là
là
một hàm

được hiểu là : ―đánh giá trong tình huống tồi nhất
nào đó.
được hiểu là : ―đánh giá trong tình huống tốt nhất

‖. Nghĩa là thời gian trong tình huống tốt nhất được xác định bởi
nào đó.

Hình 1-10 Mối quan hệ giữa thời gian thực hiện và kích thước đầu vào của một số
lớp hàm

1.2. Độ phức tạp tính toán của bài toán
1.2.1. Khái niệm về độ phức tạp của bài toán
Như đã biết, đối với một bài toán có thể có nhiều thuật toán khác nhau để giải. Mỗi
thuật toán có độ phức tạp tính toán khác nhau. Một câu hỏi được đặt ra là độ phức
tạp tính toán của các thuật toán có liên quan gì đến bài toán không? Hay nói cách
khác có phải bài toán nào cũng khó như nhau không? Câu trả lời là không. Mỗi bài

toán nó có một mức độ khó khác nhau và được đặc trưng bởi độ phức tạp tính toán
của thuật toán tốt nhất trong số tất cả các thuật toán có thể để giải nó.
Định nghĩa 1.3. Độ phức tạp tính toán của một bài toán là thời gian của thuật toán
tốt nhất trong số tất cả các thuật toán có thể để giải bài toán đó.

~ 24 ~