Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 81 - CHƯƠNG 5: PHƯƠNG PHÁP THAM LAM
(The greedy method)
I. Mở đầu
1. Ý tưởng
Phương pháp tham lam là kỹ thuật thiết kế thường được dùng để giải các bài
u cho bài
øi toán được bổ sung dần từng bước từ lời giải
øi toán ?
ược ằng p ương háp tham lam thường chỉ là chấp nhận
on S của
. Với một tập con S được chọn ra thỏa mãn các yêu cầu của bài toán, ta gọi là một
ghiệm i áp nha được với
nghiệm chấp nhận được mà tại đó hàm mục tiêu đạt
Đặc trưng tham lam của phương pháp thể hiện bởi : trong mỗi bước việc xử
ốt có thể xảy
toán tối ưu. Phương pháp được tiến hành trong nhiều bước. Tại mỗi bước, theo một
chọn lựa nào đó ( xác đònh b
ằng một hàm chọn), sẽ tìm một lời giải tối ư
toán nhỏ tương ứng. Lời giải của ba
của các bài toán con.
Lời giải được xây dựng như thế có chắc là lời giải tối ưu của ba
Các lời giải tìm đ b h p
được theo điều kiện nào đó, chưa chắc là tối ưu.

- Cập nhật các đối tượng để chọn : A = A-{x};

Cập nhật lời giải : S = S∪ {x};
ó thể cài đặt như sau : Thủ tục thuật toán tham lam c
input A[1 n]
output S //lời giải;
while ( A
≠ ∅)
{
x= Chọn(A);
A
}
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 82 - 1

2 return S;
I. Ba toán ườ


từ thành phố hiện thời đến các thành phố chư
1
5 2

3 4 4
5 2
3 7 3 put
ành trình tối ưu, hỏ nhất tính từ TP v đến
ập nhật lời giải
vw
; //Cập nhật chi phí
C =
⎦
⎢
⎢
03235
21042In C= (C
ij
)
output TOUR //H
COST;//Chi phí tương ứng

⎤
⎡
57210
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 83 -

2 1

2

2

3

2
2 4 1 OUR := {<1,2>, 2,5>,<5,3>,<3,4>} 5. T
COST := 7; u = 1;

TOUR := {<1,2>, <2,5>,<5,3>,<3,4>
COST := 14
4. Độ phức tạp của thuật toán
Thao tác chọn đỉnh thích hợp trong n đỉnh được tổ chức bằng một vòng lặp
øng lặp lồng nhau, nên
n
2
).
5. Cài đa
để duyệt. Nên chi phí cho thuật toán xác đònh bởi 2 vo
T(n)
∈ O(
ët
int GTS (mat a, int n, int TOUR[max], int Ddau)
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vn

= 0; //Luc dau, gia

int i; // Bien dem, dem tim d inh thi dun
v = Ddau; //Chon dinh xuat phat la
i = 1;
TOUR[i] = v; //Dua v vao chu trinh
daxet[v] = 1; //Dinh v da duoc xet

while(i < n)
{
mini

if(!daxet[k])

mini = a[v][k];
w = k;
}
v = w;
i++;
TOUR[i] = v;
daxet[v] = 1;
COST += mini;
}
COST += a[v][Ddau];
return COST;
}
I h oán DII. T uật t ijkstra -Tìm đường
t srọng ố
1. Bài toán
(vô hướng hoặc có hướng) có trọng

chính thức. Nếu nhãn của một đỉnh nào đó trở
thành c đi từ s đến
đỉnh đó.
3.
đỉnh còn lại của đồ thò và chiều dài (trọng
Phương pháp của thuật toán là xác đònh tuần
thứ tự tăng dần.
Thuật toán được xây dựng trên cơ sở gán cho
Nhãn tạm thời của các đỉnh cho biết cận trên của chie
đến đỉnh đó. Nhãn của các đỉnh sẽ biến đổi trong các bư
sẽ có một nhãn tạm thời trở thành
hính thức thì đó cũng chính là chiều dài ngắn nhất của đường
Mô tả thuật toán
Ký hiệu :
* L(v) để chỉ nhãn của đỉnh v, tức là cận trên của chiều dài đường đi ngắn
s
0
đến v.
án n-1 đỉnh
òn lại
input
Output : d(s ,v
Mô tả
Khởi động :
õn chính thức
S = {s
0
}; // s có Nhãn chính thức
1:
- T thơ ), v

nhất từ s
0
đến v.
* d(s
,v) : chiều dài đường đi ngắn
0
nhất từ
* m(s
0
,v) là trọng số của cung (cạnh) (s,v).
Thuật toán Dijkstra tìm chiều dài đường đi ngắn nhất từ đỉnh s đe
c đ ô tả như sau : ược m
: G, s
0
), ∀v ≠ s ;
0 0
:
•
L(v) =
∞ , ∀v ≠ s
0
; //Nhãn tạm thời
S =
∅; //Tập lưu trử các đỉnh có nha
• 0 : Bước
d(s
0
,s
0
) = L(s

1
) + m(s
1
,v)};
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 86 - - Tìm s
2
∉ S và kề vơ o cho :
L(s
∀v ∉ S};
d(s,s
2
) = L(s
2
) ); //0 = d(s
0
,s
1
) ≤ d(
0
,s

) = Min{L(v) :
( Khi đó :
s
s
ắn nhất, và s
j
là đỉnh đứng kề trước s
2
.
- S = S
∪ {s }; // S = {s , s , s } ; //s có nhãn chính thức
. . .
• Bước i:
- Tính lại nhãn tạm thời L(v), v
∉ S :
Nếu v kề với s
i-1
thì
L(v) = Min{L(v), L(s
) + m(s ,v)};
- Tìm s
i
∉ S và kề với s 1,0 −i sao cho :

( d(s,s
i
= d(s,s
1
) ≤ d(s,s
2

n-
đến t, thì thuật toán dừng khi có t
∈
S.
lam của thuật toán Dijkstra là tại mỗi bước, chọn s
i
∉ S và s
i

L(s
i
) = Min{L(v) : ∀v ∉ S };
) = L(s
i
) ); //0
u L s
i
) = Min{L(s
j
), L(s
j
) + m(s
j
,s
i
)} thì đường đi ngắn nhất từ s đến s
i
đi
, và s
j

10 80

90

15 18 40
36

10 30 4 15
4
5 2
15
4
20 6
10
3
1

Đường đi ngắn nhất từ đỉn
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 87 -


Chiều dài của đường đi ngắn nhất
từ đỉnh s (=1) đến các đỉnh khác : tsnn[]
S = {1};
Bước 1 :
- Tính nhãn tạm thời L(v), v
∉ S :
* Các đỉnh
∉ S
L
L(3) = Min{ L(3),
L(5) = Min{ L(5), L(1)+
* Các đỉnh
∉ S và không k
L(4) = L(6) = ∞.
-
1
à ùi 1 sao cho :L(s
1
) = Min{L(v) : ∀v ∉ S };
L(3) = Min{L(v) :
∀v ∉
Đường đi từ 1 đến 3 xác đònh bởi : 1 → 3 là ngắn nhất tr
đường đi từ 1 đến các đỉnh khác và d(1,3) = L(3) = 15.
-
∪
Bước
- Tính nhãn tạm thời L(v), v
∉ S :
* ỉ
và kề với 3 là 2,6 :

∞
Bước2 1→3→ 2 2 - 19 - 25
Bước3 1→3→ 6 6 - - - 29 25
Bước4 1→3→ 6→4 4 - - - 29 -
Bước5 1→3→ 2→5 5 - - - - 29 -

4. Cài đặt
- Ta biểu diễn đơn đồ thò có hướng G bằng ma trận các trọng số của cạnh :
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 88 - a= (a
uv
)
nxn
;
trong đó :
⎩
⎨
⎧
∉∞
∈
=

ngắn nhất từ s đến các đỉnh còn lại
ùng
{
øn t tại mỗi bước Daxet[i] = 0;
- Dùng mảng 1 chiều để lưu trử các nhãn tạm thời của các đỉnh
L
- Dùng mảng 1 chiều Daxet[ ] các giá trò logic để đánh dấu các đỉnh đã được
đưa vào tập S ( gồm các đỉnh có nhãn chính thức ):
Mỗi bước, nếu xác đònh được đỉnh k để
của đường từ s đến k) .
- Khởi động dữ liệu :
o Khởi động Daxet[] là rổng :
o Khởi động cận trên chiều dài của đường đi ngắn nhất từ s đến đỉnh
khác ( đán
o Khởi động trọng số nhỏ nhất đường đi từ s đến s bằng 0.
L[s] = 0;//d(s,s) = 0
- Giả sử tại mỗi bước, ( với Dht la
Nếu (L[i] + m(Dht,i) ) < L[i]) thì :
L[i] = L[Dht] + m(Dht,i);
Và trong trường hợp này, đường đi ngắn nhất từ s đến i sẽ đi qua đỉnh
ỉnh kề trước i)
- Để lưu trử các đỉnh trên
ột chiều Ddnn[ ], với tính chất Ddnn[i] là đỉnh trước đỉnh

Thuật toán được cài đặt bằng hàm sau :
t a[n][n], s
Output - Xuất ra màn hình đường đi

{
=
for ( i = 1; i <= n; i++)
if(!Daxet[i])
{

{
L[i] = L[dht] + a[dht][i] ;
dht;
//gan dinh hien tai la dinh truoc dinh i tren lo
inh
}
if(L[i] < Min) // Chon đỉnh k
{
in = L[i];
k = i;
}
}
ng đi ngắn nhất từ s đến k : Ddnn[]
xuatdd(s,k,Ddnn);
cout<< ng so
dht = k;//
Daxet[dht] = 1; a nut k vao t da xet
h++;
}

****************** *******
oid xuatdd(int s, int k, Ddnn[m

int


}
// **
v int ax])
{
i;
cout<<"\n
i = k;
while(i != s)
{
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 90 - cout<<s;
}

5. Độ phức tạp của thuật toán
Thuật toán mô tả bởi 2 vòng lặp lồng n
2
hau, nên T(n) ∈ O(n ).

IV. Thuật toán Prim – Tìm cây bao trùm nhỏ nhất (Minimal Spanning
Tree)

M t toán
nput G = (V,E)
Output T = (V, .) là MST
Mô tả :
- Gọi U là tập con của V.
- on rổng.
đỉnh 1 đặt vào T.
-
ìm ca hỏ nhất, với u
∈U và v ∉ U. Thêm đỉnh v
lời giải tối ưu.
Khởi động T = (U,.) = ∅; //Đồ thò c
- Khởi động U = {1}; // Chọn
Trong khi ( U ≠ V )
T ïnh (u,v) có trọng số n
này vào U. Thêm (u,v) vào T .
Lời giải của bài toán là

Minh họa :
Xét đồ thò sau :
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 91 -
5
7
6

3
Hoạt ật

ớc cạnh chọn Tập U
3
0 - {1}
1 (2,1 {1,2

) }
2 (3,2) {1,2,3}
3 (4,1) {1,2,3,4}
4 (5,4) {1,2,3,4,5}
5 (7,4) {1,2,3,4,5,7}
6 (6,7) {1,2,3,4,5,7,6}

4. Cài đặt
Để tiến hành cài đặt thuật toán, ta cần mô tả dữ liệu .
Đồ thò rận kề của nó :
c = (c[i][j])
nxn

j
tainotji
)
)
)
ọ

Khi tìm cạnh có trọng số nhỏ nhất
tại mỗi bước, ta sẽ
nối 1 đỉnh trong U và một đỉnh ngoài U
ảng lowcost để tìm đỉnh closest[k]
∈ U sao cho
lo
loses và lowcost ,và có k đã thêm vào U.
hi ma đỉnh k cho cây bao trùm, ta cho lowcost[k] =
∞, là một giá
vậy đỉnh này sẽ

Closest[i] = 1;

{
cost[2];
ost[j] < Min )
Min = Lowcost[j];
;
sest[k];

g l
r ( j=2; j<=n; j++)
c[k][ j] < lowcost[j]) && (lowcost[j] <

if (Lowc
{

k = j
}
cout<<endl<<k<<clo
lowcost[k] =
∞;
// Khởi độn ại Closest[], Lowcost[]
fo
if ( (Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 93 - }
}
5. Độ phức tạp thuật toán
Ta có thể thấy là Độ phức tạp trong thuật toán Prim là O(n
2
).
V. Bài toán ghi các bài hát

=
KD )(
=
i
k
a
k
i

a[i] 5 10 3 Dung lượng

b
1
k
a

21
k
a
k
a +

321
k
a
k
a
k
a ++


Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 94 - T nhận xét rằng D(b) đạt min nếu
j
T
a có
1
;
∑
=
=
j
i
i
k
a
∀∈jn1. . đạt min .
k
a
được chọn vào là giá trò nhỏ nhất của dãy
trường hợp này là các Tj được
chọn trong mỗi bước thêm vào
đó, lời giải tìm được sẽ là lời giải tối ưu. Thuật toán

* Khởi động b[
* for (i = 1
→ n)
- Chọn j = m
b
a
- C iá t
[i];
* retu
3. Độ p ùc ua
ật toán chọn min được sử dụng chính là chọn trực tiếp, Ta d
hức tạp của thuật toán trong các trường hợp là O(n
2
).
Thu ễ thấy độ
p
4. Cài đặt
int record_greedy(int a[max],int b[max],int n)
{

int
b[i] = i;
+)
; // Chính xác lại b tại mỗi bước
oicho(a[i],a[j]);
[
Chính xác dần min trong mỗi bước
n;

int i,t= 0,min = 0;

hả năng mang m kg. Giả sử w
i
, v
i
, m ∈
,
áp vào ba lô sao cho ba lô thu được có giá trò nhất.
ủa n vật có thể biểu diễn bởi mảng :
w = ( w
1
, w
2
, . . , w
n
);
Và giá trò tương ứng của các vật :
v = ( v
1
, v
2
,. . .,v
n
);
[ ], với qui ước :
giá trò v
i
(US). Có một chiếc túi xách có k
N*
∀i ∈ {1, ,n}.
Hãy chọn vật xe

ε
⎪
⎨
≤
∑
=
mw
i
ii
1
ε
⎪
n

Thiết kế thuật toán
Thuật toán tham lam cho bài toán chọn vật có giá trò giảm dần (theo đơn
iá ).
utput
, n, m)
≡
g
Input
w = ( w
1
, w
2
, . . . ,w
n
); // Trọng lượng
v = ( v


* for (i = 1; i <= n && m > 0 ; i++)
{
- Chọn j = arcmax(d,n,i); // d[j] = Max{d[i], ,d[n]};
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 96 - - b[i] ↔ b[j] ;
- // Cập nhật lại Vmax, Chon[ ], m;
if (m > w[b[i]])
{
Vmax += v[b[i]];

ε[b[i] = 1;
m -= w[b[i]];
}
- d[i]
↔ d[j] ;
).

X_GREEDY(long w[],long v[],int C[],int n,long m)
ble d[max]; // Mang don gia
b[i] = i;
C[i] = 0;
j = arcmax(d,n,i);
dcn(b[i],b[j]); //Đổi chỗ
long MA
{
int i,j,k,b[max];
long Vmax = 0;
dou
for (i = 1; i <= n; i++)
{ d[i] = (double)w[i]/v[i];
}
for(i = 1; i <= n && m > 0; i++)
{ Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -