PHÂN TÍCH THIẾT KẾ THUẬT GIẢI
THUẬT GIẢI THAM LAM
TS. NGÔ QUỐC VIỆT- 2015
Nội dung
1. Giới thiệu 2. Các thuật giải tham lam 3. Bài tập 4. Hỏi đáp.
2
Giới thiệu Thuật giải tham lam (greedy algorithm) Là một phương pháp tìm kiếm lời giải “tối ưu”. Thuật giải tham lam tiếp cận theo cách: ở mỗi bước
chọn lời giải tốt nhất
Được gọi là tối ưu cục bộ. Phần lớn tìm được lời giải
tối ưu.
Tuy nhiên có thể vì lựa chọn này dẫn đến lời giải sau
cùng không tối ưu toàn cục.
3
Một số thuật giải Greedy Fractional knapsack algorithm Huffman codes Kruskal's MST algorithm Prim's MST algorithm Dijkstra's SSSP algorithm
4
Thuật giải tham lam- Minh hoạ 1 Bài toán đổi tiền lẻ: cho một tập các đồng xu có mệnh giá khác nhau. Cần đổi N đồng lấy các đồng xu sao cho số đồng xu ít nhất.
Ví dụ: 24 = 10+ 10 + 1 + 1 + 1 + 1. Tuy nhiên nếu có
đồng 8 xu thì cách chọn trên không tối ưu.
Tiếp cận theo thuật giải tham: chọn đồng xu mệnh
giá lớn nhất có thể tại mỗi bước.
5
Thuật giải tham lam- Minh hoạ 1 Sắp xếp tập đồng xu giảm dần
6
Thuật giải tham lam- Minh hoạ 2
Bài toán lịch làm việc:
Việc j bắt đầu tại sj và kết thúc tại fj. Mỗi thời điểm làm một việc. Hai công việc không được làm chồng chéo. Yêu cầu: làm nhiều việc nhất có thể (tình theo thời gian, chứ
không phải số đầu việc)
7
Thuật giải tham lam- Minh hoạ 2 Tiếp cận tham lam cho bài toán này. Xét các thứ tự có
thể. Bắt đầu sớm nhất: xếp tăng dần theo si. Kết thúc sớm nhất: xếp tăng dần theo fi. Khoảng ngắn nhất: xếp tăng dần theo (fi-si) Ít chồng chéo nhất: với việc j, đếm số lượng (gọi là cj) việc có
chồng chéo với việc j. Xếp tăng dần theo cj.
8
Thuật giải tham lam- Minh hoạ 2 Giả sử chọn: sắp xếp tăng dần theo fi. Việc j có thể thêm vào nếu không chồng chéo với việc cuối cùng vừa thêm vào A.
9
Thuật giải tham lam- Minh hoạ 3
Bài toán xếp lịch giảng dạy n môn học vào m phòng
học. Môn j bắt đầu tại sj và kết thúc tại fj. Mục tiêu: tìm số phòng tối thiểu để có thể dạy tất cả các môn sao cho một môn không dạy ở hai phòng cùng lúc trong ngày.
Ví dụ có 4 phòng học, và 10 môn.
10
Thuật giải tham lam- Minh hoạ 3
Cách sắp xếp khác
11
Thuật giải tham lam- Minh hoạ 3 Xếp môn học tăng dần theo si.Xếp vô phòng học 1 trước, khi phòng học này đầy, xét đến phòng học kế tiếp …
12
Thuật giải tham lam- Minh hoạ 4 Bài toán xếp lịch nhằm giảm tối đa việc trễ giao hàng.
Mô tả: Việc j cần tj thời gian và phải giao tại thời điểm dj. Nếu j bắt đầu lúc sj, thì sẽ kết thúc tại fj = sj+tj. Độ trễ lj=max(0, fj-dj). Mục tiêu: sắp xếp các việc sao cho giảm tối đa L=max(lj).
13
Thuật giải tham lam- Minh hoạ 4
Ví dụ: sắp lịch cho 6 việc có thời gian làm và thời hạn giao hàng như sau
Một cách sắp xếp
14
Thuật giải tham lam- Minh hoạ 4 Sắp xếp các việc theo tiêu chuẩn nào đó (tăng dần
theo thời gian xử lý, theo thời hạn giao hàng, …)
Thực hiện xếp vô hàng đợi các việc thoả mãn ràng buộc (không chồng chéo) theo thứ tự đã chọn. Ví dụ thuật giải tham cho các việc xếp tăng dần theo deadline như sau
15
Thuật giải tham lam- Minh hoạ 4
16
Thuật giải tham lam- Minh hoạ 4 Cải tiến xếp lịch sao cho không có thời gian rảnh. Ví
dụ:
Thực hiện bằng cách bổ sung thêm bước hoán vị ‘nghịch thế’ sau khi đã xếp lịch bằng thuật giải tham. Chú ý hoán vị các nghịch thế kề nhau (giống Buble sort) nếu cần.
17
0-1 vs. Fractional Knapsack 0-1 Knapsack Problem:
Các vật không thể chia nhỏ Hoặc là chọn vật hoặc không chọn cho vào ba lô Giải bằng DP hoặc Greedy
Fractional Knapsack Problem:
Vật có thể được chia nhỏ (có thể lấy một phần cho vào ba lô) Giải thông qua greedy algorithm…
18
Greedy Fractional Knapsack Algorithm Sắp xếp các items theo giá trị trên mỗi đơn vị giảm
dần
While ba lô còn trống do
Xét next item trong danh sách đã xếp giảm dần Lấy càng nhiều càng tốt O(n log n) running time ?
19
Greedy Fractional Knapsack Algorithm
and weight
Input: set S of items w/ benefit bi
Algorithm fractionalKnapsack(S, W) wi; max. weight W Output: amount xi of each item i to maximize benefit w/ weight at most W
for each item i in S
xi 0 vi bi / wi {value} w 0 {total weight} while w < W remove item i w/ highest vi xi min{wi , W - w} w w + min{wi , W - w}
20
Greedy 0-1 Knapsack – Ví dụ 3 item
item 1 weighs 10 kg, worth $60 ($6/kg) item 2 weighs 20 kg, worth $100 ($5/kg) item 3 weighs 30 kg, worth $120 ($4/kg)
Ba lô chứa tối đa 50kg Kết quả theo thuật giải Greedy
Lấy item 1 Lấy item 2 Không còn chỗ cho item 3 không hiệu quả
Dùng DP để giải quyết
21
Greedy Fractional Knapsack – Ví dụ
2/3 Of 30
$80 +
Item 3
50
Item 2
50 20
30
Item 1
$100 +
20
10
10
$60
$60
$100
$120
W
$240
Greedy choice:
Compute the benefit per pound Sort the items based on these values Take as much as you can from the top items in the list 22
$6/kg $5/kg $4/kg
Một số Spanning Trees từ A
or
or
or
Cây bao trùm tối tiểu – Minimum spanning tree Cho đồ thị G liên thông vô hướng, cây bao trùm (cây khung) được định nghĩa là đồ thị con dạng cây (không có chu trình) có mọi đỉnh của G và mọi đỉnh liên thông nhau. Một đồ thị có thể có nhiều cây bao trùm. Graph A
23
Cây bao trùm tối tiểu Số lượng cây bao trùm của đồ thị G
1 𝑛
𝑡 𝐺 =
𝐺 𝑙à 𝑐â𝑦 𝐺 đồ 𝑡ℎị 𝑣ò𝑛𝑔 𝐶𝑛 𝑛𝑛−2 𝐺 đồ 𝑡ℎị đầ𝑦 đủ 𝐾𝑛
Đồ thị đầy đủ: mọi cặp đỉnh được nối bởi cạnh duy nhất. Bigraph: tập đỉnh trong G chia thành hai tập rời nhau U, V.
Mỗi cạnh chỉ nối giữa điểm trong U với điểm trong V.
Tìm cây bao trùm: theo chiều rộng, theo chiều sâu
24
Cây bao trùm tối tiểu Cây bao trùm nhỏ nhất là cây bao trùm có tổng trọng
Minimum Spanning Tree
Complete Graph
7
2 2
3 5 3
4
số các cạnh nhỏ hơn tất cả các cây bao trùm khác
Thuật giải tìm MST trên đồ thị có hoặc không có trọng
số: Prim, Kruskal, Boruvka. 25
1 1
MST-Thuật giải Prim Tương tự thuật giải Dijkstra, với trọng số cạnh thay
chiều dài đường đi
3.
1. Tạo cây ban đầu với đỉnh bất kz thuộc graph. 2. Thêm cạnh vào cây : chọn cạnh có trọng số nhỏ nhất (chưa có trong cây đang tạo) nối với các đỉnh của cây và thêm vào cây Lặp lại (đến khi mọi đỉnh trong cây)
26
MST-Thuật giải Prim Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative). Initialize: Vnew = {x}, where x is an arbitrary node
(starting point) from V, Enew = {}
Repeat until Vnew = V:
Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)
Add v to Vnew, and {u, v} to Enew
Output: Vnew and Enew describe a minimal spanning
tree 27
MST-Thuật giải Prim
4
4
B
C
4 B C
2
2 1 4 2 1 A 4 E F 1 A 4 E F 1 2 3 D
10 3 D 5 G 10 5 G 3 5 6
3 5 6 4
H
I
I 4
H 3 2 J 3 2 J
28
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
29
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
30
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
31
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
32
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
33
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
34
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
35
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
36
MST-Thuật giải Prim
4
B
C
2
4 4 B C 2 1 4 2 1 A 4 E F 1 A 4 E F 1
D 3 2 10 D 3 5 G 10 5 G 5 6 3
I
4
5 6 3 4
H I
H 3 2 J 3 2 J
37
MST-Thuật giải Prim-Phân tích Running
Time:
𝑂(𝑚 + 𝑛 log 𝑛) (𝑚 =
𝑒𝑑𝑔𝑒𝑠, 𝑛 = 𝑛𝑜𝑑𝑒𝑠)
Nếu không dùng heap, the run time sẽ là 𝑂(𝑛2). Không cần sắp xếp theo trọng số cạnh trước.
Vì xét theo đỉnh không cần xét khả năng tạo chu
trình
38
3.
MST-Thuật giải Krusal 1. Sắp xếp tăng dần theo trọng số cạnh 2. Chọn cạnh có trọng số nhỏ nhất. Kiểm tra nếu không tạo thành chu trình, chọn nó. Ngược lại chọn cạnh khác có Lặp bước 2 đến khi có (𝑉 − 1) cạnh trong cây bao trùm
39
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
40
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
41
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
42
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
Accepting edge (E,G) would create a cycle
3
43
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
44
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
45
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
46
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
47
MST-Thuật giải Krusal
3
F
edge
edge
C
10
dv 4
(B,E)
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
48
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
49
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
50
MST-Thuật giải Krusal
3
F
edge
edge
C
10
(B,E)
dv 4
(D,E)
dv 1
4 3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
8 6 5 4 B
D
(A,H)
5
4 4
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
G
E
(A,B)
8
(C,F)
3
(A,F) 10
(B,C)
4
3
51
MST-Thuật giải Krusal
3
F
edge
edge
C
(B,E)
dv 4
(D,E)
dv 1
3
A
(B,F)
4
(D,G) 2
(B,H)
4
(E,G)
3
5 4 B
D
(A,H)
5
H
(C,D) 3
(D,F)
6
(G,H) 3
1 2
3
E
G
(A,B)
8
(C,F)
3
}
(A,F) 10
(B,C)
4
Done
Total Cost = dv = 21
52
MST-Thuật giải Krusal-Phân tích Running Time = O(m log n) (m = edges, n =
nodes). QuickSort algorithm
Kiểm tra cạnh tạo ra chu trình có thể chậm. Tuy nhiên, sử dụng data structure “union-find” sẽ khắc phục nhược điểm.
Trong một số trường hợp (có đỉnh nối với cạnh dài
nhất với đồ thị) phải kiểm tra mọi cạnh.
53
Thuật giải tham lam-Tóm tắt Giải bài toán tìm cực đại/cực tiểu. Xây dựng công thức tối ưu cục bộ Phần lớn thực hiện bằng cách sắp xếp, sau đó thực
hiện tối ưu ở từng bước.
54
Thuật giải tham lam-Áp dụng giải quyết các bài toán khác Bài toán tìm đường đi ngắn nhất (thuật giải Dijkstra,
A*)
55
![Bài giảng Phân tích thiết kế và đánh giá thuật toán Trường ĐH Hàng Hải [Mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250909/oursky06/135x160/58071768925368.jpg)
![Giáo trình Tin học ứng dụng: Làm chủ nền tảng công nghệ (Module 01) [Chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2026/20260128/cristianoronaldo02/135x160/97961769596282.jpg)
![Giáo trình N8N AI automation [mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2026/20260128/cristianoronaldo02/135x160/1291769594372.jpg)
