Bài giảng Thiết kế và đánh giá thuật toán - Tham ăn - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Tham Ăn
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Bài toán

 Trả tiền thừa

 Ba lô

 Chiến lược tham ăn

 Cây bao trùm nhỏ nhất

 Thuật toán Prim

 Thuật toán Kruskal
1
Bài Toán Trả Tiền Thừa

 Các loại đồng xu 100c, 25c, 10c, 5c, 1c

 Với khoản tiền cần trả lại, sao cho số
lượng đồng xu là ít nhất.

 Ví dụ: trả lại 189c

 189 xu 1c => 189

 18 xu 10c, 1 xu 5c, 4 xu 1c => 23
2
Bài Toán Trả Tiền Thừa

 Số lượng đồng xu trả lại là ít nhất?

 Ý tưởng:

 Sử dụng lần lượt các đồng xu có mệnh giá từ
lớn nhất đến nhỏ nhất

 Hy vọng số lượng đồng xu là ít nhất

 Ví dụ: trả lại 189c

 1 xu 100c, 3 xu 25c, 1 xu 10c, 4 xu 1c => 9

 9 xu đã ít nhất chưa
3
Lập Trình Động – Nhắc Lại

 Thường áp dụng cho bài toán tối ưu

 Xác định được lời giải tối ưu

 Dựa trên lời giải tối ưu các bài toán con

 Có thể phức tạp hóa vấn đề

 Không khả thi với bài toán thực tế

 Không gian tìm kiếm rộng

 Thời gian tìm kiếm lâu
4
Chiến Lược Tham Ăn

 Xác định phương án (lời giải) tốt nhất tại
thời điểm quyết định

 Chọn tối ưu cục bộ (local optimal)

 Hi vọng tìm được tối ưu toàn cục (global 
optimum)

 Có thể tìm được lời giải tối ưu với một số
bài toán

 Hiệu quả trong thực tế
5
Tham Ăn – Lập Trình Động

 Đều áp dụng tìm lời giải tối ưu

 Lập trình động

 Thiết kế dưới lên (bottom-up design)
1. Giải bài toán nhỏ
2. Sau đó xác định phương án lời giải

 Tham ăn

 Thiết kế trên xuống (top-down design)
1. Xác định phương án lời giải
2. Sau đó giải bài toán nhỏ
6
Trả Tiền Thừa – Lập Trình Động

 Giải bài toán nhỏ

 Có sử dụng loại xu xxx hay không (co/không)

 Số tiền trả tăng dần từ 0

 Thiết kế bảng 2 chiều

 Gần tương tự bài toán ba lô?
7
Trả Tiền Thừa – Tham Ăn

 Các loại đồng xu 100c, 25c, 10c, 1c

 Với khoản tiền cần trả lại, sao cho số
lượng đồng xu là ít nhất.

 Ví dụ: trả lại 133c

 Kỹ thuật tham ăn?

1 xu 100c, 1 xu 25c, 8 xu 1c => 10

 1 xu 100c, 3 xu 10c, 3 xu 1c => 7

 Tham ăn có thể không cho lời giải tối ưu
8
Bài Toán Ba Lô

 Nhặt đầy đồ vật vào ba lô sao cho tối ưu

 Điều kiện khối lượng ba lô

Mục tiêu tối ưu lợi nhuận

 Bài toán:

 Có N đồ vật, với khối lượng wi và giá trị ti

 Khối lượng ba lô không vượt quá M

 Xác định tập đồ vật để tổng giá trị lớn nhất

 Sử dụng kỹ thuật tham ăn
9
Bài Toán Ba Lô – Tham Ăn
N = 5, M = 100
i A B C D E
wi 10 20 30 40 50
ti 20 30 66 40 50
10
Bài Toán Ba Lô – Tham Ăn
N = 5, M = 100
i A B C D E
wi 10 20 30 40 50
ti 20 30 66 40 50
Tham ăn theo cân nặng (wi)
Xi 1 1 1 1 0

 = 156
11
Bài Toán Ba Lô – Tham Ăn
N = 5, M = 100
i A B C D E
wi 10 20 30 40 50
ti 20 30 66 40 50
Tham ăn theo giá trị (ti)
Xi 0 1 1 0 1

 = 146
12
Bài Toán Ba Lô – Tham Ăn
N = 5, M = 100
i A B C D E
wi 10 20 30 40 50
ti 20 30 66 40 50
Tham ăn theo tỉ trọng (ti / wi)
Xi 1 1 1 1 0

 = 156
13
Đồ Thị – Định Nghĩa
Đồ thị có hướng  = (	, ) bao gồm

 Tập 	 các đỉnh

 Tập  ⊆ 	 × 	 cạnh

 Đồ thị vô hướng

 Cặp cạnh không có thứ tự ,  = (, )

 Đồ thị định hướng

 Cặp cạnh có thứ tự ,  ≠ , 
Cả hai trường hợp,  = (	).
Nếu  liên thông,  ≥ 	 − 1,
⟹ log  =  log 	
14
Đồ Thị – Ví Dụ
vô hướng định hướng
15
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
Đồ Thị – Ví Dụ
trọng số không trọng số
16
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
5 7
11 15
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
Đồ Thị – Ví Dụ
liên thông không liên thông
17
Đồ Thị – Biểu Diễn

 Biểu diễn  = (	, , với 	  	 1, 2,  ,  , là ma 
trận !"1	. . , 1	. . $
! %, &  '1	nếu	 %, & ∈ 	0	nếu	 %, & ∉ 
18
 	
lưu trữ
Bài Toán Cây Bao Trùm Nhỏ Nhất

 Input: Đồ thị liên thông, vô hướng
  (	, ) có trọng số .: 	 → ℝ

 Output: Cây bao trùm 2 – một cây kết nối
tất cả các đỉnh với trọng số nhỏ nhất
. 2 = 
 .(, )
3,4 ∈5
19
Cây Bao Trùm Nhỏ Nhất – Ví Dụ

 Input:
20
Cây Bao Trùm Nhỏ Nhất – Ví Dụ

 Output
21
Cấu Trúc Con Tối Ưu
Xóa một cạnh bất kỳ (, ) 	∈ 2. Thì, cây 2
được chia thành 2 cây con 26 và 2
Định lý. Cây con T6 là cây bao trùm nhỏ
nhất của 6 = (	6, 6), 6 là đồ thị con của bao gồm các đỉnh của 26
	6 = đỉnh của 26
6 = 8, 9 ∈ : 8, 9 ∈ 	6
Tương tự với 2
22
Thuật Toán Prim
:: tập các đỉnh kề các cạnh trong tập cạnh 2
Ban đầu tập : chứa một đỉnh tuỳ chọn của 
đồ thị , còn 2 rỗng.
Tại mỗi bước lặp:
1. Chọn (, ) ngắn nhất,  ∈ :,  ∈ 	 − :
2. Thêm đỉnh  vào tập đỉnh :
3. Thêm cạnh (, ) vào tập cạnh 2.
Tiếp tục phát triển cây 2 cho tới khi : = 	, ta 
nhận được 2 là cây bao trùm
23
Thuật Toán Kruskal
Tập 2 các cạnh được xây dựng dần từng
bước xuất phát từ 2 rỗng.
Tại mỗi bước cạnh (, ) được chọn thêm
vào 2 là cạnh ngắn nhất trong các cạnh
còn lại và không tạo thành chu trình với các
cạnh đã có trong 2.
24