Giải thuật tham lam: Bài giảng Giải thuật nâng cao

GIẢI THUẬT THAM LAM

TS. NGÔ QUỐC VIỆT 2015

Nội dung 1. Giới thiệu 2. Bài toán cây bao trùm tối thiểu (MST) 3. Huffman coding 4. Phủ tập hợp

Giải thuật nâng cao-Lý thuyết số

2 Giới thiệu

• Thuật giải tham lam xây dựng giải pháp từng bước, trong đó chọn lời bước kế tiếp dựa trên tiêu chí có lợi & hiển nhiên nhất.

• Cách tiếp cận có thể cho lời giải không đúng trong một số trường hợp, nhưng phần lớn đạt được kết quả tối ưu.

• Bài giảng minh họa greedy với: MST, Huffman

coding, phủ tập hợp.

Giải thuật nâng cao-Lý thuyết số

3

Cây bao trùm tối tiểu – Minimum spanning tree

Một số Spanning Trees từ A

Graph A

• 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.

4 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

5 Cây bao trùm tối tiểu

Complete Graph

Minimum Spanning Tree

2 2

5 3 3

• Cây bao trùm nhỏ nhất là cây bao trùm có tổng trọng 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ó

1 1

6

trọng số: Prim, Kruskal, Boruvka.

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

1. Tạo cây ban đầu với đỉnh bất kỳ 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

3. Lặp lại (đến khi mọi đỉnh trong cây)

7 MST-Thuật giải Prim

• Input: đồ thị trọng số không rỗng với tập đỉnh V và

cạnh E (trọng số có thể âm). • Khởi tạo: Vnew = {x}, với x is là node bất kỳ(starting point) từ V, Enew = {} • Lặp đến khi Vnew = V: cạnh

với minimal weight

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ó trọng số nhỏ và không tạo chu trình.

3. Lặp bước 2 đến khi có (𝑉 − 1) cạnh trong cây bao

trùm

20 MST-Thuật giải Krusal

Giải thuật nâng cao-Lý thuyết số

21 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1

4 3

A

(B,F)

(D,G) 2

(B,H)

(E,G)

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3

(D,F)

(G,H) 3

1 2

G

E

(A,B)

(C,F)

(A,F) 10

(B,C)

22 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2

(B,H)

(E,G)

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3

(D,F)

(G,H) 3

1 2

G

E

(A,B)

(C,F)

(A,F) 10

(B,C)

23 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3

(D,F)

(G,H) 3

1 2

G

E

(A,B)

(C,F)

(A,F) 10

(B,C)

24 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3

(D,F)

(G,H) 3

1 2

G

E

(A,B)

(C,F)

(A,F) 10

(B,C)

Accepting edge (E,G) would create a cycle

25 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3

1 2

G

E

(A,B)

(C,F)

(A,F) 10

(B,C)

26 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

(A,F) 10

(B,C)

27 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

3 

(A,F) 10

(B,C)

28 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

3 

(A,F) 10

(B,C)

4 

29 MST-Thuật giải Krusal

F

edge

C

10 dv 4 

(B,E)

(D,E)

dv 1 

4 3

A

(B,F)

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

3 

(A,F) 10

(B,C)

4 

30 MST-Thuật giải Krusal

F

edge

C

10

(B,E)

dv 4 

(D,E)

dv 1 

4 3

A

(B,F)

4 

(D,G) 2 

(B,H)

(E,G)

3 

8 6 5 4 B

D

(A,H)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

3 

(A,F) 10

(B,C)

4 

31 MST-Thuật giải Krusal

F

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)

4 4

H

(C,D) 3 

(D,F)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

3 

(A,F) 10

(B,C)

4 

32 MST-Thuật giải Krusal

F

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)

(G,H) 3 

1 2

G

E

(A,B)

(C,F)

3 

(A,F) 10

(B,C)

4 

33 MST-Thuật giải Krusal

F

edge

C

(B,E)

dv 4 

(D,E)

dv 1 

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)

(G,H) 3 

1 2

E

G

(A,B)

(C,F)

3 

}

(A,F) 10

(B,C)

4 

Done

Total Cost =  dv = 21

34 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.

35 Phủ tập hợp-ví dụ • Một khu quy hoạch (có nhiều khu phố) cần xác định các

vị trí xây trường với hai ràng buộc • Trường phải trong khu phố (town) • Không học sinh/phụ huynh nào phải đi qua xa (vd: 10km) từ

nhà đến trường

Các khu phố

Khu phố trong phạm vi 10km

• Câu hỏi: cần xây tối thiểu bao nhiêu trường? • Yêu cầu trên có thể giải thông qua khái niệm phủ tập

hợp.

Giải thuật nâng cao-Lý thuyết số

36 Phủ tập hợp-định nghĩa

• Cho tập phổ biến 𝑈 = 𝑢1, 𝑢2, … , 𝑢𝑛 • Gọi 𝑆1, 𝑆2, … , 𝑆𝑘 ⊆ 𝑈 là các tập con có các trọng số tương ứng 𝑐1, 𝑐2, … , 𝑐𝑛

và 𝑆𝑖

𝑖 = 𝑈.

• Mục tiêu: cần tìm 𝐼 = 1,2, … , 𝑚 sao cho cực tiểu 𝑐𝑖 𝑖 • Hỏi: U, Si, ci trong bài toán xây các trường?

• 𝑈 ={các town trong khu quy hoạch} • Với mỗi khu phố x, Sx là tập các town trong phạm vi 10km.

Trường tại x sẽ phủ các town này

• cx=1, x ?

Giải thuật nâng cao-Lý thuyết số

37 Phủ tập hợp-giải thuật greedy • Chọn Si chứa nhiều town nhất chưa được phủ • Lặp lại cho đến khi các Si được chọn phủ U.

• Ví dụ xây trường

• Chọn Sa, Sa chứa a, b, d, e, k, i, h. • Chọn Sf hoặc Sg, vì chứa f, g. • Chọn Sc và Sj chứa chính nó. • 𝑐𝑖

𝑖 = 4.

• Nhận xét: có thể chọn giải pháp tốt hơn? • Xây trường tại b, e, và i là giải pháp tốt hơn

Giải thuật nâng cao-Lý thuyết số

38 Phủ tập hợp-giải thuật greedy

1. 𝐶 = *+ 2. While 𝐶 ≠ 𝑈

Tìm tập S có cost nhỏ nhất

Đặt 𝛼 =

𝑐(𝑆) 𝑆−𝐶

Với mỗi 𝑒 ∈ 𝑆\C, đặt 𝑝𝑟𝑖𝑐𝑒(𝑒) = 𝛼 𝐶 = 𝐶 ∪ 𝑆

3. Ouput C

Giải thuật nâng cao-Lý thuyết số

39 Phủ tập hợp-giải thuật greedy-ví dụ

• Cho 𝑈 = *1,2,3,4,5+, 𝐶𝑜𝑠𝑡(𝑆1) = 5, 𝑆2 = *2,5+, *1,4,3,2+,

𝑆 = *𝑆1, 𝑆2, 𝑆3+, 𝑆1 = *4,1,3+, 𝐶𝑜𝑠𝑡(𝑆2) = 10, 𝑆3 = 𝐶𝑜𝑠𝑡(𝑆3) = 3. Minh họa với Greedy lặp 1: 𝑆1 = 𝐶𝑜𝑠𝑡(𝑆1)/|𝑆1 – 𝐶| = 5/3; 𝑆2 =

• Lần 𝐶𝑜𝑠𝑡(𝑆2)/|𝑆2 – 𝐶| = 10/2; 𝑆3 = 𝐶𝑜𝑠𝑡(𝑆3)/ |𝑆3 – 𝐶| = ¾  chọn S3. • Lần lặp 2: S1 = Cost(S1)/|S1 – C| = 5/0; S2 = Cost(S2)/|S2 – C| = 10/1  chọn S2.

• Trường hợp này greedy có nghiệm tối ưu

Giải thuật nâng cao-Lý thuyết số

40 Phủ tập hợp-giải thuật greedy-ví dụ

• 𝑈 = *1,2,3,4,5,6,7,8,9,10,11,12,13+; S1 = {1, 2} S2 = {2, 3, 4, 5} S3 = {6, 7, 8, 9, 10, 11, 12, 13} S4 = {1, 3, 5, 7, 9, 11, 13} S5 = {2, 4, 6, 8, 10, 12, 13}. Giả sử cost của các subset là giống nhau • Kết quả của greedy algorithm là C= {S3, S2, S1}, so với nghiệm tối ưu {S4, S5}.

Giải thuật nâng cao-Lý thuyết số

41 Phủ tập hợp-giải thuật greedy-ví dụ

IBM finds computer viruses (wikipedia)

• Elements: 5000 virus máy tính • Sets: 9000 substring, mỗi substring khoảng 20++ bytes thể hiện virus.

• Xác định phủ tập hợp khoảng 180 substrings phủ

toàn bộ U.

Chỉ cần search trong 180 substring để xác định có

virus hay không?

Giải thuật nâng cao-Lý thuyết số

42 SC là bài toán NP-complete

•

Định lý: Set Cover (SC) là NP-complete Chứng minh:

INSTANCE: Given a universe U of n elements, a collection of subsets of U, S = {S1, …, Sm}, and a positive integer b

, |C| ≤ b,

QUESTION: Is there a such that

(Note: The subcollection {Si | } satisfying the above condition is called a set cover of U

Giải thuật nâng cao-Lý thuyết số

43 SC là bài toán NP-complete (tt) • Cần chứng minh SC thuộc NP. Cho subcollection C, dễ dàng kiểm chứng rằng nếu |C| ≤ b và union của các tập trong C chứa mọi phần tử của U.

• Để chứng minh định lý, cần phải chứng minh Vertex Cover (VC) ≤p Set Cover (SC)

Cho instance C của VC (undirected graph G=(V,E) và số nguyên dương j), chúng ta cần xây dựng C’ của SC trong thời gian đa thức sao cho C là satisfiable iff C’ là satisfiable.

Giải thuật nâng cao-Lý thuyết số

44 SC là bài toán NP-complete (tt)

• Construction: Đặt U = E. Định nghĩa n phần tử của U và tập S như sau:

• Đánh nhãn mọi đỉnh trong V từ 1 đến n. Đặt Si là tập các cạnh nối với đỉnh i. Sau đó, đặt b = j. Cách xây dựng này là poly-time ứng với size của VC instance

• Chú ý: mỗi cạnh ứng với mỗi phần tử trong U và mỗi đỉnh ứng với and một set trong S.

Giải thuật nâng cao-Lý thuyết số

45 VERTEX-COVER p SET-COVER

one element for every edge

VC VC

one set for every vertex, containing the edges it covers

Giải thuật nâng cao-Lý thuyết số

46 SC là bài toán NP-complete (tt) • Cần chứng minh C là satisfiable iff C’ là satisfiable. • Nghĩa là, cần chứng minh nếu original instance của VC là YES instance iff constructed instance of SC là YES instance.

• (→) • Giả sử G có phủ đỉnh C kích thước tối đa là j. Theo cách xây dựng trên, C ứng với collection C’ của các subsets của U. Vì b = j, |C’| ≤ b. C’ phủ mọi elements trong U vì C “phủ ” mọi cạnh trong G. Để thấy điều này, xét bất kỳ phần tử nào của U. Sao cho một phần tử là cạnh trong G. Vì C là set cover, có ít nhất một endpoint của cạnh này thuộc C.

Giải thuật nâng cao-Lý thuyết số

47 SC là bài toán NP-complete (tt)

• (←) • Giả sử có set cover C’ kích thước tối đa b trong constructed instance. Vì mỗi tập trong in C’ được kết hợp với đỉnh trong G, đặt C là tập các đỉnh này. Thì |C| = |C’| ≤ b = j. C là vertex cover của G vì C’ là set cover.

• Để thấy điều này, xét cạnh bất kỳ e. Vì e thuộc U, nên C’ phải chứa ít nhất một tập set có chứa e. Theo cách xây dựng trên, chỉ một tập hợp chứa e ứng với các là các endpoint của e. Vậy C phải chứa ít nhất một endpoint của e.

Giải thuật nâng cao-Lý thuyết số

48 Giải pháp

Algorithm 1: (trường hợp uniform cost) 1. C = empty 2. while U is not empty

pick a set Si such that Si covers the most elements in U remove the new covered elements from U C = C union Si

5. 6. return C

Giải thuật nâng cao-Lý thuyết số

49 Solutions • Trường hợp non-uniform cost • Phương pháp tương tự. Tại mỗi bước lặp, thay vì chọn tập Si sao cho Si phủ nhiều nhất các phần tử chưa được phủ, thì chọn tập Si có cost-effectiveness α nhỏ nhất, với α được định nghĩa :

𝛼 =

𝑐 𝑆𝑖 𝐴𝑖 ∩ 𝑈

• Câu hỏi: tại sao chọn smallest α? Tạy sao định nghĩa α

như trên

Giải thuật nâng cao-Lý thuyết số

50 Solutions

Algorithm 2: (trường hợp non-uniform cost) 1. C = empty 2. while U is not empty

pick a set Si such that Si has the smallest α for each new covered elements e in U set price(e) = α remove the new covered elements from U C = C union Si