MỤC LỤC
MỤC LỤC ....................................................................................................................... 1
DANH MỤC TỪ VIẾT TẮT........................................................................................ 4
DANH MỤC BẢNG BIỂU........................................................................................... 5
DANH MỤC HÌNH ẢNH............................................................................................. 6
LỜI MỞ ĐẦU ................................................................................................................. 8
CHƢƠNG 1. GIỚI THIỆU ........................................................................................... 9
1.1. Mục tiêu và kết quả của Luận văn .................................................................... 9
1.1.1. Mục đích ........................................................................................................ 9
1.1.2. Kết quả ........................................................................................................... 9
1.2. Các ký hiệu toán học.........................................................................................10
1.3. Mạng lƣới, hệ thống trong thực tế và lý thuyết đồ thị ..................................10
1.3.1. Lý thuyết đồ thị...........................................................................................11
1.3.2. Mạng lƣới, hệ thống trong thực tế ............................................................15
CHƢƠNG 2. TỔNG QUAN BÀI TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT.......17
2.1. Bài toán tìm đƣờng đi ngắn nhất .....................................................................17
2.2. Lịch sử phát triển bài toán tìm đƣờng đi ngắn nhất và kết quả ...................18
2.3. Ứng dụng của bài toán tìm đƣờng đi ngắn nhất ............................................21
2.3.1. GPS...............................................................................................................21
2.3.2. Phân tích và xử lý ảnh................................................................................22
2.3.3. Công c ụ tìm kiếm qua mạng Internet (Social Search) ...........................23
2.3.4. Tìm kiếm trong mạng xã hội (Social Network Search) .........................23
2.3.5. Hệ thống tin nhắn .......................................................................................24
2.4. Kỹ nghệ thuật toán ............................................................................................25
2.4.1. Giới thiệu .....................................................................................................25
2.4.2. Nền tảng của kỹ nghệ thuật toán ..............................................................34
CHƢƠNG 3. CÁC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN SSSP KINH
ĐIỂN ..............................................................................................................................39
3.1. Hàng đợi ƣu tiên và các c ấu trúc Đống ..........................................................39
1

3.1.1. Hàng đợi ƣu tiên (Priority queue).............................................................39
3.1.2. Đống nhị phân .............................................................................................40
3.1.2. D- Heap (Đống D) ......................................................................................41
3.1.3. Đống Fibonacci (FibonacciHeap).............................................................41
3.3. Thuật toán Dijkstra............................................................................................43
3.3.1. Thuật toán Dijkstra cổ điển .......................................................................43
3.3.2. Các biến thể của thuật toán Dijkstra ........................................................44
3.3.3. Cải tiến thuật toán Dijkstra bằng hàng đợi ƣu tiên.................................49
CHƢƠNG 4. THUẬT TOÁN THORUP ..................................................................52
4.1. So sánh với thuật toán Dijkstra........................................................................52
4.2. Các cấu trúc dữ liệu và cách thức thực hiện nhằm xây dựng thuật toán ....55
4.2.1. Minimum Spanning Tree ...........................................................................55
4.2.2. Thuật toán Tarjan’s union-find .................................................................56
4.2.3. Gabow’s split-findmin Algorithm ............................................................58
4.2.4. Cây phân tầng (Component hierarchy - T)..............................................58
4.2.5. Cấu trúc Bucket và Cấu trúc Unvisited Data ..........................................66
4.2.6. Thuật toán thăm nút thành phần và các đỉnh ..........................................68
4.3. Cải tiến thuật toán Thorup................................................................................70
4.4. Ví dụ minh họa thuật toán Thorup ..................................................................71
4.4.1. Ví dụ về Cây khung nhỏ nhất: ..................................................................71
4.4.2. Ví dụ về xây dựng cây phân tầng: ............................................................71
4.4.3. Ví dụ về Bucket B.......................................................................................72
4.4.4. Ví dụ về Unvisited Structure (U) ..............................................................73
4.4.5. Ví dụ về thuật toán thăm các đỉnh của giải thuật Thorup......................75
CHƢƠNG 5. ĐÁNH GIÁ THỰC NGHIỆM CÁC THUẬT TOÁN .....................77
5.1. Mục đích thực nghiệm và các thuật toán đƣợc lựa chọn..............................77
5.1.1. Mục đích ......................................................................................................77
5.1.2. Các thuật toán .............................................................................................77
5.2. Ngôn ngữ lập trình, môi trƣờng thực nghiệm và Bộ dữ liệu thực nghiệm 78


2


5.2.1. Ngôn ngữ lập trình và môi trƣờng thực nghiệm .....................................78
5.2.2. Bộ dữ liệu thực nghiệm .............................................................................78
5.3. Mô tả cài đặt các thuật toán .............................................................................81
5.4. Kết quả thực nghiệm .........................................................................................83
5.5. Phân tích kết quả ...............................................................................................91
5.5.1. Thời gian chạy và Bộ nhớ sử dụng...........................................................91
5.5.2. Khả năng sử dụng lại bộ dữ liệu đã xây dựng của thuật toán Thorup và
Thorup WeiYusi ....................................................................................................92
5.6. Kết luận ..............................................................................................................95
TÀI LIỆU THAM KHẢO ...........................................................................................97

3


DANH MỤC TỪ VIẾT TẮT

DIJ: Thuật toán Dijkstra.
DIJ B: Thuật toán Dijkstra sử dụng đống nhị phân.
DIJ F: Thuật toán Dijkstra sử dụng đống Fibonacci.
SSSP: Single shortest path problem.
TR: Thuật toán Thorup.
TRWY: Thuật toán Thorup WeiYusi.
RAM: Random Access Machine.

4



DANH MỤC BẢNG BIỂU
Chương 2:
Bảng 2. 1.Thời gian chạy các thuật toán SSSP sắp xếp theo năm. ........................21
Chương 3:
Bảng 3.1.Thời gian thực hiện của đống nhị phân, đống Fibonaccis, và Đống D.40
Bảng 3.2. Thời gian chạy của đống nhị phân. ..........................................................41
Bảng 3. 3. Thời gian chạy của đống D. .....................................................................41
Bảng 3.4. Thời gian chạy của đống Fibonacci. ........................................................43
Bảng 3.5. Đánh giá độ phức tạp của Dijkstra khi áp dụng đống............................51
Chương 5:
Bảng 5.1. Các thuật toán đƣợc lựa chọn thực nghiệm. ...........................................77
Bảng 5.2. Dữ liệu đồ thị có sẵn. .................................................................................79
Bảng 5.3. Dữ liệu đồ thị với mật độ m=3n ...............................................................79
Bảng 5. 4. Dữ liệu đồ thị với mật độ m=6n ..............................................................79
Bảng 5. 5. Dữ liệu đồ thị với mật độ m=10n ............................................................79
Bảng 5. 6. Dữ liệu đồ thị với mật độ m=nloglogn ...................................................80
Bảng 5.7. Dữ liệu đồ thị với mật độ m=nlogn..........................................................80
Bảng 5.8. Dữ liệu đồ thị với mật độ m=n*(n-1)/2. ..................................................80
Bảng kết quả:
Bảng 5.R1. Dữ liệu đầu vào sẵn có - DIMACS .......................................................84
Bảng 5.R2. Mật độ đồ thị m=3n ................................................................................85
Bảng 5.R3. Mật độ đồ thị m=6n. ...............................................................................86
Bảng 5.R4. Mật độ đồ thị m=10n ..............................................................................87
Bảng 5.R5. Mật độ đồ thị m=nloglogn .....................................................................88
Bảng 5.R6. Mật độ đồ thị m=nlogn ...........................................................................89
Bảng 5.R7. Mật độ đồ thị m=
........................................................................90
Bảng 5.R 8. Bảng kết quả thời gian tìm kiếm với đỉnh nguồn s từ 1 đến 100 của
các thuật toán.................................................................................................................93

Bảng 5.R 9. So sánh khi sử dụng lại và xây dựng lại dữ liệu của thuật toán
Thorup và Thorup WeiYusi. .......................................................................................94

5


DANH MỤC HÌNH ẢNH
Chương 1:
Hình 1. 1. Bảy cây cầu Königsberg. ..........................................................................11
Hình 1. 2.Hình ảnh mô tả cấu trúc đồ thị..................................................................12
Hình 1. 3.Hình ảnh mô tả cấu trúc đồ thị..................................................................13
Hình 1. 4.Hình ảnh mô tả cấu trúc đồ thị phẳng. .....................................................14
Chương 2:
Hình 2. 1.Kỹ nghệ thuật toán. ....................................................................................33
Chương 4:
Hình 4. 1. Hình ảnh mô tả Bổ đề Thorup. ................................................................53
Hình 4. 2. Hình ảnh mô tả Bổ đề Thorup với các cạnh nối đồ thị con ≥ 3...........54
Hình 4. 3. Thuật toán Tarjan union find. ..................................................................57
Hình 4. 4. Hình ảnh mô tả định nghĩa 2. ...................................................................60
Hình 4. 5. Đồ thị hoàn chỉnh. .....................................................................................61
Hình 4.6. Cây phân tầng xây dựng từ đồ thị. ...........................................................61
Hình 4. 7. Hình minh họa min - child. ......................................................................64
Hình 4. 8.Mô tả về cấu trúc split - findmin. .............................................................68
Hình 4. 9. Ví dụ về MST.............................................................................................71
Hình 4. 10. Ví dụ về cây phân tầng ...........................................................................72
Hình 4. 11. Ví dụ về cây phân tầng ...........................................................................72
Hình 4. 12. Ví dụ về Bucket. ......................................................................................73
Hình 4. 13. Ví dụ về phép thăm .................................................................................76
Hình 4. 14. Ví dụ về phép thăm .................................................................................76
Chương 5:

Hình 5.1. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị sẵn
có. ...................................................................................................................................84
Hình 5. 2. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị
m=3n. .............................................................................................................................85

6


Hình 5.3. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị dữ
liệu m=6n. ......................................................................................................................86
Hình 5.4. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị dữ
liệu m=10n.....................................................................................................................87
Hình 5.5. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị dữ
liệu m=nloglogn............................................................................................................88
Hình 5. 6. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị dữ
liệu m = nlogn. ..............................................................................................................89
Hình 5.7. Đồ thị thể hiện thời gian chạy t của các thuật toán trên các đồ thị dữ
liệu m =
. ............................................................................................................90
Hình 5. 8. Đồ thị thời gian tìm kiếm với đỉnh nguồn từ 1 – 100 của thuật toán
Thorup. ...........................................................................................................................93
Hình 5. 9. Đồ thị thời gian tìm kiếm với đỉnh nguồn từ 1 – 100 của thuật toán
Thorup – WeiYusi. .......................................................................................................94

7


LỜI MỞ ĐẦU
Bài toán tìm đƣờng đi ngắn nhất (Shortest Path Problem) là một trong
những bài toán kinh điển nhất trong tối ƣu hoá đồ thị đã và và đang tiếp tục đƣợc

nghiên cứu nhằm đáp ứng tốt hơn các yêu cầu cụ thể của thực tiễn. Có rất nhiều
vấn đề trong thực tế thúc đẩy các nghiên cứu về tìm đƣờng đi ngắn nhất.
Việc tìm đƣờng đi ngắn nhất giữa các địa điểm nhằm xây dựng hệ thống
giao thông công cộng là một ví dụ điển hình nhằm thúc đẩy việc nghiên cứu các
vấn đề liên quan. Hãy hình dung là bạn muốn đi từ thành phố Hà Nội sang khu
vực nào đó thuộc thành phố Nagoya - Nhật Bản, con đƣờng đi sẽ nhƣ thế nào?
Bạn muốn liên lạc một ngƣời nào đó thông qua sự giới thiệu của bạn bè và bạn
của bạn bè qua mạng xã hội? Hoặc khi truy cập một trang Web trên Internet, bạn
sẽ sử dụng cách nào để có thể tải đƣợc các thông tin cần thiết một cách nhanh
nhất?
Mục đích của luận văn này là trình bày lại một cách hệ thống các thuật
toán giải bài toán đƣờng đi ngắn nhất trên đồ thị, đặc biệt đi sâu vào thuật toán
Thorup và phiên bản cải tiến bởi Wei Yusi của nó. Các kết quả khảo sát thực
nghiệm các thuật toán đƣợc trình bày giúp đƣa ra những hƣớng dẫn sử dụng các
thuật toán trong việc áp dụng giải quyết những vấn đề nảy sinh trong thực tiễn.
Luận văn đƣợc trình bày trong 5 chƣơng.
Chƣơng 1 đề cập tới mục tiêu và kết quả hƣớng tới của Luận văn cũng
nhƣ các ký hiệu toán học và một số khái niệm cở bản của lý thuyết đồ thị có liên
quan đến bài toán đƣờng đi ngắn nhất.
Các định nghĩa, lịch sử phát triển, các ứng dụng của bài toán đƣờng đi
ngắn nhất và sơ lƣợc về kỹ nghệ thuật toán đƣợc trình bày trong chƣơng 2.
Chƣơng 3 dành cho việc trình bày về các thuật toán kinh điển và các cấu
trúc dữ liệu thƣờng sử dụng trong cài đặt các thuật toán đƣờng đi ngắn nhất.
Chƣơng 4 giới thiệu chi tiết thuật toán Thorup [19] và phiên bản cải tiến
bởi Wei Yusi [24].
Chƣơng 5 trình bày các kết quả thực nghiệm theo các thuật toán và phân
tích đánh giá thời gian chạy thực nghiệm của các thuật toán.

8



CHƯƠNG 1. GIỚI THIỆU

1.1. Mục tiêu và kết quả của Luận văn
1.1.1. Mục đích
Mục tiêu của luận văn này là mô tả, phân tích, thực hiện và đánh giá thuật
toán tìm đƣờng đi ngắn nhất đơn nguồn của Thorup [19] cũng nhƣ phiên bản cải
tiến bởi Wei Yusi [24] trong việc giải bài toán đƣờng đi ngắn nhất đơn nguồn có
so sánh với các thuật toán kinh điển khác.
Hai thuật toán Thorup[19] và Thorup - WeiYusi[24] chỉ thực hiện trên đồ
thị vô hƣớng và là giải thuật tìm đƣờng đi ngắn nhất đơn nguồn nên chúng tôi sẽ
chỉ tiến hành việc thực nghiệm trên các đơn đồ thị vô hƣớng.
Đồng thời chúng tôi cũng tiến hành so sánh thời gian xử lý của giải thuật
Dijkstra áp dụng đống nhị phân và đống Fibonacci trên thực tế và so sánh với
đánh giá lý thuyết. Chƣơng 3 của luận văn đƣợc dành riêng để mô tả các thuật toán
kinh điển. Thuật toán Thorup đƣợc mô tả và phân tích trong Chƣơng 4. Khảo sát
thực nghiệm các thuật toán SSSP đƣợc trình bày trong Chƣơng 5.
1.1.2. Kết quả
Kết quả của luận văn là cơ sở để đánh giá, phân tích thời gian xử lý của các
thuật toán trên thực nghiệm và đề xuất lựa chọn thuật toán phù hợp nhất với các
yêu cầu trong thực tế.
Chúng tôi đã thử nghiệm thời gian chạy của thuật toán Thorup[19] và
Thorup - WeiYusi[24] và các thuật toán tìm đƣờng đi ngắn nhất đơn nguồn khác
trong luận văn này trên các đồ thị khác nhau trong chƣơng 5. Đồng thời chúng tôi
cũng đƣa ra đánh giá và phân tích kết quả so sánh giữa các thuật toán.
Thực nghiệm đã cho thấy thuật toán Thorup hoàn toàn không có lợi trong
thực tế. Cả phiên bản cải biên của WeiYusi[24] cũng ít có khả năng ứng dụng vào
các đồ thị thực tế do có cấu trúc tƣơng tự giải thuật Thorup[19].
9



Thuật toán Dijkstra sử dụng đống nhị phân là thuật toán chạy nhanh nhất và
thời gian xử lý của đống nhị phân chạy nhanh hơn gần gấp đôi so với đống
Fibonacci. Chúng tôi cũng trình bày các lý giải về vấn đề này theo quan điểm cá
nhân tại phần kết luận Chƣơng 5.

1.2. Các ký hiệu toán học
Trong luận văn này, ký hiệu log để chỉ
của . Đối với số nguyên không âm

và

, đó là logarithm với cơ số 2

, hàm Ackermann

đƣợc định

nghĩa đệ quy nhƣ sau:

là giá trị của nó tăng rất nhanh. Gọi

Một tính chất quan trọng của
. Khi đó

tăng rất nhanh, trái lại hàm nghịch đảo của nó

tăng rất chậm. Hàm nghịch đảo của hàm Ackermann đƣợc ký hiệu là

. Hàm


nghịch đảo Ackermann hai tham số đƣợc định nghĩa bởi
.

1.3. Mạng lưới, hệ thống trong thực tế và lý thuyết đồ thị
Có thể nói kết quả liên quan đến việc giải quyết bài toán bảy cây cầu ở
thành phố Königsberg là một trong những kết quả đầu tiên của lý thuyết đồ thị.
Leonhard Euler giải quyết bài toán này vào năm 1735 bằng cách chứng minh
rằng không có cách đi qua mỗi cái cầu đúng một lần trong hệ thống 7 cái cầu mô
tả ở hình 1.1. Bằng việc mô hình hóa các cầu bởi các cạnh của một đồ thị, Euler
đã giải quyết đƣợc bài toán về những cây cầu Königsberg. Hơn nữa ông đã đƣa
ra một lớp đồ thị có rất nhiều ứng dụng thú vị, mà hiện tại đƣợc biết dƣới tên gọi
đồ thị Euler. Kể từ đó, đồ thị đã đƣợc sử dụng nhƣ là một mô hình toán học để
mô phỏng rất nhiều các cấu trúc trong thế giới thực.

10


Hình 1. 1. Sơ đồ bảy cây cầu Königsberg.
1.3.1. Lý thuyết đồ thị
1.3.1.1. Định nghĩa
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh
đó. Một cách hình thức, đồ thị
đó tập

đƣợc xác định bởi 2 tập V và E, trong

gọi là tập các đỉnh (Vertices) và tập

ký hiệu


và

, và tập đỉnh

. Lớp các đồ thị với
chỉ ra tập đỉnh của đồ thị
hiệu bởi

. Một cạnh

gọi là tập các cạnh (Edges). Ta sẽ
, tập cạnh

đỉnh và

cạnh đƣợc ký hiệu là

, và tập cạnh của nó đƣợc kí

ta dùng kí hiệu bởi
nối hai đỉnh

và

. Để

, đƣợc ký hiệu là

.


Có thể phân loại đồ thị theo kiểu và số lƣợng cạnh nối hai đỉnh.
Dƣới đây là định nghĩa một số loại đồ thị quan trọng:
1.
cạnh trong
2.
cạnh trong
3.

đƣợc gọi là đơn đồ thị nếu giữa hai đỉnh thuộc

có nhiều nhất là 1

nối 2 đỉnh đó.
đƣợc gọi là đa đồ thị nếu giữa hai đỉnh thuộc

có thể có nhiều hơn 1

nối nối giữa 2 đỉnh đó (Hiển nhiên đơn đồ thị cũng là đa đồ thị).
đƣợc gọi là đồ thị vô hƣớng nếu các cạnh trong

hƣớng, tức là tập

gồm các cặp (u, v) không có thứ tự. (

,

)≡(

là không định

,

).

4. G đƣợc gọi là đồ thị có hƣớng nếu các cạnh là có hƣớng, nghĩa là tập
gồm các cặp (

,

) có tính thứ tự: (

,

11

)≠(

,

). Trong đồ thị có hƣớng,


các cạnh có hƣớng của nó thƣờng đƣợc gọi ngắn gọn là các cung. Trong nhiều
tình huống, đồ thị vô hƣớng cũng có thể qui về đồ thị có hƣớng nếu nhƣ ta
thaycạnh nối hai đỉnh (

,

) bất kỳ bởi hai cung (


,

) và (

,

).

Hình 1. 2. Hình ảnh mô tả cấu trúc đồ thị.
1.3.1.2. Các khái niệm
Theo định nghĩa, đồ thị
và

là một cấu trúc rời rạc, tức là các tập

hoặc là tập hữu hạn, hoặc là tập đếm đƣợc, có nghĩa là ta có thể đánh số thứ

tự 1, 2, 3... cho các phần tử của tập

và

. Hơn nữa, đứng trên phƣơng diện

ngƣời lập trình cho máy tính thì ta chỉ quan tâm đến các đồ thị hữu hạn (V và E là
tập hữu hạn) mà thôi, chính vì vậy từ đây về sau, nếu không chú thích gì thêm thì
khi nói tới đồ thị, ta hiểu rằng đó là đồ thị hữu hạn.
Cạnh liên thuộc, đỉnh kề, bậc
. Xét một cạnh e ∈

• Đối với đồ thị vô hƣớng

) thì ta nói hai đỉnh
(incident) với đỉnh

và

và đỉnh

• Với một đỉnh

, nếu e = (

,

là kề nhau (adjacent) và cạnh e này liên thuộc
.

trong đồ thị, ta định nghĩa bậc (degree) của

ký hiệu

deg( ) là số cạnh liên thuộc với . Dễ thấy rằng trên đơn đồ thị thì số cạnh liên
thuộc với

cũng là số đỉnh kề với .

Định lý: Giả sử
cả các bậc của các đỉnh trong

là đồ thị vô hƣớng với


cạnh, khi đó tổng tất

sẽ bằng 2 :

Hệ quả: Trong đồ thị vô hƣớng, số đỉnh bậc lẻ là số chẵn.

12


. Xét một cung e ∈ E, nếu e = (u, v)

• Đối với đồ thị có hƣớng

thì ta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v.
Đỉnh u khi đó đƣợc gọi là đỉnh đầu, đỉnh v đƣợc gọi là đỉnh cuối của cung e.
• Với mỗi đỉnh v trong đồ thị có hƣớng, ta định nghĩa: Bán bậc ra của v
ký hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg-(v) là số cung đi
vào đỉnh đó.
Định lý: Giả sử

là đồ thị có hƣớng với m cung, khi đó tổng tất

cả các bán bậc ra của các đỉnh bằng tổng tất cả các bán bậc vào và bằng m:

Trong một số trƣờng hợp ta có thể không quan tâm đến hƣớng của các
cung và coi các cung đó là các cạnh của đồ thị vô hƣớng. Đồ thị vô hƣớng thu
đƣợc bởi việc bỏ qua hƣớng trên tất cả các cung đƣợc gọi là đồ thị vô hƣớng nền
của đồ thị có hƣớng ban đầu.
1.3.1.2. Tính liên thông của đồ thị
Đối với đồ thị vô hướng

Đồ thị vô hƣớng

đƣợc gọi là liên thông (connected) nếu luôn

tồn tại đƣờng đi giữa mọi cặp đỉnh phân biệt của đồ thị. Nếu G không liên thông
thì chắc chắn nó sẽ là hợp của hai hay nhiều đồ thị con liên thông, các đồ thị con
này đôi một không có đỉnh chung. Các đồ thị con liên thông rời nhau nhƣ vậy
đƣợc gọi là các thành phần liên thông của đồ thị đang xét.

Hình 1. 3.Hình ảnh mô tả cấu trúc đồ thị.

13


Đôi khi, việc xoá đi một đỉnh và tất cả các cạnh liên thuộc với nó sẽ tạo ra
một đồ thị mới có nhiều thành phần liên thông hơn đồ thị ban đầu, các đỉnh nhƣ
thế gọi là đỉnh cắt hay điểm khớp. Hoàn toàn tƣơng tự, một cạnh mà việc loại bỏ
nó tạo ra một đồ thị có nhiều thành phần liên thông hơn so với đồ thị ban đầu
đƣợc gọi là một cạnh cắt hay một cầu.
Đối với đồ thị có hướng
Có hai khái niệm về tính liên thông của đồ thị có hƣớng tuỳ theo chúng ta
có quan tâm tới hƣớng của các cung hay không. G gọi là liên thông mạnh
(Strongly connected) nếu luôn tồn tại đƣờng đi (theo các cung định hƣớng) giữa
hai đỉnh bất kỳ của đồ thị, G gọi là liên thông yếu (weakly connected) nếu đồ thị
vô hƣớng nền của nó là liên thông.
1.3.1.3. Đồ thị phẳng
Một đồ thị đƣợc gọi là đồ thị phẳng nếu có thể vẽ nó trên mặt phẳng sao
cho không có 2 cạnh nào cắt nhau ngoài ở đỉnh. Đồ thị phẳng chia mặt phẳng
thành tập hợp các vùng, gọi là các mặt. Theo quy ƣớc, vùng không bị chặn phía
ngoài toàn bộ đồ thị là một mặt. Biên giới của một mặt là đồ thị con chứa tất cả

các cạnh tiếp giáp với mặt đó. Mức độ của mặt là độ dài nhỏ nhất của phạm vi
biên giới (phạm vi biên giới của face là tất cả các cạnh đƣợc chứa trong đó) .

Hình 1. 4.Hình ảnh mô tả cấu trúc đồ thị phẳng.
Công thức Euler cho đồ thị phẳng
Định lý Euler. Giả sử cho đồ thị liên thông phẳng
e cạnh và f mặt. Ta có:
v – e + f = 2.

14

có v đỉnh,


Từ công thức Euler ta có các hệ quả đƣợc sử dụng để kiểm tra một đồ thị
có phải là đồ thị phẳng hay không:
Hệ quả 1. Nếu v ≥ 3 thì e ≤ 3v - 6.
Hệ quả 2.Nếu v ≥ 3 nếu không tồn tại chu trình độ dài 3 thì e

2v

4.

Định lý Kuratowski
Có hai đồ thị không phẳng đặc biệt là K3,3 và K5 , trong đó K5 là đồ thị đầy
đủ với 5 đỉnh và K3,3 là đồ thị hai phía đầy đủ với 6 đỉnh.
Định lý Kuratowski. Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị
con đồng phôi với K3,3 hoặc K5.
1.3.1.4. Mật độ đồ thị
Trong suốt luận văn này, chúng ta sẽ định nghĩa mật độ của một đồ thị là

tỷ lệ giữa số cạnh và số đỉnh, đó là bằng
=
đủ với

. Tổng số cạnh của đồ thị đầy đủ là

, nghĩa là số cạnh của đồ thị đầy đủ là O(n2). Đồ thị đầy

2

đỉnh đƣợc ký hiệu Kn.
Số cạnh

trong một đơn đồ thị liên thông

đỉnh thoả mãn bất đẳng thức:

. Nhƣ vậy m nằm trong khoảng
đồ thị đƣợc gọi là đồ thị thƣa nếu

và

. Một

là nhỏ. Trái lại, đồ thị dày là đồ thị có

là lớn. Quan niệm “nhỏ”/”lớn” sẽ đƣợc nêu rõ trong phạm vi ứng dụng cụ
thể. Một trƣờng hợp đồ thị thƣa đặc biệt là đồ thị phẳng. Đối với một đồ thị
phẳng, mật độ đƣợc giới hạn bởi một hằng số, ta có
cho số lƣợng cạnh của đơn đồ thị liên thông là

bất kỳ đơn đồ thị liên thông với

cạnh là

xây dựng một đơn đồ thị liên thông với

cạnh là

=

( ). Do ta có cận dƣới

, nên kích thƣớc đầu vào của
. Do đó, thời gian cần thiết để
.

1.3.2. Mạng lưới, hệ thống trong thực tế
Hệ thống mạng lưới giao thông vận tải
Mạng lƣới giao thông vận tải là một phần không thể thiếu của các cơ sở hạ
tầng ở nhiều nƣớc. Ví dụ về các mạng lƣới giao thông vận tải: đƣờng bộ, đƣờng
sắt, và mạng lƣới hàng không.
Mạng lưới Web:
15


Hệ thống mạng lƣới Web bao gồm hàng tỷ trang web đƣợc kết nối bằng
các hyperlink và đƣợc biểu diễn dƣới dạng các đồ thị có hƣớng. Các trang web
và hyperlink đƣợc biểu diễn bởi các nút và các cạnh tƣơng ứng.
Một trang web đƣợc xếp hạng cao khi càng có nhiều liên kết đến với nó.
Các công cụ tìm kiếm dựa trên nguyên lý này để xếp hạng các trang Web khi

ngƣời dùng tìm kiếm nội dung thông tin.
Chúng ta sẽ rất khó để có đƣợc hình ảnh chính xác của mạng lƣới Web do:
số lƣợng các trang Web quá lớn, các trang Web đƣợc đặt trên các máy chủ khác
nhau trên phạm vi toàn thế giới. Ngoài ra, nội dung của các trang Web cũng liên
tục thay đổi theo thời gian.
Các nhà nghiên cứu thƣờng tập hợp một số mô hình Web mẫu và xây
dựng các đồ thị và mô hình toán học dựa trên các mẫu đã thu thập đƣợc để có thể
tiên đoán đƣợc việc phát triển tƣơng lai của mạng lƣới Web.
Mạng xã hội:
Trong các ngành khoa học tự nhiên và xã hội mà đồ thị mô hình quan hệ
giữa các loài, các cấu trúc xã hội, các công ty… Trong một mạng xã hội, các cá
nhân có thể đƣợc mô hình hóa bởi các nút; hai nút đƣợc kết nối bởi một cạnh bất
cứ khi nào các cá nhân tƣơng ứng là bạn bè.
Mạng lưới định tuyến
Kể từ khi Internet đã trở thành một hệ thống mạng không thể tách rời
trong việc xử lý của các giao dịch kinh doanh giữa các công ty, giữa các công ty
và cá nhân, bất kỳ vấn đề kỹ thuật xảy ra trong mạng có thể có hậu quả nghiêm
trọng trong thế giới thực. Internet hiện nay đƣợc coi là cơ sở hạ tầng quan trọng
nhất ở cấp độ của mạng lƣới giao thông và năng lƣợng.

16


CHƯƠNG 2. TỔNG QUAN BÀI TOÁN TÌM
ĐƯỜNG ĐI NGẮN NHẤT

2.1. Bài toán tìm đường đi ngắn nhất
Trong lý thuyết đồ thị, bài toán đƣờng đi ngắn nhất đơn nguồn là bài toán
tìm một đƣờng đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh trên
đƣờng đi đó là nhỏ nhất.

Định nghĩa: Cho đồ thị
Độ dài của đƣờng đi

Gọi

và một hàm trọng lƣợng

:

.

đƣợc tính là:

là tập tất cả các đƣờng đi từ

đến . Bài toán tìm đƣờng đi ngắn

nhất từ đến đƣợc phát biểu nhƣ sau:

Các dạng bài toán tìm đường đi ngắn nhất
Bài toán tìm đƣờng đi ngắn nhất đƣợc phân làm các dạng chính sau đây:
- Bài toán tìm đƣờng đi ngắn nhất đơn nguồn (single-source shortest path
problem - SSSP): Trong dạng này, chúng ta sẽ tìm đƣờng đi ngắn nhất từ một
đỉnh đến tất cả các đỉnh còn lại.
- Bài toán tìm đƣờng đi ngắn nhất giữa 2 đỉnh (single-pair shortest path
problem): Cần tìm đƣờng đi ngắn nhất giữa 2 đỉnh cho trƣớc.
- Bài toán tìm đƣờng đi ngắn nhất giữa mọi cặp đỉnh (all- pair shortest
path problem – ASPS): Cần tìm đƣờng đi ngắn nhất giữa tất cả các cặp đỉnh
trong đồ thị.


17


2.2. Lịch sử phát triển bài toán tìm đường đi ngắn nhất và kết
quả
Cùng với việc xây dựng đƣợc các đồ thị mô hình hóa các mạng lƣới, hệ
thống trong thực tế, bài toán tìm đƣờng đi ngắn nhất ngày càng quan trọng. Câu
trả lời cho 3 câu hỏi đƣợc nêu ở trên đối với các bài toán tìm đƣờng đi ngắn nhất
chính là câu trả lời: Cách đi và chi phí ngắn nhất tới Nagoya – Nhật Bản, trình tự
nhanh nhất để bạn liên lạc với ngƣời bạn đó, cách kết nối nhanh nhất với Web
server của trang Web đó,....
Tầm quan trọng của các vấn đề trên và nhiều ứng dụng đã thúc đẩy các nỗ
lực nghiên cứu trong hơn năm mƣơi năm. Trong đó một trong những vấn đề
trọng tâm của bài toán đƣờng đi ngắn nhất là trong mạng lƣới giao thông, khi
việc tìm tuyến đƣờng trở thành một trong những ứng dụng quan trọng nhất của
thuật toán đƣờng đi ngắn nhất. Phƣơng pháp để tìm một con đƣờng ngắn nhất
đƣợc nghiên cứu và phân tích trong những năm cuối 50 và đầu những năm 60 bởi
các nhà khoa học Bellman, Bock và Cameron, Caldwell, Dantzig, Dijkstra,
Floyd, Ford, Fulkerson, Hu, Klee, Leyzorek, Gray, Johnson, Ladew, Meaker ,
Petry, và Seitz, Minty, Moore, Mori và Nishimura, Parikh, Rapaport và
Abramson, Shimbel, Warshall, Whiting và Hillier,...
Hiện nay, nhiều thuật toán của của các nhà khoa học trên vẫn đang đƣợc
sử dụng dƣới hình thức này hay cách khác.
Bài toán tìm đường đi ngắn nhất đơn nguồn (SSSP)
Đầu năm 1960, có hai giải thuật nghiên cứu về đồ thị có trọng số trong đó
là thuật toán Bellman – Ford[6] với trọng số tùy ý và Dijkstra[7] với trọng số
không âm. Thuật toán Bellman – Ford[6] có thời gian chạy là
số cạnh và

, với


là

là số đỉnh. Tuy nhiên, thời gian xử lý của thuật toán nói chung

không khả quan. Điểm cộng của thuật toán là việc có khả năng phát hiện ra chu
trình âm.
Giải thuật năm 1959 của Dijkstra[7] ban đầu không sử dụng hàng đợi ƣu
tiên chạy trong thời gian

nếu cài đặt trực tiếp. Các nhà khoa học nhanh
18


chóng nhận ra rằng thuật toán Dijkstra[7] có thể đƣợc tăng tốc xử lý bằng việc sử
dụng hàng đợi ƣu tiên. Với hàng đợi ƣu tiên dựa trên đống d – ary của Johnson
vào năm 1975 và sự khái quát hóa của cây nhị phân thời gian xử lý giảm xuống
còn

. Năm 1987, Fredman và Tarjan công bố cấu trúc đống Fibonacci.

Thuật toán Dijkstra[7] áp dụng đống Fibonacci đã giảm thời gian tính toán xuống
còn

.
Cùng với sự phát triển của hệ thống tọa độ, các đồ thị thực tế giờ đƣợc gắn

vào trục tọa độ với kinh độ và vĩ độ. Việc tìm kiếm đƣờng đi ngắn nhất cũng
đƣợc thể hiện trên hệ trục tọa độ. Thuật toán A* đƣợc mô tả lần đầu vào năm
1968 bởi Peter Hart, Nils Nilsson, và Bertram Raphael. Trong bài báo của họ,

thuật toán đƣợc gọi là thuật toán A; khi sử dụng thuật toán này với một đánh giá
heuristic thích hợp sẽ thu đƣợc hoạt động tối ƣu, do đó mà có tên A*.
Theo đó thuật toán Dijistra là một trƣờng hợp đặc biệt của thuật toán A*
khi hàm h(x)=0 với mọi x.
Mọi nỗ lực của các nhà toán học đi trƣớc đều tập trung vào việc triển khai
giải thuật của Dijkstra trong mô hình tính toán RAM (Random Access Machine).
Năm 1994, Fredman và Wilard đề xuất cấu trúc đống atomic[10] cho phép
thuật toán Dijkstra[7] thực hiện với thời gian

và là thời

gian chạy trên tính toán lý thuyết do cấu trúc đống atomic[10] hiện chỉ mô tả trên
lý thuyết và không áp dụng đƣợc trong hệ thống máy tính hiện nay. Tới nay, việc
triển khai tốt nhất giải thuật của Dijkstra trong thời gian chạy
[23] (dự kiến) và thời gian

[20].

Năm 1999, Thuật toán Thorup[19] đƣợc công bố trong tạp chí Journal of
the ACM, Thorup đã phát minh ra phép tiếp cận tuần tự - thay đổi từ giải thuật
Dijkstra và đƣa thời gian triển khai thuật toán là tuyến tính trên đồ thị vô hƣớng
có trọng số nguyên dƣơng.
Bài toán tìm đường đi ngắn nhất giữa các cặp đỉnh (APSP)
Bài toán APSP – tìm đƣờng đi ngắn nhất từ mỗi đỉnh tới các đỉnh khác –
có thể giải quyết dễ dàng bằng cách thực hiện
19

lần SSSP. Vì vậy, thuật toán của



Bellman-Ford giải quyết APSP trong thời gian

và Dijkstra giải quyết

APSP (trên chiều dài cạnh không âm) trong thời gian

. Tuy

nhiên, phép tiếp cận trực tiếp đối với APSP có thể đem lại giải pháp tốt hơn.
Đồ thị dày
Giải thuật của Floyd-Warshall [12] đƣợc công bố vào năm 1962 bởi
Robert Floyd , về cơ bản thuật toán cũng tƣơng tự nhƣ các thuật toán công bố
trƣớc đây của Bernard Roy vào năm 1959 và Stephen Warshall năm 1962. Thuật
, và có lợi thế thực tế là đơn giản và

giải tính toán APSP trong thời gian

hợp lý. Giải thuật này đƣợc biết đến là phép nhân ma trận (

có thể đƣợc

dùng để giải quyết bài toán khoảng cách giữa các cặp đỉnh

, bài toán về

thực chất không yêu cầu việc tìm đƣờng đi ngắn nhất.
Điều này đƣa ra thời gian rõ ràng
. Độ phức tạp của

cho thuật toán


thƣờng gần tƣơng đƣơng với phép nhân ma trận

[3]. Fredman [8] đã đƣa ra phép nhân

thực hiện phép toán

.
Tuy nhiên việc triển khai thời gian đa thức của giải thuật Fredman không
đƣợc biết. Tới nay, giải thuật

nhanh nhất là nhờ Takaoka[18], ngƣời

sử dụng phép tiếp cận của Fredman đối với các bài toán nhỏ. Giải thuật của
là bƣớc tiến lớn về phép toán

Takaoka chạy trong thời gian
logarit đối với phép nhân ma trận tiêu chuẩn.
Đồ thị thưa

Johnson[16] đã đƣa ra một giải pháp thú vị cho bài toán chiều dài cạnh
âm. Giả sử rằng chu trình âm không tồn tại, ông đã chỉ ra rằng bài toán đƣờng đi
tới cùng khoảng cách, nhƣng chỉ có

ngắn nhất có thể chạy trong thời gian
chiều dài cạnh không âm.

Kết hợp với giải thuật SSSP của Dijkstra, ngay lập tức cho giải thuật
APSP các đồ thị trọng số tùy ý chạy trong thời gian


20

.


Dù vậy, đối với cả 2 dạng đồ thị giải thuật của Dijkstra (có hoặc không có
giải pháp rút gọn của Johnson) vẫn là giải thuật APSP chung nhanh nhất trong
nhiều năm.
Do mục tiêu của Luận văn là thử nghiệm so sánh các thuật toán tìm kiếm
đƣờng đi ngắn nhất đơn nguồn nên các thuật toán về tìm đƣờng đi ngắn nhất từng
cặp đỉnh sẽ không đƣợc nêu.
Bảng 2.1. đƣới đây liệt kê các đánh giá thời gian chạy lý thuyết của các
thuật toán tìm đƣờng đi ngắn nhất đơn nguồn trên đồ thị vô hƣớng với trọng số
không âm.
Thuật toán
Dijisktra sử dụng
list

Độ phức tạp

Nhà phát minh
Leyzorek et al.
1957, Dijkstra
1959

Dijisktra sử dụng
đống nhị phân
Dijisktra sử dụng
Fredman&Tarjan
đống Fibonacci

1987
Thorup
Thorup, 1999
Sett Pettie
Sett Pettie, 2003
Bảng 2. 1.Thời gian chạy các thuật toán SSSP sắp xếp theo năm.

2.3. Ứng dụng của bài toán tìm đường đi ngắn nhất
Tƣơng ứng với các vấn đề trong thực tế đã có rất nhiều các ứng dụng của
bài toán tìm đƣờng đi ngắn nhất trong từng mạng lƣới đã nêu trên. Chúng ta có
thể liệt kê các ứng dụng phổ biến nhất hiện nay:
2.3.1. GPS
GPS (Global Positioning System): Hệ thống định vị toàn cầu - là hệ thống
xác định vị trí dựa trên vị trí của các vệ tinh nhân tạo. Trong cùng một thời điểm,
ở một vị trí trên mặt đất nếu xác định đƣợc khoảng cách đến ba vệ tinh (tối thiểu)
thì sẽ tính đƣợc toạ độ của vị trí đó. GPS đƣợc thiết kế và quản lý bởi Bộ Quốc
phòng Hoa Kỳ, nhƣng chính phủ Hoa Kỳ cho phép mọi ngƣời sử dụng nó miễn

21


phí, bất kể quốc tịch từ năm 1980, GPS hoạt động trong mọi điều kiện thời tiết,
mọi nơi trên Trái Đất, 24 giờ một ngày.
GPS là hệ dẫn đƣờng dựa trên một mạng lƣới 24 quả vệ tinh đƣợc đặt trên
quỹ đạo không gian, hoạt động dựa trên các trạm phát tín hiệu vô tuyến điện.
Đƣợc biết nhiều nhất là các hệ thống có tên gọi LORAN - hoạt động ở giải tần
90-100 kHz chủ yếu dùng cho hàng hải, hay TACAN - dùng cho quân đội Mỹ và
biến thể với độ chính xác thấp VOR/DME - VHF dùng cho hàng không dân
dụng.
2.3.2. Phân tích và xử lý ảnh

Phân tích vùng ảnh là một phần không thể thiếu của các nghiệp vụcần xử
lý ảnh nhƣ những công việc xử lý ảnh tai nạn, phân tích hình ảnh qua thiết bị y
tế, và chỉnh sửa ảnh.
Vấn đề của việc phân vùng ảnh là việc gom các nhóm pixel gần nhau có
tính chất giống nhau. Quá trình gom nhóm thƣờng dựa trên tính toán đƣờng đi
ngắn nhất. Bề mặt của ảnh là những chiều liên tục. Đƣờng đi ngắn nhất đƣợc tính
toán với các phƣơng pháp so sánh, một biến thể của thuật toán toán Dijkstra[7].
Các thuật toán dựa trên đồ thị xem các hình ảnh nhƣ là một đồ thị, trong đó mỗi
pixel là một nút, kết nối bởi một cạnh có 4 (hoặc 8 hoặc nhiều hơn) pixel lân cận.
Một phần quan trọng là gán trọng số thích hợp để các cạnh, dựa trên hình ảnh
"tiềm năng" của hai điểm ảnh và khoảng cách Euclide giữa các pixel. Những
ngƣời sử dụng cung cấp điểm đầu cuối; các thuật toán tính toán kết quả của truy
vấn con đƣờng ngắn nhất tƣơng ứng point-to-point và các đƣờng dẫn kết quả
đƣợc hiểu nhƣ là một phần của các đối tƣợng ranh giới. Nói cách khác, đƣa ra hai
điểm đầu cuối của một đƣờng viền, các thuật toán xác định các đƣờng viền tối đa
khả năng kết nối chúng. Các trọng số cạnh là xác suất và bằng cách lấy logarit
tiêu cực, các thuật toán chỉ có thể tổng hợp các trọng trên con đƣờng để lấy
đƣờng viền tối ƣu. Đối với các tính toán ranh giới trong 3 chiều, các thuật toán
thông minh kéo phải đƣợc thích nghi. Một ranh giới có thể đƣợc tìm thấy bằng
cách kết hợp nhiều con đƣờng ngắn nhất cho đến khi một mặt kín thu đƣợc.

22


Trong tầm nhìn máy tính, thuật toán đƣờng đi ngắn nhất trên đồ thị có
trọng đã tìm thấy rất nhiều ứng dụng khác với phân khúc nhƣ phát hiện trung
tâm, xạ trị, lƣới morphing, video tổng hợp, và việc tìm kiếm những con đƣờng và
những con đƣờng mòn trên hình ảnh vệ tinh. Các ứng dụng nổi tiếng: Dò tìm
theo hình ảnh, Google Image…
2.3.3. Công cụ tìm kiếm qua mạng Internet (Social Search)

Công cụ tìm kiếm qua mạng Internet (Social search hay social search
engine) là loại hình tìm kiếm web dựa trên các đồ thị quan hệ xã hội (Social
Graph) của ngƣời tìm kiếm. Việc tìm kiếm qua Social Search sẽ tiến hành thông
qua việc phân tích các đoạn văn bản hoặc các cấu trúc liên kết văn bản bằng thuật
toán hoặc phép tính toán gần đúng.
Social search có rất nhiều dạng từ dạng bookmark chia sẻ đơn giản cho
đến việc gán nhãn mô tả bằng các thuật toán.
Hiện nay trên thế giới có rất nhiều công cụ tìm kiếm: Google, Yahoo,
Facebook Graph Search, Bing… Trong đó, nổi bật lên là công cụ tìm kiếm
Google search.
2.3.4. Tìm kiếm trong mạng xã hội (Social Network Search)
Bài toán đƣờng đi ngắn nhất là phần rất thú vị trong mạng xã hội dành cho
ngƣời dùng. Một ví dụ rất thú vị về việc này đó là trang web orcaleofbacon.org,
cho phép ngƣời dùng nhập tên hai diễn viên và máy chủ sẽ tiến hành tìm kiếm
mối quan hệ chung ngắn nhất giữa hai diễn viên này. Tƣơng tự cũng có nhƣng
trang web nhƣ vậy cho toán học.
Trong các trang mạng xã hội chuyên nghiệp nhƣ Linkedln hoặc XING,
ngƣời dùng có thể thêm các thông tin về việc làm mình mong muốn, hoặc các
thông tin tuyển dụng, thông tin mặt hàng về kinh doanh. Từ đó có thể tìm thấy
những khách hàng tiềm năng, hoặc tìm kiếm nhân viên thông qua các chuỗi kết
nối ngắn về thông tin của các cá nhân.
Facebook Graph Search là một công cụ tìm kiếm ngữ nghĩa đã đƣợc
giới thiệu bởi Facebook tháng 3 năm 2013. Nó đƣợc thiết kế để cung cấp cho câu

23


trả lời cho các truy vấn ngôn ngữ tự nhiên ngƣời sử dụng chứ không phải là một
danh sách liên kết. Kết quả tìm kiếm dựa trên cả hai nội dung của ngƣời sử dụng
và hồ sơ của những ngƣời bạn và các mối quan hệ giữa ngƣời sử dụng và bạn bè

của họ. Kết quả đƣợc dựa trên bạn bè và sở thích thể hiện trên Facebook, và cũng
định hình bởi các thiết lập riêng tƣ của ngƣời dùng.
2.3.5. Hệ thống tin nhắn
Chuyển tiếp một tin nhắn từ ngƣời gửi đến ngƣời nhận thông qua một hệ
thống mạng lƣới đƣợc gọi là routing. Các thuật toán về routing đều là các biến
thể, ở dạng này hay cách khác của các thuật toán đƣờng đi ngắn nhất (tuyến
đƣờng các gói tin truyền có chi phí tối thiểu). Hệ thống mạng có thể mô tả nhƣ
một đồ thị, chi phí giữa các cạnh phản ánh khả năng truyền tải, độ trễ, tắc nghẽn,
tỷ lệ lỗi, và các đặc tính khác.
Trong hệ thống mạng, router phải biết chính xác nơi để chuyển tiếp một
gói tin đến. Việc này đƣợc thực hiện dựa trên các thông tin trong các gói dữ liệu
và các bảng định tuyến tại các router. Số lƣợng các mạng lƣới đƣợc kết nối ngày
càng lớn, bộ nhớ cần thiết để lƣu trữ các bảng định tuyến phát triển. Yêu cầu bộ
nhớ này thay đổi rất nhiều với các giao thức định tuyến và với kiến trúc của
router.
Trong một số hệ thống nhỏ, một thiết bị trung tâm quyết định thời gian
hoàn thành của tất cả các gói tin. Trong các hệ thống chuyển tin nhanh, có rất
nhiều gói tin truyền đi mỗi giây cho nên việc chỉ có một thiết bị duy nhất để tính
toán đƣờng dẫn đầy đủ cho mỗi gói tin là không khả thi. Ban đầu việc xử lý gửi
gói tin hệ thống tính toán đƣờng đi ngắn nhất sau đó nếu có các gói tin khác có
các nguồn giống nhau và đến cùng đích tiếp tục đi theo đƣờng đi tƣơng tự mà
không tính toán lại cho đến khi không còn gói tin đƣợc gửi.
Trong các hệ thống lớn, có rất nhiều các kết nối giữa các thiết bị, và các
kết nối này thay đổi rất thƣờng xuyên, việc biết tất cả các thiết bị kết nối với
nhau hay tính toán một đƣờng đi ngắn nhất thông qua là không khả thi đối với

24


bất kỳ một thiết bị. Hệ thống nhƣ vậy thƣờng sử dụng next-hop routing. Các ứng

dụng: Hệ thống tin nhắn điện thoại, …

2.4. Kỹ nghệ thuật toán
2.4.1. Giới thiệu
Trong thời đại hiện nay, chúng ta có thể thấy sự tác động của việc áp dụng
thuật toán trong toàn bộ các phần mềm đã và đang đƣợc sử dụng. Các thuật toán
ngày càng trở nên chiếm vai trò quan trọng trong hệ thống ngành kinh tế, công
nghệ, khoa học, và trong cuộc sống hàng ngày.
Chúng ta có thể kể ra một số ngành nghề đặc biệt liên quan chặt chẽ đến
việc áp dụng các thuật toán nhƣ công nghệ sinh học, tìm kiếm thông tin, mạng lƣới
thông tin liên lạc, mật mã, hệ thống thông tin địa lý, lấy thông tin từ hình ảnh
(chỉnh sửa, khôi phục), vận tải đa phƣơng tiện...
Algorithmics – hệ thống phát triển tính hiệu quả của thuật toán trở thành
công nghệ chủ chốt trong quá trình phát triển các ứng dụng trên máy tính. Tuy
nhiên, trong những năm qua xuất hiện khoảng cách ngày càng lớn giữa lý thuyết
về thuật toán thuần túy và nhu cầu thực tế. Hệ quả của vấn đề này dẫn đến việc chỉ
một số ít các thuật toán là thực sự đƣợc áp dụng trong thực tế. Điều này thật sự rất
đáng tiếc, để hiểu đƣợc vấn đề này, chúng ta cần tìm hiểu quá trình nghiên cứu
thuật toán đƣợc diễn ra nhƣ thế nào theo cách thông thƣờng.
2.4.1.1. Thuật toán cổ điển
Trọng tâm của lý thuyết về thuật toán là các vấn đề đơn giản và có tính trừu
tƣợng. Đối với một vài vấn đề thuật toán đƣợc thiết kế và phân tích dựa trên các
mô hình giả định sinh ra từ các máy trừu tƣợng (máy tính tự động sử dụng theo lý
thuyết automata), từ đó đƣa ra đánh giá thời gian chạy của các thuật toán trong
trƣờng hợp xấu nhất và xác định đƣợc chất lƣợng của thuật toán.
Trong khoa học máy tính, thời gian thực hiện và chất lƣợng lời giải là thƣớc
đo cho tính hiệu quả của thuật toán.

25