Tiểu cấu trúc tối ưu của bài toán chuỗi con
chung dài nhất
ủ Thí dụ: X = và Y =
là LCS c a X and Y.
ị ti n t ề ố ứ
th i
ỗ
1, x2, …, xm>, ta đ nh nghĩa
Cho chu i X = .
ủ
c a X, v i
ị
ủ
m1 và
Z = là LCS c a X và Y.
m = yn thì zk = xm = yn và Zk1 là LCS c a Xủ
m1 và Y.
n1.
21
ủ Đ nh lý 4.1
Cho X = và Y = là nh ng ữ
ỗ
chu i, và
1. N u xế
Yn1.
2. N u xế m (cid:0)
3. N u xế m (cid:0) xm hàm ý Z là LCS c a Xủ
yn hàm ý Z là LCS c a X và Y yn, thì zk (cid:0)
yn, thì zk (cid:0)
Lời giải đệ quy
ể
ư
m1 và Yn1.
ủ
ể ầ
ỗ
m1 và Y. Nh ng m i trong hai bài
ể ữ ộ
ủ
Đ tìm m t LCS c a X và Y, ta có th c n tìm LCS c a X
và Yn1 và LCS c a Xủ
toán con này có nh ng bài toán “cháu” đ tìm X
ề ọ ỗ i và Yj.
ấ ể
ố ư ủ ứ ệ
ủ
ủ
G i c[i, j] là chi u dài c a LCS c a hai chu i X
ề
N u ế i = 0 hay j = 0, thì LCS có chi u dài 0. Tính ch t ti u
ấ
c u trúc t
i u c a bài toán LCS cho ra công th c đ quy
sau:
ế 0 n u i =0 hay j = 0
ế c[i, j] = c[i1, j1]+1 n u i, j > 0 và x
i = yj
i (cid:0)
ế yj
22
max(c[i, j1],c[i1,j]) n u i,j >0 và x
(5.3)
Tính chiều dài của một LCS
ự
ươ
t m t gi
ộ ả
ủ
ủ
ề
ộ
ạ
i lên
ể ế
i
ng trình (5.3), ta có th vi
D a vào ph
ậ ệ
ộ
ể
thu t đ quy đ tìm chi u dài c a m t LCS c a hai
ể
ỗ
chu i. Tuy nhiên, chúng ta dùng qui ho ch đ ng đ
ừ ướ
t
d
tính l
i theo cách
ờ ả
i gi
.
ủ ụ
ỗ
1,x2, …, xm>
ầ
Th t c LCSLENGTH có hai chu i X = là đ u vào.
ủ ụ ư
ị
ả
ể ơ
ệ
ả
Th t c l u các tr c[i, j] trong b ng c[0..m, 0..n]. Nó
ả
cũng duy trì b ng b[1..m, 1..n] đ đ n gi n hóa vi c
ạ ờ ả ố ư
t o l
i u.
i gi
i t
23
procedure LCSLENGTH(X, Y)
begin
m: = length[X]; n: = length[Y];
for i: = 1 to m do c[i, 0]: = 0; for j: = 1 to n do c[0, j]: = 0;
for i: = 1 to m do
for j: = 1 to n do
if xi = yj then
begin c[i, j]: = c[i1, j1] + 1; b[i, j]: = “” end
else if c[i – 1, j] > = c[i, j1] then
begin c[i, j]: = c[i – 1, j]; b[i, j]: = “(cid:0) ” end
else
begin c[i, j]: = c[i, j1]; b[i, j]: = “(cid:0) ” end
end;
24
ủ ụ
Hình 4.2 sau đây trình bày ma tr n ậ c c a thí d .
yj B D C A B A
0
0
0
0
0
0
0
xi
0
0 (cid:0)
0 (cid:0)
0 (cid:0)
1
1 (cid:0)
1
A
0
1
1 (cid:0)
1 (cid:0)
1 (cid:0)
2 (cid:0)
2
B
Hình 5.2
0
1 (cid:0)
1 (cid:0)
2
2 (cid:0)
2 (cid:0)
2 (cid:0)
C
0
1
1 (cid:0)
2 (cid:0)
2 (cid:0)
3 (cid:0)
3
B
0
1 (cid:0)
2
2 (cid:0)
2 (cid:0)
3 (cid:0)
3 (cid:0)
D
0
1 (cid:0)
2 (cid:0)
2 (cid:0)
3 (cid:0)
3
4
A
0
1
2 (cid:0)
2 (cid:0)
3 (cid:0)
4
B
4 (cid:0)
25
Tạo chuỗi con chung dài nhất
ể ượ
ể ạ
ủ
ộ
B ng ả b có th đ
c dùng đ t o m t LCS c a
X = and Y =
ủ
ọ ầ
ủ
ộ
ệ
ệ
Th tuc đ quy sau đây in ra m t LCS c a X và Y. L nh g i đ u tiên
là PRINTLCS(b, X, n, m).
ờ
ủ ụ
'' then
procedure PRINTLCS(b, X, i, j)
begin
if i <> 0 and j <> 0 then
if b[i, j] = '' '' then
begin PRINTLCS(b, X, i 1 , j l ) ;
print xi
end
else if b[i,j] = ''(cid:0)
PRINTLCS (b, X, i1, j)
else PRINTLCS(b, X, i, j1)
end;
26
Th i gian tính toán
ủ
c a th t c PRINT
LCS là O(m+n), vì ít
nh t ấ i hay j gi m ả
ộ ơ ị
m t đ n v trong
ủ ệ
ặ
ỗ
m i ch ng c a đ
quy.
Thí dụ 3. Bài toán cái túi (Knapsack)
ệ ộ ộ ẻ ộ n
ọ
ặ
ỉ ứ i
ấ
ư
ượ
ặ
ị ộ ổ ợ
ể ạ ẻ ộ
ấ ớ ữ ộ ử
ậ
'‘M t k tr m đ t nh p vào m t c a hi u tìm th y có
ị
ượ
ng và giá tr khác nhau, nh ng y
m t hàng có tr ng l
ố
ứ ề ọ
ộ
ng t
ch mang theo m t cái túi có s c ch a v tr ng l
đa là M. Bài toán cái túi là tìm m t t
h p các m t hàng
ộ
ỏ
mà k tr m nên b vào cái túi đ đ t m t giá tr cao
nh t v i nh ng món hàng mà y mang đi.”
ạ ể ả ằ qui ho ch đ ng i b ng ằ
ộ b ng cách
Bài toán này có th gi
dùng hai b ng ả cost và best sau đây:
ể ự ị ố ệ ượ ớ c v i
ứ ộ ứ
cost[i] ch a giá tr t
i đa mà có th th c hi n đ
ứ i
m t cái túi có s c ch a
cost[i] = cost[i – size[j]] + val[j]
ỏ ố ằ ạ
27
ị ố ượ best[i] ch a m t hàng cu i cùng b vào túi nh m đ t
đ ứ
c giá tr t ặ
i đa.
Một thí dụ của bài toán cái túi
value 4 5 10
11 13
name A B C D E
M = 17
28
ụ ủ ộ Hình 5.3 M t thí d c a bài toán cái túi
Giải thuật quy hoạch động cho bài toán cái túi
M: sức chứa tối đa của cái túi
29
for i: = 0 to M do cost[i]: = 0;
for j: = 1 to N do /* each of item type */
begin
for i:= 1 to M do /* i means capacity */
if i – size[j] > = 0 then
if cost[i] < (cost[i – size[j]] + val[j]) then
begin
cost[i]: = cost[i – size[j]] + val[j]; best[i]: = j
end;
end;
Một thể hiện của cái túi
K 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
j=1
cost[k] 0 0 4 4 4 8 8 8 12 12 12 16 16 16 20 20 20
best[k] A A A A A A A A A A A A A A A
j=2
cost[k] 0 0 4 5 5 8 9 10 12 13 14 16 17 18 20 21 22
best[k] A B B A B B A B B A B B A B B
j=3
cost[k] 0 0 4 5 5 8 10 10 12 14 15 16 18 18 20 22 24
best[k] A B B A C B A C C A C C A C C
j=4
cost[k] 0 0 4 5 5 8 10 11 12 14 15 16 18 20 21 22 24
best[k] A B B A C D A C C A C C D C C
j=5
cost[k] 0 0 4 5 5 8 10 11 13 14 15 17 18 20 21 23 24
best[k] A B B A C D E C C E C C D E C
ụ
ủ
ộ
Hình 5.4 Các m ng ả cost và best c a m t thí d bài toán cái túi
30
Ghi Chú:
i đ
ả ưọ ế
ở
ạ ớ
ể ấ ể ễ
ờ ớ
Bài toán cái túi có th d dàng gi
c n u M không l n,
ư
nh ng khi M l n thì th i gian ch y tr nên không th ch p
ậ ượ
nh n đ c.
ươ ệ ượ ể ọ ng pháp này không th làm vi c đ c khi M và tr ng
ướ ố ự ữ ố Ph
ượ
l ng/kích th c là nh ng s th c thay vì s nguyên.
ả ể ả ộ ậ ạ
i thu t qui ho ch đ ng đ gi i bài toán Gi
31
ờ ấ
Tính ch t 4.1.1
cái túi có th i gian ch y t l ạ ỉ ệ ớ NM.
v i
Thí dụ 4: Giải thuật Warshall và giải thuật Floyd
Tính bao đóng truyền
ỉ ng, chúng ta quan tâm đ n t p đ nh
ế ậ
ệ
ị ộ ướ ượ ấ ồ ị
Trong đ th có h
ế ượ t
c
mà đ n đ
ồ ị
ạ
c nh trong đ th theo m t h ướ
ằ
ừ ộ ỉ
m t đ nh nào đó b ng cách duy t các
ng đã đ c n đ nh.
ệ ộ
ế ồ ạ ộ ể ố
i m t cách nào đó đ đi t
ộ ạ
ự
ụ
M t tác v mà ta mu n th c hi n là “thêm m t c nh
ừ x đ n ế
ừ x đ n ế y n u t n t
t
y”
ồ ị ạ
ằ
Đ th t o ra b ng cách thêm t
ượ ọ
ấ
c g i là
tính ch t trên đ ạ
ấ ả
t c các c nh có
ủ ồ ị
bao đóng truy nề c a đ th .
ồ ị ườ , do
ng là
ậ ễ ề
Vì đ th bao đóng truy n thì th
ể
đó ta nên dùng cách bi u di n ma tr n k c n.
ồ ị
đ th dày
ế ậ
32
Giải thuật Warshall
ề ủ i thu t đ n gi n đ tính bao đóng truy n c a
ộ ả
ộ ồ ị ượ ế ậ ả
ễ ể
ằ ậ Có m t gi
m t đ th đ ậ ơ
ể
c bi u di n b ng ma tr n k c n.
for y : = 1 to V do
for x : = 1 to V do
if a[x, y] then
for j: = 1 to V do
if a[y, j] then a[x, j]: = true;
ề ậ
ự
ể ừ ả
ẽ ể
nút y đ n nút j, thì s có cách đ
33
ừ ộ
ả
i thu t này năm 1962, d a trên m t
S. Warshall đ ra gi
ế ồ ạ ộ
ơ
nút x
i m t cách đ đi t
N u t n t
quan sát đ n gi n: “
ế
ừ
ể
ế
đ n nút y và cách đ đi t
ế
.”
nút x đ n nút j
đi t
ụ
ộ
ề
M t thí d tính bao đóng truy n
A
H
I
B
C
G
D
E
J
K
F
L
M
ậ
ế ậ ứ
ở ầ
c kh i đ u
ậ
i thu t A B C D E F G H I J K L M
A 1 1 0 0 0 1 1 0 0 0 0 0 0
B 0 1 0 0 0 0 0 0 0 0 0 0 0
C 1 0 1 0 0 0 0 0 0 0 0 0 0
D 0 0 0 1 0 1 0 0 0 0 0 0 0
E 0 0 0 1 1 0 0 0 0 0 0 0 0
F 0 0 0 0 1 1 0 0 0 0 0 0 0
G 0 0 1 0 1 0 1 0 0 1 0 0 0
H 0 0 0 0 0 0 1 1 1 0 0 0 0
I 0 0 0 0 0 0 0 1 1 0 0 0 0
J 0 0 0 0 0 0 0 0 0 1 1 1 1
K 0 0 0 0 0 0 0 0 0 0 1 0 0
L 0 0 0 0 0 0 0 0 0 0 0 1 1
M 0 0 0 0 0 0 0 0 0 0 0 1 1
34
Ma tr n k c n ng
ớ ướ
v i b
ả
ủ
c a gi
Warshall
ậ
ố
ớ
ế ậ ứ
Ma tr n k c n ng v i
ả
ủ
ướ
c cu i cùng c a gi
b
i
ậ
thu t Warshall
i ả
Tính ch t 5ấ .3.1 Gi
thu tậ Warshall tính bao
ề ớ
đóng truy n v i chi phí
O(V3).
A B C D E F G H I J K L M
A 1 1 1 1 1 1 1 0 0 1 1 1 1
B 0 1 0 0 0 0 0 0 0 0 0 0 0
C 1 1 1 1 1 1 1 0 0 1 1 1 1
D 0 0 0 1 1 1 0 0 0 0 0 0 0
E 0 0 0 1 1 1 0 0 0 0 0 0 0
F 0 0 0 1 1 1 0 0 0 0 0 0 0
G 1 1 1 1 1 1 1 0 0 1 1 1 1
H 1 1 1 1 1 1 1 1 1 1 1 1 1
I 1 1 1 1 1 1 1 1 1 1 1 1 1
J 1 1 1 1 1 1 1 0 0 1 1 1 1
K 0 0 0 0 0 0 0 0 0 0 1 0 0
L 1 1 1 1 1 1 1 0 0 1 1 1 1
M 1 1 1 1 1 1 1 0 0 1 1 1 1
Giải thuật Warshall thể hiện sự áp dụng chiến lược quy hoạch động
vì sự tính toán căn cứ vào một hệ thức truy hồi (5.4) nhưng lại
không xây dựng thành giải thuật đệ quy. Thay vào đó là một giải
thuật lặp với sự hỗ trợ của một ma trận để lưu trữ các kết quả trung
gian.
35
Giải thích giải thuật Warshall
Giải thuật Warshall lặp V bước trên ma trận kế cận a, tạo ra
một loại những ma trận:
a(0), a(y-1),a(y),…,a(V) (5.4)
Ý tưởng chính của giải thuật là ta có thể tính tất cả các phần tử
trong mỗi ma trận a(y) từ ma trận đi trước nó a(y-1) trong loạt ma
trận (4.1)
Sau bước lặp thứ y, a[x, j] sẽ bằng 1 nếu và chỉ nếu có bất kỳ
lối đi nào từ đỉnh x đến đỉnh j với những đỉnh trung gian mang
chỉ số không lớn hơn y. Nghĩa là, x và j có thể là bất kỳ đỉnh
nào nhưng những đỉnh trung gian trên lối đi phải nhỏ hơn hay
bằng y.
Tại bước lặp thứ y, ta tính các phần tử của ma trận a bằng
công thức sau:
ay[x,j] = ay-1[x,j] or (ay-1[x, y] and ay-1[y, j]) (5.5)
Chỉ số y chỉ trị của một phần tử trong ma trận a sau bước lặp
thứ y.
36
Giải thuật Floyd cho bài toán các lối đi ngắn nhất
ướ ố ớ ồ ị
ự ố
ậ ộ
ể
ng ho c không) ta có th
ượ
i ta tìm đ
ấ
c
ố ớ ọ ặ
ấ ừ x đ n ế y đ i v i m i c p đ nh. Đ y là
ấ ỉ
ọ ặ ỉ ắ i đi ng n nh t cho m i c p đ nh (allpairs
ặ
ọ
Đ i v i đ th có tr ng s (có h
ườ
ố
mu i xây d ng m t ma tr n cho phép ng
ắ
ố
l
i đi ng n nh t t
ố
ữ
bài toán nh ng l
shortest path problem).
A
4
2
3
I
H
1
1
B
C
G
1
1
2
Hình 5.7
2
1
1
D
E
K
J
1
5
2
3
F
2
M
L
1
37
Giải thuật Floyd
ể ộ ng
for y : = 1 to V do
for x : = 1 to V do
if a [x, y] > 0 then
for j: = 1 to V do
if a [y, j] > 0 then
if (a[x, j] = 0) or (a[x, y] + a[y, j] < a [x, j])
then
a[x, j] = a[x, y] + a[y, j];
38
ươ
ượ ư ươ
ở Có th dùng m t ph
pháp Warshall, mà đ ự ư ươ
nh ph
ng t
ng pháp t
c đ a ra b i R. W. Floyd:
ộ
ả
ồ
ậ
ụ
M t thí d dùng gi
i thu t Floyd (cho đ thi hình 5.7)
ế ậ
ậ
Ma tr n k c n
c ướ
ớ b
ứ
ng v i
ở ầ ủ
kh i đ u c a
ậ
ả
i thu t Floyd
gi
Chú ý: Các phần tử trên
đường chéo đều bằng 0.
A B C D E F G H I J K L M
A 0 1 0 0 0 2 4 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 0 0 0 0 0 1 0 0 0 0 0 0 0
E 0 0 0 2 0 0 0 0 0 0 0 0 0
F 0 0 0 0 2 0 0 0 0 0 0 0 0
G 0 0 1 0 1 0 0 0 0 1 0 0 0
H 0 0 0 0 0 0 3 0 1 0 0 0 0
I 0 0 0 0 0 0 0 1 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0 1 3 2
K 0 0 0 0 0 0 0 0 0 0 0 0 0
L 0 0 0 0 0 5 5 0 0 0 0 0 1
M 0 0 0 0 0 0 0 0 0 0 0 1 0
39
ế ậ
ố
i thu t
ậ
Ma tr n k c n
ớ ướ
ứ
ng v i b
c cu i
ậ
ả
ủ
c a gi
Floyd
i ả
i
i đi
ắ
ữ
ứ ạ
A B C D E F G H I J K L M
A 6 1 5 6 4 2 4 0 0 5 6 8 7
B 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 2 6 7 5 3 5 0 0 6 7 9 8
D 0 0 0 5 3 1 0 0 0 0 0 0 0
E 0 0 0 2 5 3 0 0 0 0 0 0 0
F 0 0 0 4 2 5 0 0 0 0 0 0 0
G 2 3 1 3 1 4 6 0 0 1 2 4 3
H 5 6 4 6 4 7 3 2 1 4 5 7 6
I 6 7 5 7 5 8 4 1 2 5 6 8 7
J 10 11 9 11 9 12 8 0 0 9 1 3 2
K 0 0 0 0 0 0 0 0 0 0 0 0 0
L 7 8 6 8 6 9 5 0 0 6 7 2 1
M 8 9 7 9 7 10 6 0 0 7 8 1 2
40
ấ
Gi
Tính ch t 5.3.2
ể ả
thu tậ Floyd đ gi
ố
ữ
bài toán nh ng l
ấ ữ
ng n nh t gi a
ộ
ặ
nh ng c p có đ
ph c t p tính toán
O(V3).
Giải thích giải thuật Floyd
ậ
ướ
ạ
ặ V b
ậ
c trên ma tr n k c n
ộ ạ
ế ậ a, t o ra m t lo i
ả
ữ
i thu t Floyd l p
ậ
ưở
ậ
ể
ướ
ỗ
i thu t là ta có th tính t
ừ
c nó, a
ả
ủ
ậ (y) t
ậ
ma tr n đi tr
Gi
nh ng ma tr n:
a(0), a(y1),a(y),…,a(V) (5.6)
ầ ử
ấ ả
ng chính c a gi
Ý t
t c các ph n t
ạ
(y1) trong lo t ma
trong m i ma tr n a
tr n.ậ
ướ ặ
ỏ ấ ủ
ứ
ề
ấ ỳ
ứ y, a[x, j] sẽ ch a chi u dài nh nh t c a b t k
ữ
ế
ỉ
i đi nào t
x đ n đ nh
ư
ữ
ố
ỉ
ỉ
j mà đi qua nh ng đ nh trung gian
ấ ỳ
ỉ ố ớ ơ y. Nghĩa là, x và j có th có là b t k
ỏ ơ
ả nh h n hay
ỉ
ể
i đi ph i
Sau b
c l p th
ừ ỉ
ố
l
đ nh
không mang ch s l n h n
đ nh nào nh ng nh ng đ nh trung gian trên l
b ngằ y.
ầ ử ủ
c l p th
ứ y, ta tính các ph n t
c a ma tr n
ằ
ậ a b ng công
ạ ướ ặ
T i b
ứ
th c sau:
ay[x,j] = min( ay1[x,j], ay1[x, y] + ay1[y, j]) (5.7)
ầ ử
ộ
ỉ
ướ ặ
ị ủ
ỉ ố y ch tr c a m t ph n t
trong ma tr n
ậ a sau b
ứ
c l p th
Ch s
y.
41
ượ ọ ằ ẽ ứ
Công th c này đ c minh h a b ng hình v sau đây.
y
ay-1[x,y]
ay-1[y,j ]
j
x
ay-1[x,j ]
c
ả
ạ
ụ
ố ư
ồ ư ạ
ậ ệ
ả ậ ữ
i thu t l p v i s h tr c a m t ma tr n đ l u tr
42
ế ế ượ quy
ể ệ ự
ậ
i thu t Floyd th hi n s áp d ng chi n l
Gi
ự
ộ
ộ cho m t bài toán t
ho ch đ ng
i u hóa vì s tính toán
ộ ệ ứ
ứ
i không
căn c vào m t h th c truy h i (5.6) nh ng l
ộ
ả
ự
i thu t đ quy. Thay vào đó là m t
xây d ng thành gi
ể ư
ộ
ậ ặ ớ ự ỗ ợ ủ
gi
ả
các k t qu trung gian.
Cải tiến giải thuật Floyd
Ta thường muốn biết lối đi ngắn nhất từ một đỉnh đến
một đỉnh khác bao gồm những đỉnh trung giannào.
Một cách để thực hiện điều này là dùng thêm một ma trận
P, với P[i,j] chứa đỉnh k mà khiến giải thuật Floyd tìm
được giá trị nhỏ nhất cho a[i,j].
Giải thuật Floyd cải tiến sẽ như sau:
for i := 1 to V do
for j:= 1 to V do
P[i,j] := 0;
for i := 1 to V do
a[i,i]:= 0;
43
for y : = 1 to V do
for x : = 1 to V do
if a [x, y] > 0 then
for j: = 1 to V do
if a [y, j] > 0 then
if (a[x, j] = 0) or (a[x, y] + a[y, j] < a [x, j]) then
begin
a[x, j] = a[x, y] + a[y, j];
P[x,j] := k;
end
Để in ra những đỉnh trung gian
trên lối đi ngắn nhất từ đỉnh x
đến đỉnh j, ta gọi thủ tục
path(x,j) với path là một thủ
tục đệ quy được cho ở hình
bên.
procedure path(x, j: int)
var k : int;
begin
k := P[x,j];
if k = 0 then return;
path(x,k); writeln(k); path(k,j);
end
44
2. Giải thuật tham lam
ả
ộ ố ướ ớ ộ
ườ
ọ ạ ỗ ướ
ậ ố ư
ự
i m i b
ườ
ọ
ộ
ả
Các gi
i u hóa th
ậ
t p các kh năng l a ch n t
lam th
i thu t t
ng đi qua m t s b
ả
ộ ả
c. M t gi
ố
ư t
ng ch n m t kh năng mà xem nh
c v i m t
i thu t tham
i lúc đó
ậ
ấ ạ
t nh t t
.
ậ
ố ư ụ ộ ớ
i u c c b v i hy
ụ
ế
ả
ọ
ứ
T c là, gi
ẽ ẫ
ọ
v ng s d n đ n m t l
ộ
i thu t ch n m t kh năng t
ộ ờ ả ố ư
i gi
ả
i u toàn c c.
i t
ụ ủ
ả
ậ
Vài thí d c a gi
i thu t tham lam:
ạ ộ
ế ị
Bài toán x p l ch cho các ho t đ ng
ạ
ố
Bài toán cái túi d ng phân s
Bài toán mã Huffman
ả
ể
ậ
ố
ể
Gi
i thu t Prim đ tính cây bao trùm t
i thi u
45
Bài toán xếp lịch cho các hoạt động (Activity-
Selection Problem)
ả ử ộ ậ s ta có m t t p S = {1, 2, …, n} g m
ỉ ể ượ ạ ộ
ồ n ho t đ ng mà
ụ ư ộ
ộ tài nguyên, thí d nh m t
ạ
ở ộ
c dùng b i m t ho t
Gi
cùng mu n s d ng cùng m t
ả
gi ng đ òng, mà ch có th đ
ộ
đ ng t ố ử ụ
ư
ạ ộ
i m t lúc.
ờ ể i có th i đi m b t đ u
ỗ
ể ắ ầ si và m t ộ th i ờ
ạ
ọ
c l a ch n, ho t
i, fi). Ho t đ ng
ễ
ươ
ươ ờ
ả
n u th i kho ng [s
ứ
i và j là t ng thích n u s ạ ộ i và j
i, fi) và [sj, fj) không ph ủ
ế i >= fj hay sj
ạ ộ
M i ho t đ ng
fi, mà si (cid:0)
ế ượ ự
ế
đi m k t thúc
fi. N u đ
đ ng ộ i di n ra trong th i kho ng [s
ả
ờ
ế
ng thích
là t
ấ
l p lên nhau (t c là,
>= fi).
ộ ọ
46
ạ ộ
ớ ế ị
ươ ố ạ ộ ỗ
ng thích v i nhau và có s ho t đ ng
ấ Bài toán x p l ch các ho t đ ng là ch n ra m t chu i các
ạ ộ
ho t đ ng t
ề
nhi u nh t.
Giải thuật tham lam cho bài toán xếp lịch các
hoạt động
ả ủ ụ i thu t tham lam đ gi
ụ
ạ ộ
ứ ự ậ
ả ử ằ
ủ ể ả
ạ ộ
ế ờ ể i bài toán
ậ
s r ng các ho t đ ng nh p
:
c a th i đi m k t thúc tăng
Trong th t c áp d ng gi
ế ị
x p l ch các ho t đ ng, ta gi
vào đ
f1 (cid:0) c ượ s p theo
ắ
… (cid:0)
f2 (cid:0) th t
fn.
47
{i}; j: = i end
procedure GREEDACTIVITYSELECTOR(S, f) ; /* s is
the array keeping the set of activities and f is the array keeping
the finishing times */
begin
n := length[s]; A := {1}; j: = 1;
for i: = 2 to n do
if si >= fj then /* i is compatible with all activities in A */
begin A: = A (cid:0)
end
Thủ tục Greedy-activity-selector
ượ
ườ ờ ể
ọ ở ủ ụ
ạ ộ
ế
ng là ho t đ ng v i
ợ ệ
ộ
ể ượ ế ị
c x p l ch m t cách h p l
c ch n theo cách “tham lam” theo nghĩa
ượ ạ ộ ề ạ ộ
Ho t đ ng đ
SELECTER th
ấ mà có th đ
ớ
s m nh t
ọ
ượ
ộ
đ ng đ
ạ ơ ộ ể ế ị
i c h i đ x p l ch cho đ
l c ch n b i th t c GREEDYACTIVITY
ớ th i đi m k t thúc
ạ
. Ho t
ẽ ể
nó s đ
. c nhi u ho t đ ngkhác
ậ ế ấ t đem l i t i l
ộ ờ ả ố ư ượ ộ i thu t tham lam không nh t thi
ủ ụ
c m t l i u cho m t th hi n c a
48
ng tìm đ
ế ị i gi
ạ ộ ạ ờ ả ố
ả
i
i gi
Gi
ư
u. Tuy nhiên th t c GREEDYACTIVITYSELECTOR
ể ệ ủ
ườ
th
i t
bài toán x p l ch các ho t đ ng.
ộ
i si fi
ế ị
ụ
Hình 5.5 M t thí d
ủ
c a bài toán x p l ch
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14
49
Hai thành phần chính của giải thuật tham lam
ả
ể
ấ ự ể
ọ ụ ả i thu t tham lam là: (1) tính ch t l a ch n tham
ấ
ậ
ể ấ Có hai tính ch t mà các bài toán ph i có đ có th áp
d ng gi
lam và (2) ti u c u trúc t ố ư .
i u
ự i thu t tham lam tùy
ộ ự
ự ọ ượ
ữ ậ
ế
ọ
ộ
ờ ả ủ i gi
ữ
ậ
ệ ả
ự ỗ ọ ệ ở ả
c th c hi n b i gi
L a ch n đ
ọ
ờ nh ng ư
thu c vào nh ng l a ch n đã làm cho đ n bây gi
,
ươ
ấ ỳ ự
nó không tùy thu c vào b t k l a ch n trong t
ng lai
ộ
ư ậ
ữ
i c a nh ng bài toán con
. Nh v y, m t
hay nh ng l
ố ,
ừ
ể t
ế
trên xu ng
i thu t tham lam ti n hành theo ki u
gi
ộ ự
th c hi n m i lúc m t l a ch n tham lam.
ố ư ấ ể ấ
Tính ch t ti u c u trúc t i u (Optimal Substructure)
ộ
ấ ể ấ
ữ ờ i u ch a trong nó nh ng l i t ố ư
i t ế
i u n u m t
ả ố ư
i u cho i gi
50
ộ
i gi
ữ M t bài tóan có tính ch t ti u c u trúc t
ứ
ả ố ư
ờ
l
nh ng bài toán con.
Giải thuật tham lam so sánh với quy hoạch động
ự ộ
ệ ữ
ể ả ả
ấ ế ố ư S khác bi
khi dùng đ gi ạ
t gi a qui ho ch đ ng và gi
i u là r t t
i bài toán t ậ
i thu t tham lam
ị
nh .
:
ạ
ượ ị
ư
Bài toán cái túi d ng 01 đ
c đ nh nghiã nh sau
ộ
ộ ẻ ộ
ấ n lo i ạ
ọ
ộ ử
ị
ư
ộ
ỉ
ứ ề ọ
ể
ệ
ậ
ượ
ứ i
ng và giá tr khác nhau (món hàng th
ượ wi), nh ng ch có m t cái túi
ọ
ng
ng là
M đ mang các món hàng. Bài
ẻ ộ
ớ
ể ạ ượ
ọ ỏ
ị ố
ữ
ộ
i đa v i nh ng
c m t giá tr t
ấ
'‘M t k tr m đ t nh p vào m t c a hi u tìm th y
món hàng có tr ng l
có giá tr ị vi đô la và tr ng l
ượ
ớ ứ
v i s c ch a v tr ng l
ộ ổ ợ
h p các món hàng mà k tr m nên
toán cái túi là tìm m t t
ch n b vào cái túi đ đ t đ
món hàng mà y l y đi.”.
ượ ọ c g i là bài toán cái túi d ngạ 01 vì m i ỗ
ỏ ạ ẻ ộ i, k tr m không
51
ể ấ ặ
ộ ủ Bài toán này đ
ặ
ấ
món hàng thì ho c là l y đi ho c là b l
ầ c a món hàng.
ỉ m t ph n
th l y đi ch
Bài toán cái túi dạng phân số (Fractional
knapsack problem)
ư ậ ố ế
ẻ ộ ạ
ể ấ ư ộ ộ t cũng nh v y,
Trong bài toán cái túi d ng phân s , tình ti
ầ ủ
nh ng k tr m có th l y đi m t ph n c a m t món hàng.
ả ề ể ấ ố ư .
i u ấ ti u c u trúc t
ấ ạ
ị ự ạ
ộ ổ ợ ặ
ế
i giá tr c c đ i. N u ta l y món hàng th
h p đem l
i cũng là t
ỏ
ị ớ ố
ổ ợ
i đa M w
ừ ặ ớ ọ
ạ h p n ng M
ứ j ra
ạ
ạ
i giá
ẻ ộ
ng t
j mà k tr m
ứ j.
ừ n1 lo i m t hàng tr m t hàng th
ườ ố
ố ớ
ấ ạ
ủ ỏ Đ i v i bài toán cái túi d ng phân s , xét tr
wj w ký c a m t hàng th
ổ ợ i cũng là t
52
ị ớ
ể ấ ợ
ng h p khi
ữ
ứ j, nh ng món
ớ
ấ ứ
i giá tr l n nh t ng v i
ừ n1 lo i ạ ạ
ng
C hai bài toán đ u có tính ch t
(cid:0) Đ i v i bài toán cái túi d ng 01, xét m t t
ố ớ
ạ
ký mà đem l
ữ
kh i túi, nh ng món hàng còn l
ượ
ấ ứ
tr l n nh t ng v i tr ng l
ặ
ể ấ
có th l y đi t
(cid:0)
ặ
ta l y ra kh i túi
ạ
h p đem l
hàng còn l
ượ M – (wj –w) mà k tr m có th l y đi t
ẻ ộ
ọ
tr ng l
ứ j.
ừ ặ
ặ
m t hàng tr m t hàng th
Bài toán cái túi dạng phân số (tt.)
ả
cho bài toán cái túi d ng phân
ạ i thu t tham lam
ạ
qui ho ch đ ng Ta dùng gi
s và ố ạ
ậ
ộ cho bài toán cái túi d ng 10.
ạ i bài toán cái túi d ng phân s , tr h ệ
ộ ơ ị ọ ố ướ
ng c tiên ta tính
ượ (vi/wi ) c a ủ
ể ả
Đ gi
ố
ị ề
s giá tr ti n trên m t đ n v tr ng l
ặ
ừ
t ng m t hàng.
ẻ ộ ắ ầ ố ề
ằ
ớ
ẽ ấ
ể
ặ
53
t m t hàng có h s v
ể ư ể ữ ế ặ
ấ
t m t
K tr m b t đ u b ng cách l y càng nhi u càng t
ạ
ạ
ấ
hàng có h s ệ ố vi/wi l n nh t. Khi lo i m t hàng này đã c n
ặ
ẻ ộ
ượ ữ
mà k tr m còn có th mang thêm đ
c n a thì y s l y
ứ
ớ
ệ ố i/wi l n nhì và c
ố
ề
càng nhi u càng t
nh th cho đ n khi y không còn có th mang thêm n a.
Hình 5.6
54
procedure GREEDY_KNAPSACK(V, W, M, X, n);
Vi+1/Wi+1. M is the knapsack capacity and X is
ờ
ỏ
B qua th i gian
ứ ự
ắ
s p th t
các
i ả
món hàng, gi
ộ
ậ
thu t này có đ
ứ ạ O(n).
ph c t p
/* V, W are the arrays contain the values and weights of n objects
ordered so that Vi/Wi (cid:0)
solution vector */
var rc: real; i: integer;
begin
for i:= 1 to n do X[i]:= 0;
rc := M ; // rc = remaining knapsack
capacity //
for i := 1 to n do
begin
if W[i] > rc then exit;
X[i] := 1; rc := rc – W[i]
end;
if i (cid:0)
end
55
n then X[i] := rc/W[i]
Mã Huffman
ủ ề
ế ấ
ỹ
ề nén file (file
ậ ượ
ữ ệ
ệ
c dùng
ế
t
ổ ế
ệ ừ
ấ ữ
ế
ể
Ch đ này liên quan đ n v n đ
compression). Các mã Huffman là k thu t đ
ệ
ph bi n và r t h u hi u cho vi c nén d li u, ti
ki m t
20% đ n 90% là đi n hình.
ệ
ế
ậ
ự
ỗ
ự
c đ u tiên c a vi c xây d ng mã Huffman là đ m
ủ
trong t p
ệ (frequency) c a m i ký t
ủ
ướ ầ
B
ầ ố ấ
t n s xu t hi n
ượ
tin đ
c mã hóa.
ự
ố
mà ta mu n
ữ ở ạ
ả ử
Gi
ư
l u tr
ộ ậ
s ta có m t t p tin 100000 ký t
d ng nén.
56
a b c d e f
ầ ố
T n s 45 13 12 16 9 5
ố ị
ề
Mã có chi u dài c đ nh 000 001 010 011 100 101
ổ
ề
Mã có chi u dài thay đ i 0 101 100 111 1101 1100
ộ
t k
ỗ
ễ ả ằ
ế ế m t mã nh phân cho ký t
c di n t
ị
ự ượ
đ
ự (binary
b ng
ộ
Xét bài toán thi
character code) theo đó m i ký t
ị
m t tràng bit nh phân.
ố ị
(3 bit) đ ể
ự
ế
N u ta dùng m t
ễ ả
di n t
ộ mã có chi u dài c đ nh
ề
:
6 ký t
a = 000, b = 001, . . . , f = 101
ầ ấ ả
ể
ậ
Thì c n t
t c 300000 bit đ mã hóa toàn t p tin.
57
Mã có chiều dài thay đổi
ổ (variablelength code) có th ể
ố ị
ắ ữ ữ ữ ệ ự
ộ
ấ
ữ ơ ề
M t ộ mã có chi u dài thay đ i
ề
ệ ố ơ
t h n m t mã có chi u dài c đ nh, nó cho
làm vi c t
ự
hay xu t hi n nh ng mã ng n và nh ng ký t
nh ng ký t
ệ
ấ
ít hay xu t hi n nh ng mã dài h n.
a = 0, b = 101, . . . f = 1100
Mã này đòi h i:ỏ
(45. 1 + 13 .3 + 12.3 + 16.3 + 9.4 + 5.4).1000 = 224000 bits
ễ ậ ể ể ế đ bi u di n t p tin, ti ệ
t ki m đ ượ (cid:0)
c 25 %.
58
ấ ố ư Và đ y cũng chính là mã t ậ
i u cho t p tin này.
Mã phi-tiền tố (Prefix-code)
ỉ ữ
ữ ộ
ư ậ ượ ọ ủ
đây ta ch xét nh ng cách mã hóa mà không có mã c a ký
ự
ủ
khác. Nh ng
nào là
mã phi ti n tề ố (prefixfree
Ở
ủ
ti n tề ố (prefix) c a mã c a m t ký t
ự
t
c g i là
cách mã hóa nh v y đ
code) hay mã ti n tề ố (prefixcode).
ượ ằ
ể ứ
ệ ở ộ ề ố ự Có th ch ng minh đ
hi n b i m t cách mã hóa ký t ố ư ượ
ự
c r ng s nén tin t
i u đ
và đó là mã phi ti n t ự
c th c
.
ả ự ơ ộ c a chu ng vì nó làm đ n gi n s mã
ề ố ượ ư
đ
ả Mã phi ti n t
hóa và gi i mã.
ơ ỉ ầ
ễ ượ ự ả
ẽ ể
i v i nhau thì s bi u di n đ ề
ọ
c m i ký t ủ
trong l
ự
S mã hóa là đ n gi n; ta ch c n ghép k các mã c a các
ự ạ ớ
ký t
ậ
t p tin.
ệ
59
ượ ặ ph n đ u ễ
ầ
ộ ự ể
i mã c n m t s bi u di n thu n ti n cho mã phi
ủ
ầ ầ c a mã đ
sao cho ậ
ễ
ộ
c nh t ra m t cách d
ự ả
S gi
ề ố
ti n t
dàng.
Mã phi tiền tố và cây nhị phân
ễ ớ ị
ể
ỗ ộ
Bi u di n cho m t mã phi ti n t
ươ ứ
m i nút lá t ề ố
ớ
ng ng v i các ký t ộ
là m t cây nh phân v i
ự ượ
đ c cho.
ộ ị
ả ộ
i m t mã nh phân cho m t ký t
ủ
ễ ế ự ấ ừ
nút r đ n nút lá c a ký t
ẽ ả ự ư
nh là
Chúng ta phân gi
ớ
ứ
i điố t
m t ộ l
y, mà 0 ng v i
ẽ
“r sang con bên trái” và 1 nghĩa là “r sang con bên ph i”.
ố ư ủ ượ ườ i u c a m t t p tin th ễ
c bi u di n b ng ng đ
ể
ộ ằ
ị ầ ủ (full binary tree). M t cây nh phân
ộ ỗ ả
ầ ủ
ủ ộ ậ
Mã t
ị
m t ộ cây nh phân đ y đ
ị
đ y đ là m t cây nh phân mà m i nút không ph i lá có
đ hai con.
ế ự ấ đó các ký t ị
l y ra, thì cây nh
ỗ i u có đúng |C| nút lá, m i nút lá
60
ự ộ ậ
N u C là t p ký t
phân cho mã phi ti n t
ộ
cho m t ký t ừ
ự
mà t
ề ố ố ư
t
, và đúng |C|1 nút n i.
100
100
1
0
0
14
86
1
55
a:45
1
0
0
0
1
30
14
25
58
28
1
0
1
0
1
0
0
1
0
1
f:5
a:45 b:13
c:12
d:16
e:9
c:12
b:13
d:16
14
1
0
e:9
f:5
(a)
(b)
Hình 5.7 So sánh hai cách mã hóa
61
Mã phi tiền tố và cây nhị phân (tt.)
ươ ứ ề ố ng ng v i m t mã phi ti n t , chúng ta
ớ ộ
ể ộ ậ ổ ố ể ộ
Cho m t cây T t
ầ
có th tính t ng s bit c n đ mã hóa m t t p tin.
ự ự c trong t p ký t C, dùng
ệ ầ
ủ ể
ề ậ
ệ ủ c trong t p tin và d f(c) đ ký hi u t n
T(c) là chi u dài c a mã
ậ ậ
ỏ ể
ự c. Thì s bit đòi h i đ mã hóa t p tin là
ớ ỗ
V i m i ký t
ố ấ
s xu t hi n c a
ố
cho ký t
B(T) = (cid:0) f(c)dT(c)
c(cid:0) C
62
ủ ị Mà chúng ta coi là chi phí c a cây nh phân T.
Cấu tạo mã Huffman
ể ấ ạ i thu t tham lam đ c u t o
ộ c g i là mã Huffman
ộ ả
ậ
ề ấ
Huffman đã đ xu t m t gi
ề ố ố ư ượ ọ
m t mã phi ti n t
i u đ
t
(Huffman code).
ươ ứ ớ ị i thu t t o m t cây nh phân T t ng ng v i mã t
ả ộ
d
ể ừ ướ
ự i lên. Gi
ệ ỗ ồ ố
i
ậ ắ ầ ớ ộ ậ
i thu t b t đ u v i m t t p
ụ tr nộ
ộ
ố ậ ạ
ả
Gi
ư
u theo ki u t
ồ
g m |C| nút lá và th c hi n m t chu i g m |C| tác v
ể ạ
đ t o ra cây cu i cùng.
ợ Q, l y tr khóa theo t n s
ấ
ị
ố ượ ệ ầ ố f,
ầ ố ỏ ấ ộ ư
ậ
c dùng đ nh n di n hai đ i t ng có t n s nh nh t
M t ộ hàng đ i có đ u tiên
ể
ượ
đ
ể ộ ạ ớ
đ tr n l i v i nhau.
ả ủ ố ượ ộ ố ượ
ầ ố ng là m t đ i t
ố ượ ổ ng
ng mà đã
63
ế
ớ
ượ ộ
ệ
K t qu c a vi c tr n hai đ i t
ầ ố ủ
m i mà t n s là t ng t n s c a hai đ i t
đ ộ
c tr n.
(a)
f:5
e:9
c:12
b:13
d:16
a:45
(b)
c:12
b:13
d:16
a:45
14
0
f:5
1
e:9
(c)
d:16
a:45
(d)
a:45
14
25
25
30
0
0
f:5
1
e:9
0
c:12
1
b:13
0
c:12
1
b:13
1
d:16
14
0
f:5
1
e:9
(e)
a:45
(f)
55
100
0
1
0
1
30
25
a:45
55
0
0
1
0
c:12
1
b:13
1
d:16
14
30
25
0
0
f:5
1
e:9
0
c:12
1
b:13
1
d:16
14
Hình 5.8 Các b
ã Huffman
ướ ủ
ả
c c a gi
ậ ạ
i thu t t o m
64
0
f:5
1
e:9
Giải thuật Huffman
Giả sử Q được hiện thực bởi một
heap.
Cho một tập C gồm n ký tự, việc
khởi tạo Q được thực thi với thời
gian O(n).
Vòng lặp for được thực thi chính
xác gồm n-1 lần, và vì mỗi tác vụ
làm việc trên heap đòi hỏi O(lgn),
vòng lặp này đóng góp chi phí
O(nlgn) vào thời gian tính toán.
procedure HUFFMAN(C) ;
begin
n := |C| ; Q := C ;
for i := 1 to n -1 do
begin
z: = ALLOCATE-NODE( );
left[z]: = EXTRACT-MIN(Q);
right[z]: = EXTRACT-MIN(Q);
f[z] := f[left[z]] + f[right[z]];
INSERT(Q, z);
end
end
Như vậy, độ phức tạp của giải
thuật HUFFMAN trên tập n ký tự
sẽ là O(nlgn).
65
Thí dụ 4: Bài toán tô màu đồ thị
Cho một đồ thị vô hướng, tìm số màu tối thiểu để tô
các đỉnh của đồ thị sao cho không có hai đỉnh nào
có cạnh nối lại được tô cùng màu.
Đây là một bài toán tối ưu hóa.
Một chiến lược để giải quyết bài toán này là dùng
giải thuật “tham lam”.
Ý tưởng: Đầu tiên ta cố tô cho được nhiều đỉnh với
màu đầu tiên, và rồi dùng một màu mới tô các đỉnh
chưa tô sao cho tô được càng nhiều đỉnh càng tốt.
Và quá trình này được lặp lại với những màu khác
cho đến khi mọi đỉnh đều được tô màu.
Chú ý: Giải thuật tham lam không đem lại lời giải tối
66
ưu cho bài toán.
Để tô màu các đỉnh trong đồ thị với một màu mới, ta
Thí dụ: Trong hình vẽ, ta tô đỉnh 1 với màu đỏ, rồi thì
thực hiện các bước sau:
Chọn một đỉnh chưa tô nào đó và tô nó với màu mới.
Duyệt qua danh sách các đỉnh còn chưa tô. Với mỗi đỉnh
chưa tô, xét xem nó có cạnh nối đến bất cứ đỉnh nào đã
được tô với màu mới không. Nếu không có một cạnh như
thế, ta tô đỉnh đó với màu mới.
ta có thể tô các đỉnh 3 và 4 với cùng màu đỏ.
3
1
5
2
4
67
Thủ tục SAME_COLOR
Thủ tục SAME_COLOR xác đinh một tập các đỉnh
(biến newclr), mà tất cả những đỉnh đó có thể tô với
cùng màu mới. Thủ tục này được gọi nhiều lần cho
đến khi mọi đỉnh đều đã được tô màu.
;
procedure SAME_COLOR(G, newclr);
/* SAME_COLOR assigns to newclr a set
of vertices of G that may be given the
same color */
begin
newclr := (cid:0)
for each uncolored vertex of G do
if v is not adjacent to any vertex in newclr
then
mark v colored and add v to newclr.
end;
68
;
procedure G_COLORING(G);
procedure SAME_COLOR(G, newclr);
/* SAME_COLOR assigns to newclr a set of
vertices of G that may be given the same color ;
a: adjacency matrix for graph G */
begin
newclr := (cid:0)
for each uncolored vertex v of G do
begin
found := false;
for each vertex w X newclr do
if a[v,w] = 1 /*there is an edge between v and w in G */
then
found := true;
if not found then
mark v colored and add v to newclr
end
end;
69
for each vertex in G do mark uncolored;
while there is any vertex marked uncolored do
begin
SAME_COLOR(G, newclr);
print newclr
end.
Bậc của một đỉnh: số cạnh nối đến đỉnh đó.
Định lý: Nếu (cid:0) (G) là số màu tối thiểu để tô đồ thị G và
(cid:0) G là bậc lớn nhất trong đồ thị G thì (cid:0) (G) ≤ (cid:0) G +1
Độ phức tạp của giải thuật tô màu đồ thị
Tác vụ căn bản: kiểm tra hai đỉnh có cạnh nối hay không.
Độ phức tạp của thủ tục SAME_COLOR: O(n).
Nếu m là số màu được dùng để tô đồ thị thì thủ tục SAME_COLOR
được gọi tất cả m lần. Do đó, độ phức tạp của toàn giải thuật:
m* O(n). Vì m thường là một số nhỏ, ta có thể nói
Giải thuật có độ phức tạp tuyến tính.
70
(cid:0)
Ứng dụng: Xếp lịch thi học kỳ
Mỗi môn thi được biểu diễn bằng một đỉnh trong đồ
Xếp lịch thi là gán ca thi vào các môn thi. Các ca thi
thị.
chính là các màu dùng để tô cho các đỉnh.
Một cạnh nối giữa hai đỉnh nếu có tồn tại ít nhất một
sinh viên lấy cả hai môn và phải thi cả hai môn, do
đó không thể xếp hai môn thi biểu thị bằng hai đỉnh
đó vào cùng một ca thi.
71
Ứng dụng: Gán tần số trong lãnh vực vô tuyến, điện
thoại di động (Frequency assignment problem)
Một Heuristic cho bài toán Tô Màu đồ thị
Màu có bậc lớn nhất được tô trước. (Welsh and Powell)
Bậc của một đỉnh: số cạnh nối đến đỉnh đó.
Lý do: Những đỉnh có càng nhiều cạnh nối tới thì
Giải thuật
Arrange the vertices by decreasing order of degrees.
Color a vertex with maximal degree with color 1.
Choose an uncolored vertex with a maximum degree. If
there is another vertex with the same maximum vertex,
choose either of them.
Color the chosen vertex with the least possible (lowest
numbered) color.
If all vertices are colored, stop. Otherwise, return to 3.
72
càng khó tô nếu ta đợi cho đến khi những đỉnh láng
giềng của nó đã được tô.
