Bài toán cây khung nhỏ nhất và các ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.73 MB, 115 trang )

Bạn đang đọc: Bài toán cây khung nhỏ nhất và các ứng dụng – Tài liệu text

MỤC LỤC
DANH MỤC BẢNG BIỂU …………………………………………………………………………………….iii
Chương 1 ………………………………………………………………………………………………………………. 1
GIỚI THIỆU TỔNG QUAN ………………………………………………………………………………….. 1
1.1 Lịch sử của bài toán cây khung nhỏ nhất ……………………………………………………………. 1
1.2 Các ký hiệu toán học ………………………………………………………………………………………. 2
1.3 Lý thuyết đồ thị ……………………………………………………………………………………………… 3
1.4. Cây khung nhỏ nhất ……………………………………………………………………………………….. 6
1.4.1 Một số tính chất ……………………………………………………………………………………….. 6
1.4.2. Rừng trải rộng tối thiểu và những giả định đồ thị …………………………………………. 8
1.4.3 Thời gian tính ………………………………………………………………………………………….. 9
1.5. Các ứng dụng của bài toán MST …………………………………………………………………….. 10
1.5.1. Truyền hình cáp …………………………………………………………………………………….. 11
1.5.2 Thiết kế mạch điện tử ……………………………………………………………………………… 11
1.5.4 Clustering biểu hiện dữ liệu gen (Thuật phân nhóm dữ liệu biểu hiện gen) ……… 11
1.5.5 Xấp xỉ dựa trên MST ………………………………………………………………………………. 12
1.6. Kỹ nghệ thuật toán (Algorithm Engineering)……………………………………………………. 13
1.6.1 Giới thiệu ………………………………………………………………………………………………. 13
1.6.2 Nền tảng của kỹ nghệ thuật toán ……………………………………………………………….. 22
1.7. Mục tiêu và kết quả của Luận văn ………………………………………………………………….. 26
Chương 2 …………………………………………………………………………………………………………….. 28
CẤU TRÚC DỮ LIỆU VÀ CÁC THUẬT TOÁN GIẢI BÀI TOÁN MST……………….. 28
2.1. Khối xây dựng cơ bản …………………………………………………………………………………… 28
2.1.1. Hàng đợi ưu tiên ……………………………………………………………………………………. 28
2.1.2 Kết nối đồ thị và sơ đồ tổng quát của các thuật toán MST …………………………….. 29
2.1.3 Thuật toán Kruskal …………………………………………………………………………………. 34
2.1.4. Thuật toán Boruvka ……………………………………………………………………………….. 35
2.1.5 Thuật toán Dijkstra-Jarn’ık-Prim (DJP)………………………………………………………. 37
2.2. Khối xây dựng nâng cao ……………………………………………………………………………….. 40
2.2.1. Thuật toán “Trường hợp đồ thị dày” …………………………………………………………. 40
2.2.2. Cây quyết định MST………………………………………………………………………………. 46

3.1. Biểu diễn đồ thị …………………………………………………………………………………………… 73
3.2. Bổ đề chính và thủ tục ………………………………………………………………………………….. 75
3.2.1 Bổ đề chính. …………………………………………………………………………………………… 75
3.2.2 Phương pháp phân vùng. …………………………………………………………………………. 76
3.2.3 Thời gian tính phân vùng và thực hiện. ………………………………………………………. 78
3.3. Thuật toán MST tối ưu …………………………………………………………………………………. 81
3.3.1 Thuật toán. …………………………………………………………………………………………….. 81
3.3.2 Thời gian thực hiện. ………………………………………………………………………………… 85
3.3.3 Phân tích cây quyết định. …………………………………………………………………………. 87
3.3.4 Kết luận thời gian tính. ……………………………………………………………………………. 89
3.4 Thực hiện…………………………………………………………………………………………………….. 90
3.4.1 Thực hiện chi tiết ……………………………………………………………………………………. 90
3.4.2 Thông tin thực tiễn………………………………………………………………………………….. 91
Chương 4 …………………………………………………………………………………………………………….. 92
THỰC NGHIỆM …………………………………………………………………………………………………. 92
4.1. Mục đích thực nghiệm và các thuật toán được lựa chọn để thực nghiệm ………………. 92
4.1.1. Mục đích ………………………………………………………………………………………………. 92
4.1.2. Các thuật toán ……………………………………………………………………………………….. 92
4.2. Môi trường và dữ liệu thực nghiệm ………………………………………………………………… 93
4.2.1. Bộ dữ liệu thực nghiệm…………………………………………………………………………… 93
4.2.2. Môi trường thực nghiệm …………………………………………………………………………. 95
4.3. Mô tả cài đặt các thuật toán …………………………………………………………………………… 95
4.4. Kết quả thực nghiệm ……………………………………………………………………………………. 96

4.5.Phân tích kết quả thực nghiệm MST ………………………………………………………………… 98
Tài liệu tham khảo ……………………………………………………………………………………………….. 99
Phụ lục ……………………………………………………………………………………………………………… 100

DANH MỤC BẢNG BIỂU
Bảng 1.1: Thời gian chạy trường hợp tồi nhất các thuật toán MST, sắp xếp theo năm. ……………. 10
Bảng 2.1 Thời gian thực hiện của đống nhị phân, đống Fibonaccis, và Đống mềm. ……………….. 29
Bảng 2.2: Giá trị của

……………………………………………………………………………….. 54

Bảng 4.1: Các thuật toán được lựa chọn thực nghiệm …………………………………………………. 92
với mật độ đồ thị

Bảng 4.2 Giá trị của

………………………………………………. 93

với mật độ đồ thị

Bảng 4.3 : Giá trị của

……………………………………….. 93

Bảng 4.4: Giá trị

với mật độ đồ thị

……………………………………………….. 94

Bảng 4.5 Giá trị

với mật độ đồ thị

……………………………………………………. 94

Bảng 4.6 Giá trị của

với mật độ đồ thị

…………………………………….. 94

Bảng 4.7 Giá trị của

với mật độ đồ thị

……………………………….. 94

Bảng 4.8 Giá trị của

với mật độ đồ thị

…………………………………………….. 94

Bảng C.1: Thể hiện giá trị của ,
của đơn đồ thị có

đỉnh,

cạnh với mật độ đồ thị

Bảng C.2: Thể hiện giá trị của ,
của đơn đồ thị có

đỉnh,

đơn đồ thị có

đỉnh

đơn đồ thị có

đỉnh

đỉnh
đỉnh,

và thời gian chạy t(ms) của các thuật toán tìm MST của

cạnh với mật độ đồ thị

Bảng C.7: Thể hiện giá trị của
đơn đồ thị có

…………………………… 107

cạnh với mật độ đồ thị ……………………………………………………….. 108

Bảng C.6: Thể hiện giá trị của
đơn đồ thị có

…………………………………… 106

và thời gian chạy t(ms) của các thuật toán tìm MST của

cạnh với mật độ đồ thị

Bảng C.5: Thể hiện giá trị của

…………………………. 105

và thời gian chạy t(ms) của các thuật toán tìm MST của

cạnh với mật độ đồ thị

Bảng C.4: Thể hiện giá trị của

……………………………….. 104

và thời gian chạy t(ms) của các thuật toán tìm MST

cạnh với mật độ đồ thị

Bảng C.3: Thể hiện giá trị của
đơn đồ thị có

và thời gian chạy t(ms) của các thuật toán tìm MST

……………………………………… 109

và thời gian chạy t(ms) của các thuật toán tìm MST của

cạnh với mật độ đồ thị

iii

. ……………………………………. 110

Hình 1.1: Đơn đồ thị liên thông

với

và

…………………………………………….. 4

Hình 1.2: Các thuộc tính chu kỳ và các thuộc tính cắt cắt. ……………………………………………. 7
Hình 1.3. Kỹ nghệ thuật toán ………………………………………………………………………………….. 21
Hình 2.1: Một đồ thị với

đỉnh xác định bởi ((1, 2), (1, 3), (2, 3)) và cây quyết định tối

ưu nối cứng của nó. ……………………………………………………………………………………………….. 49
Hình 2.2: Cấu trúc dữ liệu Đống mềm với ba hàng đợi mềm ……………………………………….. 58
Hình B.1: Ví dụ về chọn lọc, bắt đầu từ một sự lặp lại liên kết lại. ………………………………. 100
Hình B.2.1: Đồ thị đầu vào .Hình B.2.2: Sau khi phân vùng…………………………………….. 102
Hình B.2.3: Sau cây quyết định. Hình B.2.4: Đồ thị kết nối Ga. ……………………………….. 103
Hình B.2.5: Sau DenseCase. Hình B.2.6: Cạnh ứng viên Gb. ……………………………………. 103
Hình B.2.7: cạnh MST T’được tìm thấy bởi Boruvka2. ……………………………………………… 104
Hình C.1: Đồ thị thể hiện thời gian chạy t của các thuật toán trên đồ thị ngẫu nhiên với mật
độ đồ thị

(trục Ox biểu diễn

, Oy biểu diễn 𝑡 𝑠 ) ………………………………….. 105

Hình C.2: Đồ thị thể hiện thời gian chạy t của các thuật toán trên đồ thị ngẫu nhiên với mật độ
đồ thị

(trục Ox biểu diễn m, Oy biểu diễn t(s)) ……………………………………. 106

Hình C.3: Đồ thị thể hiện thời gian chạy t của các thuật toán trên đồ thị ngẫu nhiên với mật
độ đồ thị

(trục Ox biểu diễn

, Oy biểu diễn 𝑡 𝑠 ) ………………………………… 107

Hình C.4: Đồ thị thể hiện thời gian chạy t của các thuật toán trên đồ thị ngẫu …………….. 108
nhiên với mật độ đồ thị

(trục Ox biểu diễn

, Oy biểu diễn 𝑡 𝑠 ) ………………. 108

Hình C.5: Đồ thị thể hiện thời gian chạy t của các thuật toán trên đồ thị ngẫu nhiên với mật
độ đồ thị

𝑥

(trục Ox biểu diễn

,Oy biểu diễn 𝑡 𝑠 )……………………….. 109

Hình C.6: Đồ thị thể hiện thời gian chạy t của các thuật toán trên đồ thị ngẫu nhiên với mật
độ đồ thị

𝑥

(trục Ox biểu diễn

,Oy biểu diễn 𝑡) ………………………. 110

Hình C.7: Đồ thị thể hiện thời gian chạy t(ms) của các thuật toán trên đồ thị ngẫu nhiên với
mật độ đồ thị

𝑥 (trục Ox biểu diễn

, Oy biểu diễn 𝑡) …………………………….. 111

Chương 1
GIỚI THIỆU TỔNG QUAN
1.1 Lịch sử của bài toán cây khung nhỏ nhất
Cho G = (V, E) (V là tập đỉnh, E là tập cạnh) là đồ thị vô hướng liên thông có
trọng số trên cạnh 𝑤

. Giả sử T là một cây khung của G, ta gọi trọng số của

cây T là tổng trọng số các cạnh trong T. Bài toán đặt ra là trong số các cây khung
của G, hãy tìm cây khung có trọng số nhỏ nhất. Cây khung như vậy được gọi là cây
khung nhỏ nhất của đồ thị (minimum spanning tree) và bài toán đặt ra được gọi là bài
toán cây khung nhỏ nhất.
Năm 1926, nhà toán học người Séc Otakar Boruvka mô tả một thuật toán giải
“một số bài toán cực tiểu hoá” [4]. Ông đã đề xuất các thuật toán để tối ưu hoá mạng
lưới điện. Vào thời Boruvka chưa có các khái niệm về đồ thị và cây khung tối thiểu.
Thuật toán của ông là thuật toán giải bài toán cây khung nhỏ nhất được biết đến sớm
nhất. Ngày nay thuật toán này được gọi là thuật toán của Boruvka. Trong luận văn,
cây khung nhỏ nhất được gọi tắt là “MST”.
Năm 1930, một thuật toán MST khác được phát hiện bởi nhà toán học Séc
Jarn’ık [9]. Thuật toán này được đề xuất độc lập bởi nhà toán học và khoa học máy
tính người Mỹ Prim vào năm 1957, và sau đó tái khám phá bởi các nhà khoa học máy
tính Hà Lan Dijkstra trong năm 1959. Do đó, thuật toán đôi khi được gọi là thuật toán
của Prim, thuật toán của Jarn’ık, thuật toán Prim-Jarn’ık hoặc thuật toán DJP. Trong
luận văn này, chúng tôi gọi thuật toán này là thuật toán DJP.
Thuật toán Kruskal là một thuật toán trong lý thuyết đồ thị để tìm cây bao
trùm tối thiểu của một đồ thị liên thông có trọng số. Nói cách khác, nó tìm một tập
hợp các cạnh tạo thành một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số
các cạnh là nhỏ nhất. Thuật toán Kruskal là một ví dụ của thuật toán tham lam. Thuật
toán này xuất bản lần đầu tiên năm 1956, bởi Joseph Kruskal

Nhiều thuật toán MST hiện đại sử dụng các ý tưởng từ thuật toán Boruvka và
DJP. Cụ thể là các thuật toán MST tối ưu được nghiên cứu trong luận văn này sử

dụng rất nhiều ý tưởng từ cả hai thuật toán. Kể từ khi phát minh ra các thuật toán, các
bài toán MST đã được nghiên cứu rất nhiều, nhưng chưa ai tìm ra được cận dưới
chính xác cho độ phức tạp thời gian của bài toán MST. Thuật toán MST tối ưu nghiên
cứu trong luận văn này được thiết kế bởi Pettie và Ramachandran [13] vào năm 2002.
Các tác giả đã chứng minh rằng các thuật toán chạy trong thời gian tối ưu, nhưng
không thể đưa ra một cận dưới chính xác thấp hơn. Thuật toán này sẽ được trình bày
ở chương 3.
Phần tiếp theo của chương này sẽ trình bày phát biểu bài toán cây khung nhỏ
nhất, tổng quan về các thuật toán MST quan trọng. Trước hết chúng ta sẽ đưa ra các
ký hiệu toán học được sử dụng trong luận văn, cũng như một số kiến thức cơ bản của
lý thuyết đồ thị.
1.2 Các ký hiệu toán học
Trong luận văn, ta sẽ sử dụng ký hiệu log =
, ký hiệu

Với số nguyên
và
Ví dụ:

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

được định nghĩa quy nạp như sau:

logloglog .
Ký hiệu

được định nghĩa là

, nghĩa là, số lần

các hàm logarithm phải được áp dụng cho đến khi thu được kết quả là
này tăng rất chậm, và

. Hàm số

là nhỏ hơn 6 cho tất cả các giá trị “thực” của .

Giai thừa của một số nguyên dương n, kí hiệu là n!, được định nghĩa là
∏
Hàm n! có thể định nghĩa đệ qui bởi:
. Đối với số nguyên không âm

và

nghĩa đệ quy như sau:

và !=( −1). Dễ dàng thấy là
hàm Ackermann 𝐴(, ) được định

{𝐴
𝐴(

𝐴

)

𝐴

Một tính chất quan trọng của 𝐴

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

𝐴′( ) = 𝐴(, ). Khi đó 𝐴′ tăng rất nhanh, ngược 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 𝛼( ) là nhỏ
hơn 5 cho tất cả giá trị “thực” của. Hàm nghịch đảo Ackermann hai tham số được
định nghĩa bởi 𝛼(, ) = min{ ≥1| 𝐴( ,[ / ]) ≥ log }. Chú ý là hàm 𝛼 tăng rất
chậm. Đối với số nguyên

≥1, hàm 𝛽(, ) được định nghĩa là 𝛽

≥ 0 và

{ |

, nghĩa là 𝛽(, ) là số lần các hàm logarithm được áp

dụng đối với

để thu được kết quả là ≤

/ .

1.3 Lý thuyết đồ thị
Đồ thị vô hướng G là một kiểu dữ liệu trừu tượng được xác định bởi
, trong đó

là một tập đỉnh và

thứ tự. Ta sẽ ký hiệu
{

là một tập cạnh, đó là các cặp đỉnh không có

=| |, và tập đỉnh

=| | và

. Lớp các đồ thị với

Để chỉ ra tập đỉnh của đồ thị
. Một cạnh

hiệu bởi

đỉnh và

ta dùng kí hiệu bởi

{𝑣 𝑣

𝑣, tập cạnh

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

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

nối hai đỉnh 𝑣 và 𝑣, và được ký hiệu 𝑣 𝑣. Theo

định nghĩa của một đồ thị vô hướng, một cạnh là một cặp không có thứ tự gồm hai
đỉnh, vì vậy 𝑣
dương 𝑤
thì

𝑣

𝑣 𝑣. Mỗi cạnh

của đồ thị sẽ được gán một trọng số

có thể hiểu đó là chi phí của “sử dụng” cạnh. Nếu 𝑤

được coi là nhẹ hơn

nặng hơn

𝑤

với

. Để đơn giản, tất cả các ví dụ đồ thị

trong luận văn này sẽ có trọng số cạnh tương ứng với khoảng cách Euclide giữa các
điểm cuối. Điều này là một giả định phổ biến trong các ví dụ thực tế, chẳng hạn như
mạng lưới đường bộ và mạng lưới điện hoặc dây dữ liệu. Bậc của một đỉnh v, ký hiệu
bởi

𝑣 là số cạnh kề với nó (nhận nó là đầu mút). Một đường đi trong đồ thị là

một dãy các đỉnh và cạnh xen kẽ bắt đầu từ một đỉnh và kết thúc tại một đỉnh. Như

vậy, mỗi cạnh trên đường đi sẽ kết nối giữa một đỉnh với một đỉnh đi sau nó. Như vậy
đường đi có thể mô tả bởi dãy: 𝑣

𝑣

𝑣 𝑣

𝑣

Ta gọi chu trình là một đường đi không chứa cạnh lặp lại khởi đầu và kết thúc
tại cùng một đỉnh, nghĩa là 𝑣

𝑣

. Một đường đi được gọi là đường đi đơn

nếu các đỉnh trên nó là phân biệt. Tương tự như vậy, một chu trình đơn là một chu
trình mà các đỉnh trên nó là phân biệt, ngoại trừ đỉnh bắt đầu và kết thúc.

với 𝒏

Hình 1.1: Đơn đồ thị liên thông

và 𝒎
{𝑣 ,…, 𝑣 } và

Ví dụ: Hình 1.1 cho một ví dụ về đồ thị G = (V, E) với
{ 𝑣 𝑣

𝑣 𝑣

bởi đoạn tô đậm) 𝑣

𝑣 𝑣

𝑣

đơn.

cạnh

trên

Dãy

chấm) 𝑣

(các
𝑣 𝑣

𝑣

𝑣 𝑣

𝑣 𝑣
𝑣 𝑣

𝑣

. Dãy (các cạnh trên đường đi thể hiện
𝑣

𝑣 𝑣

đường
𝑣 𝑣

đi
𝑣

thể
𝑣 𝑣

𝑣

cho ta ví dụ một đường đi
hiện

bởi

đoạn

gạch

𝑣 cho ta ví dụ về một chu

trình đơn.
Một đồ thị được gọi liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất
kỳ. Ta gọi khuyên là một cạnh nối một đỉnh với chính nó, tức là cạnh có dạng
𝑣 𝑣. Cạnh như vậy sẽ được tính hai lần trong
và

𝑣. Hai cạnh khác nhau,

là cạnh song song (hay cạnh lặp) nếu chúng cùng nối một cặp đỉnh. Một đồ thị

có chứa cạnh lặp được gọi là đa đồ thị. Một đồ thị có chứa cạnh lặp và khuyên được
gọi là giả đồ thị. Ta gọi đơn đồ thị là đồ thị vô hướng không có khuyên và không có

các cạnh lặp. Từ định nghĩa, tập cạnh

của đơn đồ thị là một tập các bộ không có thứ

tự gồm hai đỉnh. Bậc lớn nhất của một đỉnh trong một đơn đồ thị là

, và bậc của

một đỉnh là số đỉnh lân cận với nó. Đồ thị trong hình 1.1 là một đơn đồ thị liên
thông. Nếu đồ thị là không liên thông, đồ thị con liên thông cực đại của nó được gọi
là thành phần được liên thông.
Có thể chứng minh được rằng số lượng cạnh trong một đơn đồ thị liên thông
luôn lớn hơn hoặc bằng n-1. Vì vậy, cây là đồ thị liên thông có ít cạnh nhất. Ta gọi
rừng là đồ thị mà mỗi thành phần liên thông là một cây.

Xem thêm: Luật sư Hoàng Duy Hùng: Góp ý hay gieo rắc ‘độc dược chính trị’?

Một trường hợp đặc biệt của một đơn đồ thị liên thông là đồ thị đầy đủ. Đồ thị
đầy đủ là đồ thị có tất cả các cạnh có thể. Tổng số cạnh của đồ thị đầy đủ là
=

, nghĩa là số cạnh của đồ thị đầy đủ là

. Đồ thị đầy đủ với

đỉnh được ký hiệu Kn.
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 m/n. Số cạnh m trong một đơn đồ thị liên thông n
đỉnh thoả mãn bất đẳng thức:
khoảng

và

. Như vậy m nằm trong

. Một đồ thị được gọi là đồ thị thưa nếu

tự, đồ thị dày là đồ thị có

là nhỏ. Tương

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. Đồ thị
phẳng là đồ thị có thể vẽ trong mặt phẳng sao cho hai cạnh bất kỳ là không giao nhau,
ngoại trừ tại đỉnh. Ta có
Định lý 1.3: Đồ thị phẳng đơn liên thông với

đỉnh có

≤ 3 −6 cạnh.

Do đó, đối với một đồ thị phẳng, mật độ được giới hạn bởi một hằng số, ta có
= ( ). Do ta có cận dưới cho số lượng cạnh của đơn đồ thị liên thông là

nên kích thước đầu vào của bất kỳ đơn đồ thị liên thông với

cạnh là

. Do đó,

thời gian cần thiết để xây dựng một đơn đồ thị liên thông với

cạnh là

1.4. Cây khung nhỏ nhất

Định nghĩa: Cho G là một đồ thị liên thông. Một cây khung của G là một cây
chứa tất cả các đỉnh với tập cạnh là tập con của tập cạnh của G. Nói cách khác cây
khung là một cây bao trùm tất cả các đỉnh trong G.
Định nghĩa: Cho T là một cây khung của một đồ thị liên thông có trọng số.
Trọng lượng của T được xác định bằng tổng trọng số của các cạnh trong T:
∑
Định nghĩa: Cho G là một đồ thị liên thông có trọng số. Cây khung nhỏ nhất
(MST) của G là cây khung của G với trọng số là nhỏ nhất.
Rõ ràng là từ định nghĩa, MST là một lời giải cho các bài toán trong đó đòi hỏi
phải so sánh các trọng số cạnh. Nếu đồ thị có trọng số các cạnh là bằng nhau thì mọi
cây khung của nó đều là MST. Ví dụ này cho thấy đồ thị có thể có nhiều cây khung
nhỏ nhất. Tuy nhiên, trong phần tiếp theo ta sẽ thấy là nếu một đồ thị có trọng số các
cạnh là phân biệt (tức là không có hai cạnh nào có cùng trọng số), thì cây khung nhỏ
nhất của nó là duy nhất.
1.4.1 Một số tính chất
Thuộc tính chu trình
Định lý 1.4.1: Đối với mỗi chu trình đơn của đồ thị liên thông có trọng số
với trọng lượng cạnh phân biệt, cạnh nặng nhất trong chu trình không thuộc bất cứ
một MST nào của .
Chứng minh: Xem Hình 1.2a. Giả sử ngược lại, tức là cạnh nặng nhất e
thuộc
một MST. Xóa
của

từ một MST sẽ chia thành hai cây con tách rời với hai điểm cuối

trong cây con khác nhau. Có tồn tại một số cạnh

đầu cuối trong hai cây con khác nhau. Bởi vì 𝑤

trong chu trình với các
𝑤

, kết nối hai cây con lại

sẽ sinh ra một cây khung có trọng lượng nhỏ hơn. Do đó

bằng

không thuộc về

một MST.

(a) Các thuộc tính chu kỳ. Các cạnh đậm là

(b) Các thuộc tính cắt. Chỉ có các cạnh trong

MST. Các đường đứt minh họa của tách cây

cắt

được hiển thị.

Hình 1.2: Các thuộc tính chu kỳ và các thuộc tính cắt cắt.
Thuộc tính cắt
Định nghĩa: Cho

là tập đỉnh của một đồ thị ,|

. Cho

là hai tập con khác rỗng tạo thành phân hoạch của tập đỉnh

và
là

và

là tập các cạnh với có một đầu mút thuộc
𝑡

. Giả sử

còn đầu mút kia thuộc

. Khi đó

tạo thành một lát cắt trong đồ thị .
Định lý 1.4.2: Giả sử C là một lát cắt trong một đồ thị liên thông có trọng

số

với trọng lượng cạnh phân biệt, cạnh nhẹ nhất trong

phải thuộc một MST

của .
Chứng minh: Xem Hình 1.2b. Giả sử 𝑢 và 𝑣 biểu thị đỉnh điểm cuối của cạnh
nhẹ. Nếu

là cạnh duy nhất trong

trên đường đơn bất kỳ giữa 𝑢 và 𝑣, do đó

chứng minh là hiển nhiên bởi vì tất cả các đỉnh trong
MST. Ngược lại, giả sử ngược lại, tức là nhẹ nhất cạnh
Nó là rõ ràng có một số cạnh,, trong

phải được kết nối trong một
không thuộc về một MST.

trên đường giữa 𝑢 và 𝑣 trong MST giả định,

ngược lại thì hai đỉnh sẽ không được kết nối trong MST. Do 𝑤
bởi

𝑤

, thay thế

sẽ tạo ra một cây khung có trọng lượng nhỏ hơn. Do đó thuộc về một MST.
Sử dụng hai thuộc tính trên có thể chứng mình các kết quả sau:

Định lý 1.4.3: Cho

khác biệt, cho
, vậy thì

là một đồ thị liên thông có trọng số với trọng số cạnh

là một MST của

, và cho

là một cạnh bất kỳ trong

là cạnh nhẹ ở một lát cắt trong. Nếu

, vậy thì

Nếu

là cạnh nặng

nhất trong một chu trình của .
Tính duy nhất
Định lý 1.4.4: Một đồ thị liên thông có trọng số với trọng lượng số cạnh phân
biệt có một MST duy nhất.
Trong luận văn này, chúng tôi sẽ giả định rằng tất cả các đồ thị có trọng số
cạnh khác biệt. Như vậy, tất cả các đồ thị xét trong luận văn sẽ có MST duy nhất.
1.4.2. Rừng trải rộng tối thiểu và những giả định đồ thị
Chúng tôi đã xác định các bài toán MST cho các đồ thị liên thông. Thành phần
liên thông có ý nghĩa, vì theo định nghĩa của một cây, không tồn tại cây khung cho

các đồ thị không liên thông.
Một rừng khung được xác định bởi sự kết hợp của cây khung cho mỗi thành
phần liên thông trong một đồ thị. Tương tự, rừng khung tối thiểu (MSF) được xác
định như rừng khung với trọng số tối thiểu. Do đó, bài toán MSF là một sự tổng quát
của bài toán MST, và có thể được giải quyết bằng cách giải quyết các bài toán MST
cho từng thành phần liên thông trong đồ thị. Dễ dàng xác định các thành phần liên
thông của đồ thị trong thời gian tuyến tính nhờ sử dụng tìm kiếm theo chiều sâu
(DFS), và sau đó giải quyết các bài toán MST cho mỗi thành phần được liên thông.
Bài toán MST như là một chuyển hóa của bài toán MSF, chúng tôi sẽ đề cập
đến hai thuật ngữ thay thế cho nhau khi sự khác biệt là không đáng kể.

Đối với đồ thị đầu vào bất kỳ, nếu nó không phải là đơn đồ thị, chúng ta có
thể thực hiện một bước tính toán trước để loại bỏ các cạnh lặp và các khuyên. Bước
tính toán trước đó có thể được thực hiện trong thời gian tuyến tính bằng việc thực
hiện

𝑡𝑟

𝑡

được xây dựng dựa trên DFS.

Trong luận văn này, chúng tôi giả định là tất cả các đơn đồ thị và liên thông.
1.4.3 Thời gian tính
Trong phần này, chúng tôi sẽ trình bày thời gian chạy của các thuật toán MST
trong luận văn này, cũng như một số thuật toán quan trọng khác .
Các thuật toán MST nhận đầu vào đồ thị

có

đỉnh và

cạnh. Một hàm mô

tả chính xác độ phức tạp của bài toán MST cho đồ thị nói chung là chưa được xác
định cho đến thời điểm hiện tại. Luận văn sẽ cho thấy tồn tại một thuật toán chạy theo
thứ tự thời gian tối ưu của sự so sánh tổng số các trọng lượng cạnh, mặc dù các hàm
cho “tối ưu” là không rõ.
Dễ dàng chứng minh rằng đối với mọi ,

>2, luôn có thể xây dựng một đơn

đồ thị mà mỗi cạnh thuộc ít nhất một chu trình đơn. Do đó, để giải quyết các bài toán
MST, mỗi trọng số cạnh phải được xử lý ít nhất một lần, suy ra cận dưới cho độ phức
tạp của bài toán MST là Ω( ). Cận dưới tốt nhất hiện nay là

( ·𝛼 (, )) của

Chazelle[5]. Ở đây, 𝛼(, ) là nghịch đảo của hàm Ackermann tăng rất chậm, một
cách phát biểu nôm na là độ phức tạp của bài toán MST “gần như tuyến tính” với kích
thước đồ thị. Năm 1995, Karger et al. [10] trình bày một thuật toán MST ngẫu nhiên
với thời gian kỳ vọng là ( ). Thuật toán này hoạt động theo giả định rằng chúng ta
có quyền truy cập vào vô số bit thực sự ngẫu nhiên. Tuy nhiên, luận văn này sẽ chỉ
tập trung về trường hợp xấu nhất thời gian chạy cho các thuật toán tất định giải bài
toán MST.
Hàm

biểu thị tối thiểu (tối ưu) so sánh số trọng số cạnh cần thiết để

tìm MST của đồ thị bất kỳ với n đỉnh và m cạnh. Hàm

biểu thị tối thiểu (tối

ưu) số so sánh trọng số cạnh cần thiết để tìm MST của đồ thị G riêng biệt. Bảng 1.1.1

cho thấy thời gian chạy các thuật toán xác định MST khác nhau (và cây quyết định tối
ưu) với mật độ đồ thị khác nhau.
Lưu ý, các giới hạn thưa – dày là duy nhất cho mỗi thuật toán. Các thuật toán
được đề cập trong Luận văn này được viết với chữ đậm. Thuật toán được gọi là “tối
ưu” là thuật toán MST tối ưu của Pettie và Ramachandran [13], mà chúng tôi sẽ phân
tích trong luận văn này.
Bảng 1.1.1 cho thấy rằng thuật toán MST tồn tại với thời gian hoạt động tuyến
tính cho mật độ nhất định. Nhưng đối với các lớp trung gian của đồ thị “thưa”, chưa
có thuật toán MST với thời gian chạy tuyến tính. Tuy nhiên, như đã nói ở trên, luận
văn này sẽ trình bày một thuật toán mà chạy theo thứ tự “tối ưu” thời gian cho tất cả
các mật độ.
Thời gian chạy

Thuật toán

Đồ thị phẳng

Boruvka [4], 1926
DJP [9],[8], 1930

Kruskal, 1956
Kruskal, edges sorted by weight
Yao, 1974
Dense Case [8], 1987
Boruvka + DJP
Chazelle [5], 2000
Precomputed optimal decision tree for G
Optimal [13], 2002

Đồ thị thưa

Đồ thị dày

𝛼

Bảng 1.1: Thời gian chạy trường hợp tồi nhất các thuật toán MST, sắp xếp theo năm.
1.5. Các ứng dụng của bài toán MST
Cây bao trùm tối thiểu là hữu ích trong việc xây dựng lưới mạng, bằng cách
mô tả cách để kết nối một tập hợp các địa điểm bằng cách sử dụng tổng số chí phí của
dây nhỏ nhất. Phần lớn các công việc trên cây bao trùm tối thiểu đã được tiến hành
nghiên cứu và ứng dụng bởi các công ty truyền thông.

1.5.1. Truyền hình cáp
Một ví dụ là một công ty truyền hình cáp đặt cáp đến một khu phố mới. Nếu
nó là hạn chế để chôn cáp chỉ theo những con đường nhất định, do đó sẽ có một đồ

thị đại diện những điểm đó được nối với nhau bằng những con đường. Một trong số
những con đường có thể tốn kém hơn, bởi vì nó là dài hơn, hoặc yêu cầu các cáp
được chôn sâu hơn. Một cây bao trùm cho đồ thị đó sẽ là một tập hợp con của những
con đường mà không có chu kỳ nhưng vẫn kết nối đến từng nhà. Có thể có một vài
cây khung có thể tồn tại. Một cây bao trùm tối thiểu sẽ phải ràng buộc với tổng chi
phí thấp nhất.
1.5.2 Thiết kế mạch điện tử
Trong thiết kế mạch điện tử, nó thường là cần thiết để nối dây một số chân lại
với nhau để làm cho nó có điện tương đương. Một cây bao trùm tối thiểu cần chi phí
ít nhất của dây để kết nối một tập hợp điểm.
1.5.3 Quần đảo kết nối

Giả sử chúng ta có một nhóm các hòn đảo mà chúng ta muốn liên kết với cây
cầu để nó có thể đi du lịch từ một hòn đảo bất kỳ khác trong nhóm. Giả sử thêm rằng
chính phủ muốn chi tiêu số tiền tối thiểu về dự án này. Các kỹ sư có thể tính toán chi
phí cho một liên kết cầu mỗi cặp có thể có của hòn đảo. Tập hợp các cây cầu đó sẽ
giúp ta đi du lịch từ hòn đảo bất kỳ đến tất cả các đảo khác với chi phí tối thiểu cho
chính phủ là cây bao trùm tối thiểu.
1.5.4 Clustering biểu hiện dữ liệu gen (Thuật phân nhóm dữ liệu biểu hiện gen)
Cây bao trùm tối thiểu cũng cung cấp một phương pháp hợp lý để nhóm các
điểm trong không gian thành các nhóm tự nhiên. Ví dụ, Ying Xu và cộng sự [19] mô
tả một kết cấu mới biểu diễn cho một tập hợp các dữ liệu biểu hiện gene đa chiều như
một cây bao trùm tối thiểu. Một thuộc tính quan trọng của biểu diễn này là mỗi cụm
dữ liệu biểu hiện gen tương ứng với một cây con của MST, trong đó một cách chuyển
đổi chặt chẽ một bài toán phân nhóm đa chiều với một bài toán phân vùng cây. Họ đã

chứng minh rằng, mặc dù mối quan hệ giữa các dữ liệu là rất đơn giản trong các biểu

diễn MST, không có thông tin quan trọng bị mất cho các kết quả của phân nhóm. Họ
nhận thấy rằng có hai lợi thế quan trọng trong việc biểu diễn cho một tập hợp các dữ
liệu đa chiều như một MST. Một cấu trúc đơn giản của một cây thuận tiện cho việc
thực hiện hiệu quả chính xác của thuật toán phân cụm. Mặt khác là nó có thể vượt
qua nhiều bài toán phải đối mặt bởi các thuật toán phân nhóm cổ điển từ một phân
nhóm dựa trên MST không phụ thuộc vào hình dạng hình học chi tiết của một cụm.
Một công cụ mới được gọi là phần mềm EXCAVATOR, viết tắt của “EXpression
data Clustering Analysis and VisualizATiOn Resource,” đã được phát triển dựa trên
new framework. Các kết quả phân nhóm trên các dữ liệu biểu hiện gen (1) từ nấm
men Saccharomyces cerevisiae, (2) trong phản ứng nguyên bào sợi huyết thanh của
loài người, và (3) của Arabidopsis trong phản ứng để tìm ra chitin là rất hứa hẹn.
1.5.5 Xấp xỉ dựa trên MST
Trong các bài toán nhân viên bán hàng đi du lịch (TSP), chúng ta đưa ra một
đồ thị vô hướng hoàn chỉnh

có hàm trọng lượng w kết hợp với mỗi cạnh, và

chúng ta mong muốn tìm được một tour của

với trọng lượng tối thiểu. Bài toán

này đã được chứng minh là NP-khó ngay cả khi hàm trọng lượng thõa mãn bất đẳng
thức tam giác,

., cho tất cả ba đỉnh 𝑥 𝑦 𝑧

𝑤 𝑥 𝑧

𝑤 𝑥 𝑦

𝑤 𝑦𝑧 .

Các bất bình đẳng tam giác phát sinh trong nhiều tình huống thực tế. Nó có thể
được hiển thị mà các chiến lược tiếp theo cung cấp một thuật toán xấp xỉ với một tỷ
lệ của 2 ràng buộc cho các bài toán nhân viên bán hàng đi du lịch với bất đẳng thức
tam giác. Đầu tiên, hãy tìm một cây khung tối thiểu T đối với đồ thị cho trước. Sau
đó tăng gấp đôi MST và xây dựng một tour

. Cuối cùng, thêm các đường tắt để

không có đỉnh được truy cập nhiều hơn một lần, mà được thực hiện bởi một bộ cây
định trước. Kết quả là chiều dài các tour không quá hai lần là tối ưu. Nó cũng có thể
chỉ ra được rằng một cách tiếp cận dựa trên MST cũng cung cấp một xấp xỉ tốt cho
các bài toán cây Steiner.

1.6. Kỹ nghệ thuật toán (Algorithm Engineering)
1.6.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.
1.6.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.
Giải quyết các các vấn đề trừu tượng và mô hình máy trừu tượng (abstract
machine) có những điểm đáng chú ý trên lý thuyết:

– Các thuật toán được thiết kế với các vấn đề như vậy có thể áp dụng trên
nhiều ứng dụng cụ thể hóa trong các lĩnh vực khác nhau.
– Hầu hết các mô hình máy cổ điển đều tương đương với thời gian sai khác
không quá đa thức, tác động của thuật toán không được tính toán chi tiết.
– Trường hợp xấu nhất của thuật toán xảy ra không giống như trong thiết kế.
– Cho phép các máy tính độc lập thực hiện thuật toán để có thể so sánh về
trường hợp xấu nhất mà không cần trang bị gì thêm.
Từ quan điểm của lý thuyết thuật toán, việc áp dụng thuật toán là một phần
của việc thiết kế và phát triển phần mềm. Hiệu quả của thuật toán được đánh giá qua
những người chuyên môn trong lĩnh vực của ứng dụng đó.
Tuy nhiên, chúng ta nên lưu ý rằng đối với nhiều người tiên phong trong thuật

toán những ngày đầu, như Knuth, Floyd và những người khác, tất cả các thuật toán
mà họ thiết kế được đánh giá dựa vào tiêu chuẩn thực hành. Điều này làm thay đổi
quan điểm về thiết kế thuật toán, và dẫn đến yêu cầu phải phát triển các cấu trúc dữ
liệu tiên tiến để cài đặt các thuật toán.
Qua việc triển khai và thử nghiệm giữa lý thuyết và thực hành, nhiều nhà khoa
học đã nhận ra nhu cầu của việc thiết kế và phân tích từ thực tế ngày càng lớn. Một
nhóm các nhà nghiên cứu thuật toán bắt đầu tìm cách để khắc phục vấn đề này cách
đây 15 năm.
1.6.1.2. Nền tảng của Kỹ nghệ thuật toán
Qua cách tiếp cận thuật toán, chúng ta có thể thấy việc thực thi và thí nghiệm
có tầm quan trọng như việc phân tích và thiết kế. Cách tiếp cận này đã cho chúng ta
một khái niệm mới, đó là Kỹ nghệ thuật toán.
Thomas Kuhn tiến hành phân tích cấu trúc sự biến chuyển của khoa học và sử
dụng các mô hình khái niệm để miêu tả lại “sự kết hợp truyền thống của nghiên cứu
khoa học”. Theo Kuhn sự biến chuyển mô hình chỉ xảy ra khi mô hình cũ đang khủng

hoảng và không thể giải quyết được các vấn đề mới. Vậy sự kiện đòi hỏi mô hình
mới? Chúng ta sẽ liệt kê một vài ví dụ sau đây:
– Các mô hình máy tính Von – Neumann đã dần không còn thích hợp trong
thực tế với các việc như xử lý song song, xử lý pipelining, dự đoán trước, phân cấp
bộ nhớ và bộ nhớ đệm, xử lý đa luồng, và mô hình tính toán phân tán và song song.
– Trọng tâm của việc thiết kế thuật toán tập trung vào việc cải thiện đánh giá
tiệm cận trong trường hợp xấu nhất và đảm bảo thuật toán đưa ra kết quả xấp xỉ như
đã dự đoán. Điều này dẫn đến việc có nhiều thuật toán và cấu trúc dữ liệu được thiết
kế có nhiều ý tưởng mới nhưng không có tính thực tế. Đôi khi, điều đó không chắc
chắn rằng các thuật toán sẽ không được áp dụng. Dù vậy, việc áp dụng vào thực tế sẽ
rất khó khăn đến mức không ai muốn thử thực hiện việc này.

Điểm bất lợi của việc nghiên cứu thời gian chạy tiệm cận là chúng có thể ẩn đi
các hằng số rất lớn. Tương tự, yêu cầu bộ nhớ có thể là rất lớn cho dù là bị chặn bởi
đa thức.
– Như ví dụ cụ thể, chúng tôi có thể trích dẫn một số vấn đề trong thuật toán:
1.

Rất nhiều (không phải tất cả) sơ đồ xấp xỉ thời gian đa thức (PTAS),

chẳng hạn các sơ đồ của Aurora hoặc Mitchell cho bài toán người du lịch
(TSP), có hệ số rất lớn.
2.

Robins và Zelikovsky trình bày một hệ thống thuật toán giải bài toán

cây Steiner trong đồ thị với thời gian chạy là

, trong đó

là một

tham số ảnh hưởng đến hiệu suất. Đối với trường hợp lớn, thuật toán của họ
đạt cận tỷ lệ tốt nhất hiện nay là 1.55. Để cải tiến tốt nhất mức xấp xỉ bảo đảm
ở 1.598 bởi Hougardy và Prömel, cần thiết phải chọn

. Ngoài ra, còn

cần hơn 217 thiết bị đầu cuối.
3.

Câu hỏi liệu một đa giác đơn có thể được tam giác hóa trong thời gian

tuyến tính hay không là một trong những vấn đề chính trong hình học tính toán
nhiều năm qua. Năm 1990, vấn đề này cuối cùng đã được Chazelle giải quyết,

ông đã đưa ra một thuật toán với thời gian tuyến tính khá phức tạp. Theo
những kiến thức chúng tôi biết thì thuật toán này chưa bao giờ được áp dụng.
4.

Việc xây dựng hình học, được biết đến như một kỹ thuật cắt, cung cấp

một kỹ thuật phân vùng không gian cho bất kỳ kích thước hữu hạn nào mà
trong đó có vô số ứng dụng trong hình học tính toán. Tuy nhiên, thuật toán dựa
trên cuttings dường như cho thấy một thách thức đối với việc thực hiện.
Trong thực tế, yếu tố hằng số đóng vai trò khá lớn: trong các ứng dụng như
phẫu thuật có sự trợ giúp của máy tính, phục hồi thông tin bằng công cụ tìm kiếm,
hướng dẫn xe cộ, và nhiều ứng dụng khác, giải pháp này phải được tính trong thời
gian gần như tức thời. Trong các ứng dụng khác, năng suất của người sử dụng một
công cụ phần mềm có liên quan chặt chẽ với hiệu suất của công cụ. Ở đây bất kỳ sự
cải thiện nào đối với yếu tố hằng số đều xứng đáng được đầu tư. Vì vậy, việc cải tiến
yếu tố hằng số thường tạo ra khác biệt cho dù công cụ có được áp dụng hay không.
– Khái niệm về hiệu quả như khả năng giải quyết thời gian đa thức thường
không phù hợp. Thậm chí thời gian chạy nhỏ, nhưng siêu tuyến tính, mức độ đa thức
có thể quá chậm. Các ứng dụng thực tế, chẳng hạn trong thiết kế VLSI, tin sinh học,
hoặc xử lý dữ liệu không gian, yêu cầu phải xử lý các tập dữ liệu cực lớn. Trong
những trường hợp như vậy, chúng ta thường chỉ có thể áp dụng các thuật toán đòi hỏi
thời gian và không gian chạy tuyến tính, thậm chí cần các thuật toán thời gian dưới
tuyến tính. Trong thực tế, nghiên cứu về các thuật toán dưới tuyến tính gần đây đã

xuất hiện như là một lĩnh vực nghiên cứu mới. Thuật toán dưới tuyến tính hoặc chỉ
xem xét một mẫu nhỏ ngẫu nhiên của các dữ liệu đầu vào hoặc quá trình khi nó đến,
và sau đó trích một bản tóm tắt nhỏ.
– Như đã nêu ở trên, tiêu chí chính khi thiết kế thuật toán lý thuyết là tính hiệu
quả. Điều này đã kích thích sự phát triển của các cấu trúc dữ liệu rất tinh vi –cho dù
đối với nhiều cấu trúc, liệu chúng có được thực hiện một cách hợp lý hay không vẫn
là một câu hỏi. Tuy nhiên, trong thực tế, ngoài tính hiệu quả, những mục tiêu thiết kế
khác đều có vai trò quan trọng như nhau, đôi khi tầm quan trọng của một tiêu chí nào

đó thậm chí còn được đặt cao hơn, chẳng hạn tính linh hoạt, dễ sử dụng, bảo trì, …
Trong thực tế, cấu trúc dữ liệu và các thuật toán đơn giản được ưa thích hơn những
cái phức tạp.
– Các khía cạnh lý thuyết về các thuật toán thường đưa ra một bài thuyết trình
cấp cao, còn các chi tiết cần thiết để bắt đầu thực hiện thì để lại cho người đọc.
– Sự khởi đầu dễ dàng nhất để nghiên cứu và phát triển ý tưởng thuật toán mới
là từ vấn đề đơn giản. Tuy nhiên, cùng với tiến độ chung trong khoa học máy tính và
sự sẵn có của sức mạnh tính toán, các ứng dụng tự trở nên phức tạp hơn. Các ứng
dụng như vậy đòi hỏi một mô hình cẩn thận. Câu hỏi đặt ra là liệu kiến thức học được
cho các mô hình đơn giản có thể thay thế những mô hình phức tạp hơn.
– Dữ liệu đầu vào thực thường không phải là cấu trúc của các trường hợp khó
nhất được sử dụng trong phân tích lý thuyết. Do đó rất có thể là hiệu suất dự đoán là
không khả dụng.
– Công việc thử nghiệm tốt đòi hỏi sự nỗ lực đáng kể (thời gian, nhân lực, kỹ
năng lập trình, kinh nghiệm, …).
Trong nhiều thiết lập thử nghiệm, người ta thực hiện các thí nghiệm với các
trường hợp ngẫu nhiên. Điều này có thể gây hiểu nhầm lớn. Ví dụ, một vài đồ thị
ngẫu nhiên có một số thuộc tính cấu trúc làm cho chúng khác biệt với đồ thị trong thế

giới thực. Một ví dụ khác phát sinh trong tính toán hình học: một bộ mẫu thống nhất
của các điểm đảm bảo chắc chắn các điểm sẽ ở vị trí tùy ý. Tuy nhiên trong thực tế,
rất có khả năng không thực hiện giả thiết này.
Thật không may, làm việc với các dữ liệu đầu vào thực tế cũng có vấn đề của
nó: Những dữ liệu này có thể không có sẵn cho các nhà nghiên cứu hoặc có thể là độc
quyền. Để thu hẹp khoảng cách giữa thực tế và lý thuyết, Kỹ nghệ thuật toán
(Algorithm Engineering) đòi hỏi một phương pháp mở rộng hơn. Tuy nhiên,
Algorithm Engineering sẽ phải giữ được những lợi thế của lý thuyết:
– Tính tổng quát,

– Độ tin cậy, và
– Khả năng dự đoán.
Hy vọng là Algorithm Engineering sẽ làm tăng tác động của nó trên các lĩnh
vực khác một cách đáng kể. Kỹ nghệ thuật toán sẽ làm cho việc chuyển giao các ứng
dụng được tăng tốc.
1.6.1.3. Định nghĩa Kỹ nghệ thuật toán (Algorithm Engineering)
Một số chi tiết của Algorithm Engineering đã được trình bày tại các hội thảo
của DIMACS Implementation Challenges (http://dimacs.rutgers.edu/Challenges/):
“Những vấn đề được thực hiện bởi DIMACS giải quyết câu hỏi về việc xác
định hiệu suất thuật toán thực tế nơi mà những phân tích trường hợp xấu nhất là quá
bi quan và mô hình xác suất là quá phi thực tế: việc thử nghiệm có thể cung cấp các
hướng dẫn để thực hiện thuật toán thực tế khi mà phân tích không thành công.
Thí nghiệm cũng mang thuật toán gần gũi hơn với các vấn đề ban đầu, tạo nên
động lực cho các công trình lý thuyết. Nó cũng góp phần kiểm tra rất nhiều giả định
về phương pháp thực hiện và cấu trúc dữ liệu. Nó tạo ra một cơ hội để phát triển và
kiểm tra vấn đề, máy phát ví dụ, và các phương pháp khác để kiểm tra và so sánh
hiệu suất của thuật toán. Đó là một bước tiến trong việc chuyển giao công nghệ bằng

cách cung cấp các hệ thống xử lý của các thuật toán cho những người khác để sửa đổi
thích hợp.
Kể từ năm 1990, khi First Challenge bắt đầu với dòng chảy mạng, tổng cộng
chín thách thức thực hiện đã được tiến hành. Thuật ngữ Algorithm Engineering lần
đầu tiên được sử dụng với độ đặc hiệu và tác động đáng kể trong năm 1997, với việc
tổ chức Hội thảo đầu tiên về Algorithm Engineering (WAE 1997). Một vài năm trước
đây, David Bader, Bernard Moret, và Peter Sanders định nghĩa như sau:
“Algorithm Engineering đề cập đến quá trình cần thiết để biến đổi một thuật
toán từ bút chì trên giấy thành hiện thực, hiệu quả, kiểm nghiệm tốt, và dễ dàng sử
dụng. Vì vậy, nó bao gồm một số chủ đề, từ hành vi mẫu bộ nhớ cache đến các

nguyên tắc của công nghệ phần mềm; tuy nhiên trọng tâm chính của nó là thử
nghiệm. “
Chúng ta đồng ý rằng tất cả các chủ đề được đề cập đều là những phần quan
trọng của Algorithm Engineering, nhưng vẫn muốn có một cái nhìn rộng hơn về vấn
đề này. Một định nghĩa tổng quát hơn đã xuất hiện trong thông báo của ALCOM-FT
Summer School về Algorithm Engineering năm 2001:
“Algorithm Engineering liên quan với việc thiết kế, phân tích lý thuyết và thực
nghiệm, kỹ thuật và điều chỉnh các thuật toán, và đang thu hút được sự quan tâm
ngày càng tăng trong cộng đồng những người nghiên cứu thuật toán. Quy tắc mới nổi
này giải quyết các vấn đề về hiệu suất thuật toán thực tế bằng cách kết hợp cẩn thận
các phương pháp lý thuyết truyền thống cùng với các khảo sát thực nghiệm kỹ lưỡng.
“(Đăng trong DMANET vào ngày 17 tháng năm 2001 bởi Guiseppe Italiano).
1.6.1.4. Phương pháp luận
Phương pháp khoa học có nguồn gốc từ các ngành khoa học tự nhiên. Nó xem
khoa học như là một chu kỳ giữa lý thuyết và thực nghiệm. Lý thuyết có thể quy nạp
và diễn dịch một phần – theo lý thuyết dựa trên giả định cụ thể – xây dựng giả thuyết

Xem thêm: Game Góc Nhìn Thứ 3 Là Gì – Game Góc Nhìn “Người Thứ… Tư” Trông Như Thế Nào

thực nghiệm đã được thử nghiệm.
Các kết quả của các thí nghiệm lần lượt có thể dẫn đến giả thuyết hay lý thuyết
mới, v.v… Cũng giống như công nghệ phần mềm, Algorithm Engineering không phải
là một quá trình đơn giản. Lý tưởng nhất, người ta sẽ thiết kế một thuật toán, thực
hiện nó, và sử dụng nó. Tuy nhiên, các thuật toán tối ưu, tức là thuật toán tốt nhất để
giải quyết vấn đề trong một ứng dụng, và bước thực hiện cuối cùng không được biết
trước.
Trong Algorithm Engineering, một bằng chứng lý thuyết cho sự phù hợp đối
với một mục đích cụ thể được thay thế bởi một đánh giá thực nghiệm. Ví dụ, thử
nghiệm đó giúp kiểm tra liệu code được thiết lập có hiệu quả hoặc trong trường hợp
thuật toán gần đúng, thì mới có hiệu quả.

Thông thường, để đưa ra các kết quả đánh giá thực nghiệm đòi hỏi một phiên bản
thiết kế và thực hiện nữa. Vì vậy, như đã nêu trong DFG Priority Program 1307 [556]:
“Cốt lõi của Algorithm Engineering là một chu kỳ điều khiển bởi các giả
thuyết giả định.” [Www.algorithm-engineering.de]
Thông thường, phân tích được coi là một phần của chu kỳ này, dẫn đến một
chu kỳ mà trong đó bao gồm thiết kế, phân tích, thực hiện và đánh giá thử nghiệm các
thuật toán thực tế. Tuy nhiên, vì kết quả phân tích của thiết kế sẽ ngay lập tức đưa ra
phản hồi cho các nhà thiết kế và không đi qua thực hiện và thử nghiệm đầu tiên, nó
có vẻ thích hợp hơn khi để cho các giai đoạn phân tích là một phần của chu kỳ riêng
cùng với các thiết kế thuật toán. Như vậy, trong Hình 1.3, chu trình cốt lõi ở trung
tâm chỉ bao gồm thiết kế, thực hiện và thử nghiệm.
Algorithm Engineering luôn luôn được thúc đẩy bởi các ứng dụng thực tế.
Kịch bản ứng dụng xác định các phần cứng mà phải được làm giống thực nhất. Trong
giai đoạn đầu tiên của Algorithm Engineering, không chỉ là một mô hình máy tính tốt
đã được chọn, mà còn là vấn đề tự nó đã được mô hình hóa một cách thích hợp, mà

thường là bị loại trừ từ thiết kế thuật toán. Kết quả của một giai đoạn thử nghiệm có
thể sau đó yêu cầu một phiên bản của giai đoạn mô hình, vì các mô hình được lựa
chọn là không thích hợp. Đôi khi việc phân tích các mô hình được lựa chọn đã có thể
tiết lộ bất cập của nó. Điều này tạo ra một chu kỳ khác bao gồm các ứng dụng, mô
hình hóa và phân tích. Các ứng dụng cũng cung cấp dữ liệu thực tế để đánh giá thử
nghiệm và đánh giá thực nghiệm có thể tiết lộ nhu cầu xem xét thêm một số khía
cạnh khác cho loại dữ liệu cụ thể. Các thành phần đáng tin cậy từ các thư viện phần
mềm có thể dễ dàng hóa các nhiệm vụ. Người ta cho rằng một chương trình thiết kế
tốt nên được cung cấp trong một thư viện phần mềm để có thể tái sử dụng.
Rõ ràng, đây là một sự phụ thuộc tuần hoàn trong Algorithm Engineering.
Chúng ta dừng thảo luận với một trích dẫn từ DFG Priority Program 1307:

“Mô hình thực tế cho cả máy tính và các ứng dụng, cũng như các thư viện
thuật toán và các bộ sưu tập dữ liệu đầu vào thực tế cho phép tạo ra cầu nối chặt chẽ
với các ứng dụng.” [Www.algorithm-engineering.de]
1.6.1.5. Tình trạng của Kỹ nghệ thuật toán
Có rất nhiều hội nghị nói về kỹ nghệ thuật toán nhưng đa phần đều chỉ là một
phần nội dung của hội nghị chứ không phải tất cả. Hội nghị đầu tiên dành riêng cho
kỹ nghệ thuật toán là Workshop on Algorithm Engineering (WAE) được tổ chức tại
Venice (Italy) vào ngày 11 – 13, tháng 9 năm 1997. Đó là điểm khởi đầu của một loạt
các hội nghị hàng năm. Tại hội nghị WAE 5 ở Aarhus, Đan Mạch, 2001, WAE đã trở
thành một trong những hội nghị hàng đầu Châu Âu về các thuật toán ESA. Kể từ đó
hội nghị WAE trở thành hội nghị kiểu mẫu được công nhận. Sau WAE, một loạt hội
nghị ALENEX (Algorithm Engineering and Experiments) được tổ chức và thành lập.
ALENEX diễn ra hàng năm và chia sẻ với SODA, ACM-SIAM Symposium on
Discrete Algorithms về các thuật toán Discrete. Một trong những hội nghị mới về kỹ
nghệ thuật toán là SEA, hội nghị quốc tế về thực nghiệm thuật toán cho đến năm

2009 vẫn được biết đến là hội nghị WEA (Workshop on Experimental Algorithms).

Hình 1.3. Kỹ nghệ thuật toán
Tạp chí chính thức cho lĩnh vực này là tạp chí ACM Journal of Experimental
Algorithmics được xuất bản năm 1996. Tạp chí trở thành một kết nối cho các hoạt

2.2.3. Đống mềm ……………………………………………………………………………………………. 55C hương 3 …………………………………………………………………………………………………………….. 73THU ẬT TOÁN MST TỐI ƯU ……………………………………………………………………………… 733.1. Biểu diễn đồ thị …………………………………………………………………………………………… 733.2. Bổ đề chính và thủ tục ………………………………………………………………………………….. 753.2.1 Bổ đề chính. …………………………………………………………………………………………… 753.2.2 Phương pháp phân vùng. …………………………………………………………………………. 763.2.3 Thời gian tính phân vùng và thực thi. ………………………………………………………. 783.3. Thuật toán MST tối ưu …………………………………………………………………………………. 813.3.1 Thuật toán. …………………………………………………………………………………………….. 813.3.2 Thời gian thực thi. ………………………………………………………………………………… 853.3.3 Phân tích cây quyết định hành động. …………………………………………………………………………. 873.3.4 Kết luận thời hạn tính. ……………………………………………………………………………. 893.4 Thực hiện …………………………………………………………………………………………………….. 903.4.1 Thực hiện cụ thể ……………………………………………………………………………………. 903.4.2 Thông tin thực tiễn ………………………………………………………………………………….. 91C hương 4 …………………………………………………………………………………………………………….. 92TH ỰC NGHIỆM …………………………………………………………………………………………………. 924.1. Mục đích thực nghiệm và các thuật toán được lựa chọn để thực nghiệm ………………. 924.1.1. Mục đích ………………………………………………………………………………………………. 924.1.2. Các thuật toán ……………………………………………………………………………………….. 924.2. Môi trường và tài liệu thực nghiệm ………………………………………………………………… 934.2.1. Bộ dữ liệu thực nghiệm …………………………………………………………………………… 934.2.2. Môi trường thực nghiệm …………………………………………………………………………. 954.3. Mô tả setup các thuật toán …………………………………………………………………………… 954.4. Kết quả thực nghiệm ……………………………………………………………………………………. 964.5. Phân tích tác dụng thực nghiệm MST ………………………………………………………………… 98T ài liệu tìm hiểu thêm ……………………………………………………………………………………………….. 99P hụ lục ……………………………………………………………………………………………………………… 100 iiDANH MỤC BẢNG BIỂUBảng 1.1 : Thời gian chạy trường hợp tồi nhất các thuật toán MST, sắp xếp theo năm. ……………. 10B ảng 2.1 Thời gian thực thi của đống nhị phân, đống Fibonaccis, và Đống mềm. ……………….. 29B ảng 2.2 : Giá trị của ……………………………………………………………………………….. 54B ảng 4.1 : Các thuật toán được lựa chọn thực nghiệm …………………………………………………. 92 với tỷ lệ đồ thịBảng 4.2 Giá trị của ………………………………………………. 93 với tỷ lệ đồ thịBảng 4.3 : Giá trị của ……………………………………….. 93B ảng 4.4 : Giá trịvới tỷ lệ đồ thị ……………………………………………….. 94B ảng 4.5 Giá trịvới tỷ lệ đồ thị ……………………………………………………. 94B ảng 4.6 Giá trị củavới tỷ lệ đồ thị …………………………………….. 94B ảng 4.7 Giá trị củavới tỷ lệ đồ thị ……………………………….. 94B ảng 4.8 Giá trị củavới tỷ lệ đồ thị …………………………………………….. 94B ảng C. 1 : Thể hiện giá trị của, của đơn đồ thị cóđỉnh, cạnh với tỷ lệ đồ thịBảng C. 2 : Thể hiện giá trị của, của đơn đồ thị cóđỉnh, đỉnh, đơn đồ thị cóđỉnhđơn đồ thị cóđỉnhđỉnhđỉnh, và thời hạn chạy t ( ms ) của các thuật toán tìm MST củavà thời hạn chạy t ( ms ) của các thuật toán tìm MST củacạnh với tỷ lệ đồ thịBảng C. 7 : Thể hiện giá trị củađơn đồ thị có …………………………… 107 cạnh với tỷ lệ đồ thị ……………………………………………………….. 108B ảng C. 6 : Thể hiện giá trị củađơn đồ thị có …………………………………… 106 và thời hạn chạy t ( ms ) của các thuật toán tìm MST củacạnh với tỷ lệ đồ thịBảng C. 5 : Thể hiện giá trị của …………………………. 105 và thời hạn chạy t ( ms ) của các thuật toán tìm MST củacạnh với tỷ lệ đồ thịBảng C. 4 : Thể hiện giá trị của ……………………………….. 104 và thời hạn chạy t ( ms ) của các thuật toán tìm MSTcạnh với tỷ lệ đồ thịBảng C. 3 : Thể hiện giá trị củađơn đồ thị cóvà thời hạn chạy t ( ms ) của các thuật toán tìm MST. …………………………………….. 109 và thời hạn chạy t ( ms ) của các thuật toán tìm MST củacạnh với tỷ lệ đồ thịiii. ……………………………………. 110H ình 1.1 : Đơn đồ thị liên thôngvớivà …………………………………………….. 4H ình 1.2 : Các thuộc tính chu kỳ luân hồi và các thuộc tính cắt cắt. ……………………………………………. 7H ình 1.3. Kỹ nghệ thuật toán ………………………………………………………………………………….. 21H ình 2.1 : Một đồ thị vớiđỉnh xác lập bởi ( ( 1, 2 ), ( 1, 3 ), ( 2, 3 ) ) và cây quyết định hành động tốiưu nối cứng của nó. ……………………………………………………………………………………………….. 49H ình 2.2 : Cấu trúc tài liệu Đống mềm với ba hàng đợi mềm ……………………………………….. 58H ình B. 1 : Ví dụ về tinh lọc, khởi đầu từ một sự tái diễn link lại. ………………………………. 100H ình B. 2.1 : Đồ thị nguồn vào. Hình B. 2.2 : Sau khi phân vùng …………………………………….. 102H ình B. 2.3 : Sau cây quyết định hành động. Hình B. 2.4 : Đồ thị liên kết Ga. ……………………………….. 103H ình B. 2.5 : Sau DenseCase. Hình B. 2.6 : Cạnh ứng viên Gb. ……………………………………. 103H ình B. 2.7 : cạnh MST T’được tìm thấy bởi Boruvka2. ……………………………………………… 104H ình C. 1 : Đồ thị biểu lộ thời hạn chạy t của các thuật toán trên đồ thị ngẫu nhiên với mậtđộ đồ thị ( trục Ox màn biểu diễn, Oy trình diễn 𝑡 𝑠 ) ………………………………….. 105H ình C. 2 : Đồ thị biểu lộ thời hạn chạy t của các thuật toán trên đồ thị ngẫu nhiên với mật độđồ thị ( trục Ox màn biểu diễn m, Oy màn biểu diễn t ( s ) ) ……………………………………. 106H ình C. 3 : Đồ thị bộc lộ thời hạn chạy t của các thuật toán trên đồ thị ngẫu nhiên với mậtđộ đồ thị ( trục Ox màn biểu diễn, Oy trình diễn 𝑡 𝑠 ) ………………………………… 107H ình C. 4 : Đồ thị biểu lộ thời hạn chạy t của các thuật toán trên đồ thị ngẫu …………….. 108 nhiên với tỷ lệ đồ thị ( trục Ox trình diễn, Oy màn biểu diễn 𝑡 𝑠 ) ………………. 108H ình C. 5 : Đồ thị biểu lộ thời hạn chạy t của các thuật toán trên đồ thị ngẫu nhiên với mậtđộ đồ thị ( trục Ox màn biểu diễn, Oy màn biểu diễn 𝑡 𝑠 ) ……………………….. 109H ình C. 6 : Đồ thị biểu lộ thời hạn chạy t của các thuật toán trên đồ thị ngẫu nhiên với mậtđộ đồ thị ( trục Ox trình diễn, Oy trình diễn 𝑡 ) ………………………. 110H ình C. 7 : Đồ thị biểu lộ thời hạn chạy t ( ms ) của các thuật toán trên đồ thị ngẫu nhiên vớimật độ đồ thị𝑥 ( trục Ox biểu diễniv, Oy màn biểu diễn 𝑡 ) …………………………….. 111C hương 1GI ỚI THIỆU TỔNG QUAN1. 1 Lịch sử của bài toán cây khung nhỏ nhấtCho G = ( V, E ) ( V là tập đỉnh, E là tập cạnh ) là đồ thị vô hướng liên thông cótrọng số trên cạnh 𝑤. Giả sử T là một cây khung của G, ta gọi trọng số củacây T là tổng trọng số các cạnh trong T. Bài toán đặt ra là trong số các cây khungcủa G, hãy tìm cây khung có trọng số nhỏ nhất. Cây khung như vậy được gọi là câykhung nhỏ nhất của đồ thị ( minimum spanning tree ) và bài toán đặt ra được gọi là bàitoán cây khung nhỏ nhất. Năm 1926, nhà toán học người Séc Otakar Boruvka diễn đạt một thuật toán giải ” một số ít bài toán cực tiểu hoá ” [ 4 ]. Ông đã yêu cầu các thuật toán để tối ưu hoá mạnglưới điện. Vào thời Boruvka chưa có các khái niệm về đồ thị và cây khung tối thiểu. Thuật toán của ông là thuật toán giải bài toán cây khung nhỏ nhất được biết đến sớmnhất. Ngày nay thuật toán này được gọi là thuật toán của Boruvka. Trong luận văn, cây khung nhỏ nhất được gọi tắt là ” MST “. Năm 1930, một thuật toán MST khác được phát hiện bởi nhà toán học SécJarn ‘ ık [ 9 ]. Thuật toán này được yêu cầu độc lập bởi nhà toán học và khoa học máytính người Mỹ Prim vào năm 1957, và sau đó tái mày mò bởi các nhà khoa học máytính Hà Lan Dijkstra trong năm 1959. Do đó, thuật toán đôi lúc được gọi là thuật toáncủa Prim, thuật toán của Jarn ‘ ık, thuật toán Prim-Jarn ‘ ık hoặc thuật toán DJP. Trongluận văn này, chúng tôi gọi thuật toán này là thuật toán DJP.Thuật toán Kruskal là một thuật toán trong kim chỉ nan đồ thị để tìm cây baotrùm tối thiểu của một đồ thị liên thông có trọng số. Nói cách khác, nó tìm một tậphợp các cạnh tạo thành một cây chứa tổng thể các đỉnh của đồ thị và có tổng trọng sốcác cạnh là nhỏ nhất. Thuật toán Kruskal là một ví dụ của thuật toán tham lam. Thuậttoán này xuất bản lần tiên phong năm 1956, bởi Joseph KruskalNhiều thuật toán MST văn minh sử dụng các ý tưởng sáng tạo từ thuật toán Boruvka vàDJP. Cụ thể là các thuật toán MST tối ưu được nghiên cứu và điều tra trong luận văn này sửdụng rất nhiều ý tưởng sáng tạo từ cả hai thuật toán. Kể từ khi ý tưởng ra các thuật toán, cácbài toán MST đã được nghiên cứu và điều tra rất nhiều, nhưng chưa ai tìm ra được cận dướichính xác cho độ phức tạp thời hạn của bài toán MST. Thuật toán MST tối ưu nghiêncứu trong luận văn này được phong cách thiết kế bởi Pettie và Ramachandran [ 13 ] vào năm 2002. Các tác giả đã chứng tỏ rằng các thuật toán chạy trong thời hạn tối ưu, nhưngkhông thể đưa ra một cận dưới đúng mực thấp hơn. Thuật toán này sẽ được trình bàyở chương 3. Phần tiếp theo của chương này sẽ trình diễn phát biểu bài toán cây khung nhỏnhất, tổng quan về các thuật toán MST quan trọng. Trước hết tất cả chúng ta sẽ đưa ra cácký hiệu toán học được sử dụng trong luận văn, cũng như 1 số ít kỹ năng và kiến thức cơ bản củalý thuyết đồ thị. 1.2 Các ký hiệu toán họcTrong luận văn, ta sẽ sử dụng ký hiệu log =, ký hiệuVới số nguyênvàVí dụ :, đó là logarithm với cơ số 2. được định nghĩa quy nạp như sau : logloglog. Ký hiệuđược định nghĩa là { |, nghĩa là, số lầncác hàm logarithm phải được vận dụng cho đến khi thu được hiệu quả lànày tăng rất chậm, và. Hàm sốlà nhỏ hơn 6 cho tổng thể các giá trị ” thực ” của. Giai thừa của 1 số ít nguyên dương n, kí hiệu là n !, được định nghĩa làHàm n ! hoàn toàn có thể định nghĩa đệ qui bởi :. Đối với số nguyên không âmvànghĩa đệ quy như sau : và ! = ( − 1 ). Dễ dàng thấy làhàm Ackermann 𝐴 (, ) được định { 𝐴𝐴 ( Một đặc thù quan trọng của 𝐴là giá trị của nó tăng rất nhanh. Gọi𝐴 ′ ( ) = 𝐴 (, ). Khi đó 𝐴 ′ tăng rất nhanh, ngược lại hàm nghịch đảo của nó 𝐴tăngrất chậm. Hàm nghịch đảo của hàm Ackermann được ký hiệu là 𝛼. Hàm 𝛼 ( ) là nhỏhơn 5 cho toàn bộ giá trị ” thực ” của. Hàm nghịch đảo Ackermann hai tham số đượcđịnh nghĩa bởi 𝛼 (, ) = min { ≥ 1 | 𝐴 (, [ / ] ) ≥ log }. Chú ý là hàm 𝛼 tăng rấtchậm. Đối với số nguyên ≥ 1, hàm 𝛽 (, ) được định nghĩa là 𝛽 ≥ 0 và { |, nghĩa là 𝛽 (, ) là số lần các hàm logarithm được ápdụng đối vớiđể thu được tác dụng là ≤ /. 1.3 Lý thuyết đồ thịĐồ thị vô hướng G là một kiểu tài liệu trừu tượng được xác lập bởi, trong đólà một tập đỉnh vàthứ tự. Ta sẽ ký hiệulà một tập cạnh, đó là các cặp đỉnh không có = | |, và tập đỉnh = | | và. Lớp các đồ thị vớiĐể chỉ ra tập đỉnh của đồ thị. Một cạnhhiệu bởiđỉnh vàta dùng kí hiệu bởi { 𝑣 𝑣𝑣, tập cạnhcạnh được ký hiệu là, và tập cạnh của nó được kínối hai đỉnh 𝑣 và 𝑣, và được ký hiệu 𝑣 𝑣. Theođịnh nghĩa của một đồ thị vô hướng, một cạnh là một cặp không có thứ tự gồm haiđỉnh, vì thế 𝑣dương 𝑤thì𝑣 𝑣. Mỗi cạnhcủa đồ thị sẽ được gán một trọng sốcó thể hiểu đó là ngân sách của ” sử dụng ” cạnh. Nếu 𝑤được coi là nhẹ hơnnặng hơnvới. Để đơn thuần, toàn bộ các ví dụ đồ thịtrong luận văn này sẽ có trọng số cạnh tương ứng với khoảng cách Euclide giữa cácđiểm cuối. Điều này là một giả định phổ cập trong các ví dụ thực tế, ví dụ điển hình nhưmạng lưới đường đi bộ và mạng lưới điện hoặc dây tài liệu. Bậc của một đỉnh v, ký hiệubởi𝑣 là số cạnh kề với nó ( nhận nó là đầu mút ). Một đường đi trong đồ thị làmột dãy các đỉnh và cạnh xen kẽ khởi đầu từ một đỉnh và kết thúc tại một đỉnh. Nhưvậy, mỗi cạnh trên đường đi sẽ liên kết giữa một đỉnh với một đỉnh đi sau nó. Như vậyđường đi hoàn toàn có thể diễn đạt bởi dãy : 𝑣𝑣 𝑣Ta gọi quy trình là một đường đi không chứa cạnh lặp lại khởi đầu và kết thúctại cùng một đỉnh, nghĩa là 𝑣. Một đường đi được gọi là đường đi đơnnếu các đỉnh trên nó là phân biệt. Tương tự như vậy, một quy trình đơn là một chutrình mà các đỉnh trên nó là phân biệt, ngoại trừ đỉnh khởi đầu và kết thúc. với 𝒏Hình 1.1 : Đơn đồ thị liên thôngvà 𝒎 { 𝑣, …, 𝑣 } vàVí dụ : Hình 1.1 cho một ví dụ về đồ thị G = ( V, E ) với { 𝑣 𝑣𝑣 𝑣𝑣 𝑣bởi đoạn tô đậm ) 𝑣𝑣 𝑣đơn. cạnhtrênDãychấm ) 𝑣 ( các𝑣 𝑣𝑣 𝑣𝑣 𝑣𝑣 𝑣. Dãy ( các cạnh trên đường đi thể hiện𝑣 𝑣đường𝑣 𝑣đithể𝑣 𝑣cho ta ví dụ một đường đihiệnbởiđoạngạch𝑣 cho ta ví dụ về một chutrình đơn. Một đồ thị được gọi liên thông nếu luôn tìm được đường đi giữa hai đỉnh bấtkỳ. Ta gọi khuyên là một cạnh nối một đỉnh với chính nó, tức là cạnh có dạng𝑣 𝑣. Cạnh như vậy sẽ được tính hai lần trongvà𝑣. Hai cạnh khác nhau, là cạnh song song ( hay cạnh lặp ) nếu chúng cùng nối một cặp đỉnh. Một đồ thịcó chứa cạnh lặp được gọi là đa đồ thị. Một đồ thị có chứa cạnh lặp và khuyên đượcgọi là giả đồ thị. Ta gọi đơn đồ thị là đồ thị vô hướng không có khuyên và không cócác cạnh lặp. Từ định nghĩa, tập cạnhcủa đơn đồ thị là một tập các bộ không có thứtự gồm hai đỉnh. Bậc lớn nhất của một đỉnh trong một đơn đồ thị là, và bậc củamột đỉnh là số đỉnh lân cận với nó. Đồ thị trong hình 1.1 là một đơn đồ thị liênthông. Nếu đồ thị là không liên thông, đồ thị con liên thông cực lớn của nó được gọilà thành phần được liên thông. Có thể chứng tỏ được rằng số lượng cạnh trong một đơn đồ thị liên thôngluôn lớn hơn hoặc bằng n-1. Vì vậy, cây là đồ thị liên thông có ít cạnh nhất. Ta gọirừng là đồ thị mà mỗi thành phần liên thông là một cây. Một trường hợp đặc biệt quan trọng của một đơn đồ thị liên thông là đồ thị không thiếu. Đồ thịđầy đủ là đồ thị có toàn bộ các cạnh hoàn toàn có thể. Tổng số cạnh của đồ thị khá đầy đủ là, nghĩa là số cạnh của đồ thị rất đầy đủ là. Đồ thị vừa đủ vớiđỉnh được ký hiệu Kn. Trong suốt luận văn này, tất cả chúng ta sẽ định nghĩa tỷ lệ của một đồ thị là tỷ lệgiữa số cạnh và số đỉnh, đó là bằng m / n. Số cạnh m trong một đơn đồ thị liên thông nđỉnh thoả mãn bất đẳng thức : khoảngvà. Như vậy m nằm trong. Một đồ thị được gọi là đồ thị thưa nếutự, đồ thị dày là đồ thị cólà nhỏ. Tươnglà lớn. Quan niệm “ nhỏ ” / ” lớn ” sẽ được nêu rõ trongphạm vi ứng dụng đơn cử. Một trường hợp đồ thị thưa đặc biệt quan trọng là đồ thị phẳng. Đồ thịphẳng là đồ thị hoàn toàn có thể vẽ trong mặt phẳng sao cho hai cạnh bất kể là không giao nhau, ngoại trừ tại đỉnh. Ta cóĐịnh lý 1.3 : Đồ thị phẳng đơn liên thông vớiđỉnh có ≤ 3 − 6 cạnh. Do đó, so với một đồ thị phẳng, tỷ lệ được số lượng giới hạn bởi một hằng số, ta có = ( ). Do ta có cận dưới cho số lượng cạnh của đơn đồ thị liên thông lànên kích cỡ nguồn vào của bất kể đơn đồ thị liên thông vớicạnh là. Do đó, thời hạn thiết yếu để thiết kế xây dựng một đơn đồ thị liên thông vớicạnh là1. 4. Cây khung nhỏ nhấtĐịnh nghĩa : Cho G là một đồ thị liên thông. Một cây khung của G là một câychứa tổng thể các đỉnh với tập cạnh là tập con của tập cạnh của G. Nói cách khác câykhung là một cây bao trùm toàn bộ các đỉnh trong G.Định nghĩa : Cho T là một cây khung của một đồ thị liên thông có trọng số. Trọng lượng của T được xác lập bằng tổng trọng số của các cạnh trong T : Định nghĩa : Cho G là một đồ thị liên thông có trọng số. Cây khung nhỏ nhất ( MST ) của G là cây khung của G với trọng số là nhỏ nhất. Rõ ràng là từ định nghĩa, MST là một lời giải cho các bài toán trong đó đòi hỏiphải so sánh các trọng số cạnh. Nếu đồ thị có trọng số các cạnh là bằng nhau thì mọicây khung của nó đều là MST. Ví dụ này cho thấy đồ thị hoàn toàn có thể có nhiều cây khungnhỏ nhất. Tuy nhiên, trong phần tiếp theo ta sẽ thấy là nếu một đồ thị có trọng số cáccạnh là phân biệt ( tức là không có hai cạnh nào có cùng trọng số ), thì cây khung nhỏnhất của nó là duy nhất. 1.4.1 Một số tính chấtThuộc tính chu trìnhĐịnh lý 1.4.1 : Đối với mỗi quy trình đơn của đồ thị liên thông có trọng sốvới khối lượng cạnh phân biệt, cạnh nặng nhất trong quy trình không thuộc bất cứmột MST nào của. Chứng minh : Xem Hình 1.2 a. Giả sử ngược lại, tức là cạnh nặng nhất ethuộcmột MST. Xóacủatừ một MST sẽ chia thành hai cây con tách rời với hai điểm cuốitrong cây con khác nhau. Có sống sót một số ít cạnhđầu cuối trong hai cây con khác nhau. Bởi vì 𝑤trong quy trình với các, liên kết hai cây con lạisẽ sinh ra một cây khung có khối lượng nhỏ hơn. Do đóbằngkhông thuộc vềmột MST. ( a ) Các thuộc tính chu kỳ luân hồi. Các cạnh đậm là ( b ) Các thuộc tính cắt. Chỉ có các cạnh trongMST. Các đường đứt minh họa của tách câycắtđược hiển thị. Hình 1.2 : Các thuộc tính chu kỳ luân hồi và các thuộc tính cắt cắt. Thuộc tính cắtĐịnh nghĩa : Cholà tập đỉnh của một đồ thị, |. Cholà hai tập con khác rỗng tạo thành phân hoạch của tập đỉnhvàlàvàlà tập các cạnh với có một đầu mút thuộc. Giả sửcòn đầu mút kia thuộc. Khi đótạo thành một lát cắt trong đồ thị. Định lý 1.4.2 : Giả sử C là một lát cắt trong một đồ thị liên thông có trọngsốvới khối lượng cạnh phân biệt, cạnh nhẹ nhất trongphải thuộc một MSTcủa. Chứng minh : Xem Hình 1.2 b. Giả sử 𝑢 và 𝑣 bộc lộ đỉnh điểm cuối của cạnhnhẹ. Nếulà cạnh duy nhất trongtrên đường đơn bất kể giữa 𝑢 và 𝑣, do đóchứng minh là hiển nhiên do tại toàn bộ các đỉnh trongMST. Ngược lại, giả sử ngược lại, tức là nhẹ nhất cạnhNó là rõ ràng có một số ít cạnh, , trongphải được liên kết trong mộtkhông thuộc về một MST.trên đường giữa 𝑢 và 𝑣 trong MST giả định, ngược lại thì hai đỉnh sẽ không được liên kết trong MST. Do 𝑤bởi, thay thếsẽ tạo ra một cây khung có khối lượng nhỏ hơn. Do đó thuộc về một MST.Sử dụng hai thuộc tính trên hoàn toàn có thể chứng mình các hiệu quả sau : Định lý 1.4.3 : Chokhác biệt, cho, vậy thìlà một đồ thị liên thông có trọng số với trọng số cạnhlà một MST của, và cholà một cạnh bất kể tronglà cạnh nhẹ ở một lát cắt trong. Nếu, vậy thìNếulà cạnh nặngnhất trong một quy trình của. Tính duy nhấtĐịnh lý 1.4.4 : Một đồ thị liên thông có trọng số với khối lượng số cạnh phânbiệt có một MST duy nhất. Trong luận văn này, chúng tôi sẽ giả định rằng tổng thể các đồ thị có trọng sốcạnh độc lạ. Như vậy, tổng thể các đồ thị xét trong luận văn sẽ có MST duy nhất. 1.4.2. Rừng trải rộng tối thiểu và những giả định đồ thịChúng tôi đã xác lập các bài toán MST cho các đồ thị liên thông. Thành phầnliên thông có ý nghĩa, vì theo định nghĩa của một cây, không sống sót cây khung chocác đồ thị không liên thông. Một rừng khung được xác lập bởi sự phối hợp của cây khung cho mỗi thànhphần liên thông trong một đồ thị. Tương tự, rừng khung tối thiểu ( MSF ) được xácđịnh như rừng khung với trọng số tối thiểu. Do đó, bài toán MSF là một sự tổng quátcủa bài toán MST, và hoàn toàn có thể được xử lý bằng cách xử lý các bài toán MSTcho từng thành phần liên thông trong đồ thị. Dễ dàng xác lập các thành phần liênthông của đồ thị trong thời hạn tuyến tính nhờ sử dụng tìm kiếm theo chiều sâu ( DFS ), và sau đó xử lý các bài toán MST cho mỗi thành phần được liên thông. Bài toán MST như thể một chuyển hóa của bài toán MSF, chúng tôi sẽ đề cậpđến hai thuật ngữ thay thế sửa chữa cho nhau khi sự độc lạ là không đáng kể. Đối với đồ thị đầu vào bất kể, nếu nó không phải là đơn đồ thị, tất cả chúng ta cóthể thực thi một bước thống kê giám sát trước để vô hiệu các cạnh lặp và các khuyên. Bướctính toán trước đó hoàn toàn có thể được triển khai trong thời hạn tuyến tính bằng việc thựchiện𝑡𝑟được thiết kế xây dựng dựa trên DFS.Trong luận văn này, chúng tôi giả định là toàn bộ các đơn đồ thị và liên thông. 1.4.3 Thời gian tínhTrong phần này, chúng tôi sẽ trình diễn thời hạn chạy của các thuật toán MSTtrong luận văn này, cũng như 1 số ít thuật toán quan trọng khác. Các thuật toán MST nhận đầu vào đồ thịcóđỉnh vàcạnh. Một hàm môtả đúng mực độ phức tạp của bài toán MST cho đồ thị nói chung là chưa được xácđịnh cho đến thời gian hiện tại. Luận văn sẽ cho thấy sống sót một thuật toán chạy theothứ tự thời hạn tối ưu của sự so sánh tổng số các khối lượng cạnh, mặc dầu các hàmcho ” tối ưu ” là không rõ. Dễ dàng chứng tỏ rằng so với mọi, > 2, luôn hoàn toàn có thể kiến thiết xây dựng một đơnđồ thị mà mỗi cạnh thuộc tối thiểu một quy trình đơn. Do đó, để xử lý các bài toánMST, mỗi trọng số cạnh phải được giải quyết và xử lý tối thiểu một lần, suy ra cận dưới cho độ phứctạp của bài toán MST là Ω ( ). Cận dưới tốt nhất lúc bấy giờ là ( · 𝛼 (, ) ) củaChazelle [ 5 ]. Ở đây, 𝛼 (, ) là nghịch đảo của hàm Ackermann tăng rất chậm, mộtcách phát biểu nôm na là độ phức tạp của bài toán MST ” gần như tuyến tính ” với kíchthước đồ thị. Năm 1995, Karger et al. [ 10 ] trình diễn một thuật toán MST ngẫu nhiênvới thời hạn kỳ vọng là ( ). Thuật toán này hoạt động giải trí theo giả định rằng chúng tacó quyền truy vấn vào vô số bit thực sự ngẫu nhiên. Tuy nhiên, luận văn này sẽ chỉtập trung về trường hợp xấu nhất thời hạn chạy cho các thuật toán tất định giải bàitoán MST.Hàmbiểu thị tối thiểu ( tối ưu ) so sánh số trọng số cạnh thiết yếu đểtìm MST của đồ thị bất kể với n đỉnh và m cạnh. Hàmbiểu thị tối thiểu ( tốiưu ) số so sánh trọng số cạnh thiết yếu để tìm MST của đồ thị G riêng không liên quan gì đến nhau. Bảng 1.1.1 cho thấy thời hạn chạy các thuật toán xác lập MST khác nhau ( và cây quyết định hành động tốiưu ) với tỷ lệ đồ thị khác nhau. Lưu ý, các số lượng giới hạn thưa – dày là duy nhất cho mỗi thuật toán. Các thuật toánđược đề cập trong Luận văn này được viết với chữ đậm. Thuật toán được gọi là ” tốiưu ” là thuật toán MST tối ưu của Pettie và Ramachandran [ 13 ], mà chúng tôi sẽ phântích trong luận văn này. Bảng 1.1.1 cho thấy rằng thuật toán MST sống sót với thời hạn hoạt động giải trí tuyếntính cho tỷ lệ nhất định. Nhưng so với các lớp trung gian của đồ thị ” thưa “, chưacó thuật toán MST với thời hạn chạy tuyến tính. Tuy nhiên, như đã nói ở trên, luậnvăn này sẽ trình diễn một thuật toán mà chạy theo thứ tự ” tối ưu ” thời hạn cho tất cảcác tỷ lệ. Thời gian chạyThuật toánĐồ thị phẳngBoruvka [ 4 ], 1926DJP [ 9 ], [ 8 ], 1930K ruskal, 1956K ruskal, edges sorted by weightYao, 1974D ense Case [ 8 ], 1987B oruvka + DJPChazelle [ 5 ], 2000P recomputed optimal decision tree for GOptimal [ 13 ], 2002 Đồ thị thưaĐồ thị dàyBảng 1.1 : Thời gian chạy trường hợp tồi nhất các thuật toán MST, sắp xếp theo năm. 1.5. Các ứng dụng của bài toán MSTCây bao trùm tối thiểu là hữu dụng trong việc thiết kế xây dựng lưới mạng, bằng cáchmô tả cách để liên kết một tập hợp các khu vực bằng cách sử dụng tổng số chí phí củadây nhỏ nhất. Phần lớn các việc làm trên cây bao trùm tối thiểu đã được tiến hànhnghiên cứu và ứng dụng bởi các công ty truyền thông online. 101.5.1. Truyền hình cápMột ví dụ là một công ty truyền hình cáp đặt cáp đến một thành phố mới. Nếunó là hạn chế để chôn cáp chỉ theo những con đường nhất định, do đó sẽ có một đồthị đại diện thay mặt những điểm đó được nối với nhau bằng những con đường. Một trong sốnhững con đường hoàn toàn có thể tốn kém hơn, do tại nó là dài hơn, hoặc nhu yếu các cápđược chôn sâu hơn. Một cây bao trùm cho đồ thị đó sẽ là một tập hợp con của nhữngcon đường mà không có chu kỳ luân hồi nhưng vẫn liên kết đến từng nhà. Có thể có một vàicây khung hoàn toàn có thể sống sót. Một cây bao trùm tối thiểu sẽ phải ràng buộc với tổng chiphí thấp nhất. 1.5.2 Thiết kế mạch điện tửTrong phong cách thiết kế mạch điện tử, nó thường là thiết yếu để nối dây 1 số ít chân lạivới nhau để làm cho nó có điện tương tự. Một cây bao trùm tối thiểu cần chi phíít nhất của dây để liên kết một tập hợp điểm. 1.5.3 Quần đảo kết nốiGiả sử tất cả chúng ta có một nhóm các hòn hòn đảo mà tất cả chúng ta muốn link với câycầu để nó hoàn toàn có thể đi du lịch từ một hòn hòn đảo bất kể khác trong nhóm. Giả sử thêm rằngchính phủ muốn tiêu tốn số tiền tối thiểu về dự án Bất Động Sản này. Các kỹ sư hoàn toàn có thể đo lường và thống kê chiphí cho một link cầu mỗi cặp hoàn toàn có thể có của hòn hòn đảo. Tập hợp các cây cầu đó sẽgiúp ta đi du lịch từ hòn hòn đảo bất kể đến tổng thể các hòn đảo khác với ngân sách tối thiểu chochính phủ là cây bao trùm tối thiểu. 1.5.4 Clustering bộc lộ tài liệu gen ( Thuật phân nhóm tài liệu bộc lộ gen ) Cây bao trùm tối thiểu cũng cung ứng một giải pháp hài hòa và hợp lý để nhóm cácđiểm trong khoảng trống thành các nhóm tự nhiên. Ví dụ, Ying Xu và tập sự [ 19 ] môtả một cấu trúc mới màn biểu diễn cho một tập hợp các tài liệu bộc lộ gene đa chiều nhưmột cây bao trùm tối thiểu. Một thuộc tính quan trọng của màn biểu diễn này là mỗi cụmdữ liệu biểu lộ gen tương ứng với một cây con của MST, trong đó một cách chuyểnđổi ngặt nghèo một bài toán phân nhóm đa chiều với một bài toán phân vùng cây. Họ đã11chứng minh rằng, mặc dầu mối quan hệ giữa các tài liệu là rất đơn thuần trong các biểudiễn MST, không có thông tin quan trọng bị mất cho các hiệu quả của phân nhóm. Họnhận thấy rằng có hai lợi thế quan trọng trong việc màn biểu diễn cho một tập hợp các dữliệu đa chiều như một MST. Một cấu trúc đơn thuần của một cây thuận tiện cho việcthực hiện hiệu suất cao đúng chuẩn của thuật toán phân cụm. Mặt khác là nó hoàn toàn có thể vượtqua nhiều bài toán phải đương đầu bởi các thuật toán phân nhóm cổ xưa từ một phânnhóm dựa trên MST không phụ thuộc vào vào hình dạng hình học cụ thể của một cụm. Một công cụ mới được gọi là ứng dụng EXCAVATOR, viết tắt của “ EXpressiondata Clustering Analysis and VisualizATiOn Resource, ” đã được tăng trưởng dựa trênnew framework. Các tác dụng phân nhóm trên các tài liệu biểu lộ gen ( 1 ) từ nấmmen Saccharomyces cerevisiae, ( 2 ) trong phản ứng nguyên bào sợi huyết thanh củaloài người, và ( 3 ) của Arabidopsis trong phản ứng để tìm ra chitin là rất hứa hẹn. 1.5.5 Xấp xỉ dựa trên MSTTrong các bài toán nhân viên cấp dưới bán hàng đi du lịch ( TSP ), tất cả chúng ta đưa ra mộtđồ thị vô hướng hoàn chỉnhcó hàm khối lượng w phối hợp với mỗi cạnh, vàchúng ta mong ước tìm được một tour củavới khối lượng tối thiểu. Bài toánnày đã được chứng tỏ là NP-khó ngay cả khi hàm khối lượng thõa mãn bất đẳngthức tam giác ,., cho tổng thể ba đỉnh 𝑥 𝑦 𝑧𝑤 𝑥 𝑧𝑤 𝑥 𝑦𝑤 𝑦𝑧. Các bất bình đẳng tam giác phát sinh trong nhiều trường hợp thực tế. Nó có thểđược hiển thị mà các kế hoạch tiếp theo cung ứng một thuật toán xê dịch với một tỷlệ của 2 ràng buộc cho các bài toán nhân viên cấp dưới bán hàng đi du lịch với bất đẳng thứctam giác. Đầu tiên, hãy tìm một cây khung tối thiểu T so với đồ thị cho trước. Sauđó tăng gấp đôi MST và kiến thiết xây dựng một tour. Cuối cùng, thêm các đường tắt đểkhông có đỉnh được truy vấn nhiều hơn một lần, mà được thực thi bởi một bộ câyđịnh trước. Kết quả là chiều dài các tour không quá hai lần là tối ưu. Nó cũng có thểchỉ ra được rằng một cách tiếp cận dựa trên MST cũng phân phối một giao động tốt chocác bài toán cây Steiner. 121.6. Kỹ nghệ thuật toán ( Algorithm Engineering ) 1.6.1 Giới thiệuTrong thời đại lúc bấy giờ, tất cả chúng ta hoàn toàn có thể thấy sự tác động ảnh hưởng của việc áp dụngthuật toán trong hàng loạt các ứng dụng đã và đang được sử dụng. Các thuật toánngày càng trở nên chiếm vai trò quan trọng trong mạng lưới hệ thống ngành kinh tế tài chính, công nghệ tiên tiến, khoa học, và trong đời sống hàng ngày. Chúng ta hoàn toàn có thể kể ra một số ít ngành nghề đặc biệt quan trọng tương quan ngặt nghèo đế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ôngtin liên lạc, mật mã, mạng lưới hệ thống thông tin địa lý, lấy thông tin từ hình ảnh ( chỉnh sửa, Phục hồi ), vận tải đường bộ đa phương tiện … Algorithmics – mạng lưới hệ thống tăng trưởng tính hiệu suất cao của thuật toán trở thành côngnghệ chủ chốt trong quy trình tăng trưởng các ứng dụng trên máy tính. Tuy nhiên, trongnhững năm qua Open khoảng cách ngày càng lớn giữa kim chỉ nan về thuật toánthuần túy và nhu yếu thực tế. Hệ quả của yếu tố này dẫn đến việc chỉ 1 số ít ít cácthuật toán là thực sự được vận dụng trong thực tế. Điều này thật sự rất đáng tiếc, đểhiểu được yếu tố này, tất cả chúng ta cần tìm hiểu và khám phá quy trình nghiên cứu và điều tra thuật toán đượcdiễn ra như thế nào theo cách thường thì. 1.6.1. 1. Thuật toán cổ điểnTrọng tâm của kim chỉ nan về thuật toán là các yếu tố đơn thuần và có tính trừutượng. Đối với một vài yếu tố thuật toán được phong cách thiết kế và nghiên cứu 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 hóa sử dụng theo lý thuyếtautomata ), từ đó đưa ra nhìn nhận thời hạn chạy của các thuật toán trong trường hợpxấu nhất và xác lập được chất lượng của thuật toán. Trong khoa học máy tính, thời hạn thực thi và chất lượng giải thuật là thướcđo cho tính hiệu suất cao của thuật toán. Giải quyết các các yếu tố trừu tượng và quy mô máy trừu tượng ( abstractmachine ) có những điểm đáng chú ý quan tâm trên triết lý : 13 – Các thuật toán được phong cách thiết kế với các yếu tố như vậy hoàn toàn có thể vận dụng trênnhiều ứng dụng cụ thể hóa trong các nghành nghề dịch vụ khác nhau. – Hầu hết các quy mô máy cổ xưa đều tương tự với thời hạn sai kháckhông quá đa thức, tác động ảnh hưởng của thuật toán không được đo lường và thống kê cụ thể. – Trường hợp xấu nhất của thuật toán xảy ra không giống như trong phong cách thiết kế. – Cho phép các máy tính độc lập triển khai thuật toán để hoàn toàn có thể so sánh vềtrường hợp xấu nhất mà không cần trang bị gì thêm. Từ quan điểm của kim chỉ nan thuật toán, việc vận dụng thuật toán là một phầncủa việc phong cách thiết kế và tăng trưởng ứng dụng. Hiệu quả của thuật toán được nhìn nhận quanhững người trình độ trong nghành của ứng dụng đó. Tuy nhiên, tất cả chúng ta nên chú ý quan tâm rằng so với nhiều người tiên phong trong thuậttoán những ngày đầu, như Knuth, Floyd và những người khác, tổng thể các thuật toánmà họ phong cách thiết kế được nhìn nhận dựa vào tiêu chuẩn thực hành thực tế. Điều này làm thay đổiquan điểm về phong cách thiết kế thuật toán, và dẫn đến nhu yếu phải tăng trưởng các cấu trúc dữliệu tiên tiến và phát triển để thiết lập các thuật toán. Qua việc tiến hành và thử nghiệm giữa kim chỉ nan và thực hành thực tế, nhiều nhà khoahọc đã nhận ra nhu yếu của việc phong cách thiết kế và nghiên cứu và phân tích từ thực tế ngày càng lớn. Mộtnhóm các nhà nghiên cứu thuật toán khởi đầu tìm cách để khắc phục yếu tố này cáchđây 15 năm. 1.6.1. 2. Nền tảng của Kỹ nghệ thuật toánQua cách tiếp cận thuật toán, tất cả chúng ta hoàn toàn có thể thấy việc thực thi và thí nghiệmcó tầm quan trọng như việc nghiên cứu và phân tích và phong cách thiết kế. Cách tiếp cận này đã cho chúng tamột khái niệm mới, đó là Kỹ nghệ thuật toán. Thomas Kuhn triển khai nghiên cứu và phân tích cấu trúc sự biến chuyển của khoa học và sửdụng các quy mô khái niệm để miêu tả lại “ sự phối hợp truyền thống cuội nguồn của nghiên cứukhoa học ”. Theo Kuhn sự biến chuyển quy mô chỉ xảy ra khi quy mô cũ đang khủng14hoảng và không hề xử lý được các yếu tố mới. Vậy sự kiện yên cầu mô hìnhmới ? Chúng ta sẽ liệt kê một vài ví dụ sau đây : – Các quy mô máy tính Von – Neumann đã dần không còn thích hợp trongthực tế với các việc như giải quyết và xử lý song song, giải quyết và xử lý pipelining, Dự kiến trước, phân cấpbộ nhớ và bộ nhớ đệm, giải quyết và xử lý đa luồng, và quy mô đo lường và thống kê phân tán và song song. – Trọng tâm của việc phong cách thiết kế thuật toán tập trung chuyên sâu vào việc cải tổ đánh giátiệm cận trong trường hợp xấu nhất và bảo vệ thuật toán đưa ra hiệu quả xê dịch nhưđã Dự kiến. Điều này dẫn đến việc có nhiều thuật toán và cấu trúc tài liệu được thiếtkế có nhiều ý tưởng sáng tạo mới nhưng không có tính thực tế. Đôi khi, điều đó không chắcchắn rằng các thuật toán sẽ không được vận dụng. Dù vậy, việc vận dụng vào thực tế sẽrất khó khăn vất vả đến mức không ai muốn thử thực thi việc này. Điểm bất lợi của việc nghiên cứu và điều tra thời hạn chạy tiệm cận là chúng hoàn toàn có thể ẩn đicác hằng số rất lớn. Tương tự, nhu yếu bộ nhớ hoàn toàn có thể là rất lớn mặc dầu là bị chặn bởiđa thức. – Như ví dụ đơn cử, chúng tôi hoàn toàn có thể trích dẫn một số ít yếu tố trong thuật toán : 1. Rất nhiều ( không phải tổng thể ) sơ đồ giao động thời hạn đa thức ( PTAS ), ví dụ điển hình các sơ đồ của Aurora hoặc Mitchell cho bài toán người du lịch ( TSP ), có thông số rất lớn. 2. Robins và Zelikovsky trình diễn một mạng lưới hệ thống thuật toán giải bài toáncây Steiner trong đồ thị với thời hạn chạy là, trong đólà mộttham số ảnh hưởng tác động đến hiệu suất. Đối với trường hợp lớn, thuật toán của họđạt cận tỷ suất tốt nhất lúc bấy giờ là 1.55. Để nâng cấp cải tiến tốt nhất mức giao động bảo đảmở 1.598 bởi Hougardy và Prömel, thiết yếu phải chọn. Ngoài ra, còncần hơn 217 thiết bị đầu cuối. 3. Câu hỏi liệu một đa giác đơn hoàn toàn có thể được tam giác hóa trong thời giantuyến tính hay không là một trong những yếu tố chính trong hình học tính toánnhiều năm qua. Năm 1990, yếu tố này ở đầu cuối đã được Chazelle xử lý, 15 ông đã đưa ra một thuật toán với thời hạn tuyến tính khá phức tạp. Theonhững kiến thức và kỹ năng chúng tôi biết thì thuật toán này chưa khi nào được vận dụng. 4. Việc thiết kế xây dựng hình học, được biết đến như một kỹ thuật cắt, cung cấpmột kỹ thuật phân vùng khoảng trống cho bất kể size hữu hạn nào màtrong đó có vô số ứng dụng trong hình học đo lường và thống kê. Tuy nhiên, thuật toán dựatrên cuttings có vẻ như cho thấy một thử thách so với việc triển khai. Trong thực tế, yếu tố hằng số đóng vai trò khá lớn : trong các ứng dụng nhưphẫu thuật có sự trợ giúp của máy tính, phục sinh thông tin bằng công cụ tìm kiếm, hướng dẫn xe cộ, và nhiều ứng dụng khác, giải pháp này phải được tính trong thờigian gần như tức thời. Trong các ứng dụng khác, hiệu suất của người sử dụng mộtcông cụ ứng dụng có tương quan ngặt nghèo với hiệu suất của công cụ. Ở đây bất kể sựcải thiện nào so với yếu tố hằng số đều xứng danh được góp vốn đầu tư. Vì vậy, việc cải tiếnyếu tố hằng số thường tạo ra độc lạ mặc dầu công cụ có được vận dụng hay không. – Khái niệm về hiệu suất cao như năng lực xử lý thời hạn đa thức thườngkhông tương thích. Thậm chí thời hạn chạy nhỏ, nhưng siêu tuyến tính, mức độ đa thứccó thể quá chậm. Các ứng dụng thực tế, ví dụ điển hình trong phong cách thiết kế VLSI, tin sinh học, hoặc giải quyết và xử lý tài liệu khoảng trống, nhu yếu phải giải quyết và xử lý các tập dữ liệu cực lớn. Trongnhững trường hợp như vậy, tất cả chúng ta thường chỉ hoàn toàn có thể vận dụng các thuật toán đòi hỏithời gian và khoảng trống chạy tuyến tính, thậm chí còn cần các thuật toán thời hạn dướituyến tính. Trong thực tế, nghiên cứu và điều tra về các thuật toán dưới tuyến tính gần đây đãxuất hiện như thể một nghành nghề dịch vụ nghiên cứu và điều tra mới. Thuật toán dưới tuyến tính hoặc chỉxem xét một mẫu nhỏ ngẫu nhiên của các tài liệu nguồn vào hoặc quy trình khi nó đến, và sau đó trích một bản tóm tắt nhỏ. – Như đã nêu ở trên, tiêu chuẩn chính khi phong cách thiết kế thuật toán kim chỉ nan là tính hiệuquả. Điều này đã kích thích sự tăng trưởng của các cấu trúc tài liệu rất phức tạp – cho dùđối với nhiều cấu trúc, liệu chúng có được thực thi một cách hài hòa và hợp lý hay không vẫnlà một câu hỏi. Tuy nhiên, trong thực tế, ngoài tính hiệu suất cao, những tiềm năng thiết kếkhác đều có vai trò quan trọng như nhau, nhiều lúc tầm quan trọng của một tiêu chuẩn nào16đó thậm chí còn còn được đặt cao hơn, ví dụ điển hình tính linh động, dễ sử dụng, bảo dưỡng, … Trong thực tế, cấu trúc tài liệu và các thuật toán đơn thuần được ưa thích hơn nhữngcái phức tạp. – Các góc nhìn triết lý về các thuật toán thường đưa ra một bài thuyết trìnhcấp cao, còn các cụ thể thiết yếu để khởi đầu thực thi thì để lại cho người đọc. – Sự khởi đầu thuận tiện nhất để điều tra và nghiên cứu và tăng trưởng sáng tạo độc đáo thuật toán mớilà từ yếu tố đơn thuần. Tuy nhiên, cùng với quy trình tiến độ chung trong khoa học máy tính vàsự sẵn có của sức mạnh thống kê giám sát, các ứng dụng tự trở nên phức tạp hơn. Các ứngdụng như vậy yên cầu một quy mô cẩn trọng. Câu hỏi đặt ra là liệu kỹ năng và kiến thức học đượccho các quy mô đơn thuần hoàn toàn có thể sửa chữa thay thế những quy mô phức tạp hơn. – Dữ liệu nguồn vào thực thường không phải là cấu trúc của các trường hợp khónhất được sử dụng trong nghiên cứu và phân tích triết lý. Do đó rất hoàn toàn có thể là hiệu suất Dự kiến làkhông khả dụng. – Công việc thử nghiệm tốt yên cầu sự nỗ lực đáng kể ( thời hạn, nhân lực, kỹnăng lập trình, kinh nghiệm tay nghề, … ). Trong nhiều thiết lập thử nghiệm, người ta thực thi các thí nghiệm với cáctrường hợp ngẫu nhiên. Điều này hoàn toàn có thể gây hiểu nhầm lớn. Ví dụ, một vài đồ thịngẫu nhiên có 1 số ít thuộc tính cấu trúc làm cho chúng độc lạ với đồ thị trong thếgiới thực. Một ví dụ khác phát sinh trong đo lường và thống kê hình học : một bộ mẫu thống nhấtcủa các điểm bảo vệ chắc như đinh các điểm sẽ ở vị trí tùy ý. Tuy nhiên trong thực tế, rất có năng lực không triển khai giả thiết này. Thật không may, thao tác với các tài liệu nguồn vào thực tế cũng có yếu tố củanó : Những tài liệu này hoàn toàn có thể không có sẵn cho các nhà nghiên cứu hoặc hoàn toàn có thể là độcquyền. Để thu hẹp khoảng cách giữa thực tế và kim chỉ nan, Kỹ nghệ thuật toán ( Algorithm Engineering ) yên cầu một chiêu thức lan rộng ra hơn. Tuy nhiên, Algorithm Engineering sẽ phải giữ được những lợi thế của triết lý : – Tính tổng quát, 17 – Độ an toàn và đáng tin cậy, và – Khả năng Dự kiến. Hy vọng là Algorithm Engineering sẽ làm tăng tác động ảnh hưởng của nó trên các lĩnhvực khác một cách đáng kể. Kỹ nghệ thuật toán sẽ làm cho việc chuyển giao các ứngdụng được tăng cường. 1.6.1. 3. Định nghĩa Kỹ nghệ thuật toán ( Algorithm Engineering ) Một số chi tiết cụ thể của Algorithm Engineering đã được trình diễn tại các hội thảocủa DIMACS Implementation Challenges ( http://dimacs.rutgers.edu/Challenges/ ) : ” Những yếu tố được thực thi bởi DIMACS xử lý câu hỏi về việc xácđịnh hiệu suất thuật toán thực tế nơi mà những nghiên cứu và phân tích trường hợp xấu nhất là quábi quan và quy mô Xác Suất là quá phi thực tế : việc thử nghiệm hoàn toàn có thể phân phối cáchướng dẫn để thực thi thuật toán thực tế khi mà nghiên cứu và phân tích không thành công xuất sắc. Thí nghiệm cũng mang thuật toán thân mật hơn với các yếu tố khởi đầu, tạo nênđộng lực cho các khu công trình kim chỉ nan. Nó cũng góp thêm phần kiểm tra rất nhiều giả địnhvề chiêu thức thực thi và cấu trúc tài liệu. Nó tạo ra một thời cơ để tăng trưởng vàkiểm tra yếu tố, máy phát ví dụ, và các giải pháp khác để kiểm tra và so sánhhiệu suất của thuật toán. Đó là một bước tiến trong việc chuyển giao công nghệ tiên tiến bằngcách cung ứng các mạng lưới hệ thống giải quyết và xử lý của các thuật toán cho những người khác để sửa đổithích hợp. Kể từ năm 1990, khi First Challenge khởi đầu với dòng chảy mạng, tổng cộngchín thử thách triển khai đã được triển khai. Thuật ngữ Algorithm Engineering lầnđầu tiên được sử dụng với độ đặc hiệu và ảnh hưởng tác động đáng kể trong năm 1997, với việctổ chức Hội thảo tiên phong về Algorithm Engineering ( WAE 1997 ). Một vài năm trướcđây, David Bader, Bernard Moret, và Peter Sanders định nghĩa như sau : ” Algorithm Engineering đề cập đến quy trình thiết yếu để đổi khác một thuậttoán từ bút chì trên giấy thành hiện thực, hiệu suất cao, kiểm nghiệm tốt, và thuận tiện sửdụng. Vì vậy, nó gồm có 1 số ít chủ đề, từ hành vi mẫu bộ nhớ cache đến các18nguyên tắc của công nghệ phần mềm ; tuy nhiên trọng tâm chính của nó là thửnghiệm. ” Chúng ta chấp thuận đồng ý rằng tổng thể các chủ đề được đề cập đều là những phần quantrọng của Algorithm Engineering, nhưng vẫn muốn có một cái nhìn rộng hơn về vấnđề này. Một định nghĩa tổng quát hơn đã Open trong thông tin của ALCOM-FTSummer School về Algorithm Engineering năm 2001 : ” Algorithm Engineering tương quan với việc phong cách thiết kế, nghiên cứu và phân tích triết lý và thựcnghiệm, kỹ thuật và kiểm soát và điều chỉnh các thuật toán, và đang lôi cuốn được sự quan tâmngày càng tăng trong hội đồng những người nghiên cứu và điều tra thuật toán. Quy tắc mới nổinày xử lý các yếu tố về hiệu suất thuật toán thực tế bằng cách kết hợp cẩn thậncác phương pháp lý thuyết truyền thống lịch sử cùng với các khảo sát thực nghiệm kỹ lưỡng. ” ( Đăng trong DMANET vào ngày 17 tháng năm 2001 bởi Guiseppe Italiano ). 1.6.1. 4. Phương pháp luậnPhương pháp khoa học có nguồn gốc từ các ngành khoa học tự nhiên. Nó xemkhoa học như thể một chu kỳ luân hồi giữa triết lý và thực nghiệm. Lý thuyết hoàn toàn có thể quy nạpvà diễn dịch một phần – theo triết lý dựa trên giả định đơn cử – kiến thiết xây dựng giả thuyếtthực nghiệm đã được thử nghiệm. Các hiệu quả của các thí nghiệm lần lượt hoàn toàn có thể dẫn đến giả thuyết hay lý thuyếtmới, v.v … Cũng giống như công nghệ phần mềm, Algorithm Engineering không phảilà một quy trình đơn thuần. Lý tưởng nhất, người ta sẽ phong cách thiết kế một thuật toán, thựchiện nó, và sử dụng nó. Tuy nhiên, các thuật toán tối ưu, tức là thuật toán tốt nhất đểgiải quyết yếu tố trong một ứng dụng, và bước thực thi sau cuối không được biếttrước. Trong Algorithm Engineering, một dẫn chứng triết lý cho sự tương thích đốivới một mục tiêu đơn cử được sửa chữa thay thế bởi một nhìn nhận thực nghiệm. Ví dụ, thửnghiệm đó giúp kiểm tra liệu code được thiết lập có hiệu suất cao hoặc trong trường hợpthuật toán gần đúng, thì mới có hiệu suất cao. 19T hông thường, để đưa ra các hiệu quả nhìn nhận thực nghiệm yên cầu một phiên bảnthiết kế và thực thi nữa. Vì vậy, như đã nêu trong DFG Priority Program 1307 [ 556 ] : ” Cốt lõi của Algorithm Engineering là một chu kỳ luân hồi điều khiển và tinh chỉnh bởi các giảthuyết giả định. ” [ Www. algorithm-engineering.de ] Thông thường, nghiên cứu và phân tích được coi là một phần của chu kỳ luân hồi này, dẫn đến mộtchu kỳ mà trong đó gồm có phong cách thiết kế, nghiên cứu và phân tích, triển khai và nhìn nhận thử nghiệm cácthuật toán thực tế. Tuy nhiên, vì tác dụng nghiên cứu và phân tích của phong cách thiết kế sẽ ngay lập tức đưa raphản hồi cho các nhà phong cách thiết kế và không đi qua thực thi và thử nghiệm tiên phong, nócó vẻ thích hợp hơn khi để cho các tiến trình nghiên cứu và phân tích là một phần của chu kỳ luân hồi riêngcùng với các phong cách thiết kế thuật toán. Như vậy, trong Hình 1.3, quy trình cốt lõi ở trungtâm chỉ gồm có phong cách thiết kế, triển khai và thử nghiệm. Algorithm Engineering luôn luôn được thôi thúc bởi các ứng dụng thực tế. Kịch bản ứng dụng xác lập các phần cứng mà phải được làm giống thực nhất. Tronggiai đoạn tiên phong của Algorithm Engineering, không riêng gì là một quy mô máy tính tốtđã được chọn, mà còn là yếu tố tự nó đã được quy mô hóa một cách thích hợp, màthường là bị loại trừ từ phong cách thiết kế thuật toán. Kết quả của một quy trình tiến độ thử nghiệm cóthể sau đó nhu yếu một phiên bản của quá trình quy mô, vì các quy mô được lựachọn là không thích hợp. Đôi khi việc nghiên cứu và phân tích các quy mô được lựa chọn đã có thểtiết lộ chưa ổn của nó. Điều này tạo ra một chu kỳ luân hồi khác gồm có các ứng dụng, môhình hóa và nghiên cứu và phân tích. Các ứng dụng cũng phân phối tài liệu thực tế để nhìn nhận thửnghiệm và nhìn nhận thực nghiệm hoàn toàn có thể bật mý nhu yếu xem xét thêm một số ít khíacạnh khác cho loại tài liệu đơn cử. Các thành phần đáng an toàn và đáng tin cậy từ các thư viện phầnmềm hoàn toàn có thể thuận tiện hóa các trách nhiệm. Người ta cho rằng một chương trình thiết kếtốt nên được phân phối trong một thư viện ứng dụng để hoàn toàn có thể tái sử dụng. Rõ ràng, đây là một sự nhờ vào tuần hoàn trong Algorithm Engineering. Chúng ta dừng tranh luận với một trích dẫn từ DFG Priority Program 1307 : 20 ” Mô hình thực tế cho cả máy tính và các ứng dụng, cũng như các thư việnthuật toán và các bộ sưu tập tài liệu nguồn vào thực tế được cho phép tạo ra cầu nối chặt chẽvới các ứng dụng. ” [ Www. algorithm-engineering.de ] 1.6.1. 5. Tình trạng của Kỹ nghệ thuật toánCó rất nhiều hội nghị nói về kỹ nghệ thuật toán nhưng phần lớn đều chỉ là mộtphần nội dung của hội nghị chứ không phải tổng thể. Hội nghị tiên phong dành riêng chokỹ nghệ thuật toán là Workshop on Algorithm Engineering ( WAE ) được tổ chức triển khai tạiVenice ( Italy ) vào ngày 11 – 13, tháng 9 năm 1997. Đó là điểm khởi đầu của một loạtcác hội nghị hàng năm. Tại hội nghị WAE 5 ở Aarhus, Đan Mạch, 2001, WAE đã trởthành một trong những hội nghị số 1 Châu Âu về các thuật toán ESA. Kể từ đóhội nghị WAE trở thành hội nghị kiểu mẫu được công nhận. Sau WAE, một loạt hộinghị ALENEX ( Algorithm Engineering and Experiments ) được tổ chức triển khai và xây dựng. ALENEX diễn ra hàng năm và san sẻ với SODA, ACM-SIAM Symposium onDiscrete Algorithms về các thuật toán Discrete. Một trong những hội nghị mới về kỹnghệ thuật toán là SEA, hội nghị quốc tế về thực nghiệm thuật toán cho đến năm2009 vẫn được biết đến là hội nghị WEA ( Workshop on Experimental Algorithms ). Hình 1.3. Kỹ nghệ thuật toánTạp chí chính thức cho nghành nghề dịch vụ này là tạp chí ACM Journal of ExperimentalAlgorithmics được xuất bản năm 1996. Tạp chí trở thành một liên kết cho các hoạt21

Source: https://evbn.org
Category: Góc Nhìn