Please purchase a
Please purchase a
personal license.
personal license.
C
C
Á
Á
C THU
C THU
Ậ
Ậ
T TO
T TO
Á
Á
N
N
THAM LAM (GREEDY)
THAM LAM (GREEDY)
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t tham lam
t tham lam
Khái niệm:

Traveling Salesperson Problem
Traveling Salesperson Problem
Giải quyết bài toán với giải thuật tham lam:
1. Xét các cạnh có độ dài từ nhỏ đến lớn để đưa vào chu
trình ( có n(n-1)/2 cạnh)
2. Mỗi cạnh sẽ được đưa vào chu trình nếu:
1. Không tạo thành một chu trình thiếu (tạo thành chu
trình trước khi đi đủ hết tất cả n đỉnh)
2. Không tạo thành một đỉnh có cấp >=3 ( không có
nhiều hơn 2 cạnh xuất phát từ một đỉnh, do yêu cầu
của bài toán mỗi thành phố chỉ đến 1 lần: 1 đến, 1 đi)
3. Lặp lại bước 2 cho đến khi xây dựng được 1 chu
trình
Traveling Salesperson Problem
Traveling Salesperson Problem
Ví dụ:
Cho độ dài đường đi giữa các thành phố được
biểu diễn bằng ma trận kề sau. Tìm chu trình ngắn nhất
giữa các thành phố
• (3,5) = 1  (5,6) = 2  (4,7) = 4
(2,7) = 5  (1,6) = 7 (1,4) = 13
(2,3) =21
Tổng đường đi: (1,4,7,2,3,5,6,1)=53
 Đây chỉ là phương án tốt
Phương án tối ưu: (1,4,7,2,5,3,6,1) =41
1 2 3 4 5 6 7
1 16 12 13 6 7 11
2 21 18 8 19 5
3 20 1 3 15
4 14 10 4

a mãn
đ
i
ề
u ki
ệ
n )
{ cycle = cycle + e;
length_cycle = length_cycle + length(e);
}
E = E – e;
}
}
Traveling Salesperson Problem
Traveling Salesperson Problem
Giải pháp khác của thuật toán tham lam:
1. Xuất phát từ 1 đỉnh bất kỳ, chọn 1 cạnh có độ dài nhỏ
nhất từ đỉnh đó đến đỉnh kế tiếp.
2. Từ đỉnh kế tiếp, chọn cạnh có độ dài nhỏ nhất đi ra từ
đỉnh này thỏa mạn 2 điều kiện ( không tạo chu trình
trước khi qua n đỉnh, 1 đỉnh không lớn hơn 2 đường
đi)
3. Lặp lại bước 2 cho đến khi đi đến n đỉnh thì quay lại
đỉnh xuất phát
Traveling Salesperson Problem
Traveling Salesperson Problem
Bài tập: Tìm đường đi ngắn nhất của người giao
hàng với độ dài giữa các thành phố cho bởi ma
trận sau:
Đường đi đã tìm ra tối ưu chưa?