Giáo trình Toán rời rạc - Bài 19: Thuật toán tham lam

Thuật toán tham lam

Trần Vĩnh Đức

HUST

Ngày 1 tháng 9 năm 2019

1 / 64

Tài liệu tham khảo

I

S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,

Algorithms, July 18, 2006.

2 / 64

Nội dung

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

Mã hóa Huﬀman

Công thức Horn

Phủ các tập

Bài toán

1

4

A

B

C

E

4

6

4

3

5

4

2

F

D

I

Bạn cần xây dựng mạng máy tính bằng cách kết nối từng cặp

máy.

I

Cần chọn một số kết nối để mạng liên thông;

nhưng không phải tất cả các cặp: Mỗi kết nối tốn một chi phí

(tiền bảo trì).

I

Mạng với chi phí nhỏ nhất là gì?

4 / 64

1

4

A

B

C

E

4

6

4

3

5

4

2

F

D

Tính chất

Xóa một cạnh trên chu trình không làm mất tính liên thông của đồ

thị.

Vậy, mạng với chi phí nhỏ nhất phải là một cây.

5 / 64

Bài toán Cây bao trùm nhỏ nhất (Minimal Spaning Tree)

I

Input: Đồ thị vô hướng G = (V, E); mỗi cạnh có trọng số w_e.

Output: Một cây T = (V, E^′) với E^′⊆ E, với tổng trọng số

∑

weight(T) =

w_e

e∈E^′

là nhỏ nhất.

6 / 64

Tìm cây bao trùm

1

4

A

B

A

C

E

C

E

4

6

4

3

5

2

5

4

2

F

D

F

B

D

4

Đây có phải lời giải tối ưu không?

7 / 64

Thuật toán Kruskal

1

4

A

C

E

4

6

4

3

4

5

2

F

B

D

Bắt đầu với đồ thị rỗng và chọn cạnh từ E theo quy tắc sau.

Lặp lại việc thêm cạnh nhỏ nhất mà không tạo thành

chu trình.

8 / 64

Ví dụ: Thuật toán Kruskal

1

7

8

5

2

3

7

8

9

5

9

15

4

5

6

11

6

7

Hình: Nguồn: tikz examples

9 / 64

Nhát cắt

Định nghĩa

Xét đồ thị G = (V, E). Một nhát cắt là một cách chia tập đỉnh

thành hai nhóm: S và V − S.

S

V − S

e

Hình: Nhát cắt và các cạnh nối giữa hai phân hoạch.

10 / 64

Tính chất Cắt

Giả sử các cạnh X là một phần của một MST nào đó của

G = (V, E). Chọn một tập đỉnh bất kỳ S sao cho không có cạnh

nào của X nối giữa S và V − S, và xét e là cạnh có trọng số nhỏ

nhất nối hai phân hoạch này. Khi đó, X ∪ {e} là một phần của một

MST nào đó.

A

B

1

3

C

D

E

A

C

E

e

2

1

2

3

2

F

B

D

1

4

V − S

S

11 / 64

Ví dụ

A

B

C

D

E

A

B

C

D

E

F

e

F

V − S

S

Nhát cắt S và V − S và một cây bao trùm nhỏ nhất.

12 / 64

Chứng minh Tính chất Cắt

S

V − S

e

Xét X là một phần của MST T; nếu cạnh e cũng là một phần của

T thì Tính chất Cắt đúng.

13 / 64

Chứng minh Tính chất Cắt (2)

S

V − S

e

I

Giả sử e không thuộc MST T. Xét T ∪ {e}.

Việc thêm cạnh e vào T sẽ tạo ra một chu trình.

Chu trình này chứa ít nhất một cạnh e^′khác đi qua nhát cắt.

14 / 64

Chứng minh Tính chất Cắt (3)

S

V − S

e

Xét đồ thị T^′= (T ∪ {e}) − {e^′}.

I

T^′là một cây. Tại sao?

G = (V, E) là một cây nếu và chỉ nếu G liên thông và

|E| = |V| − 1;

15 / 64

Chứng minh Tính chất Cắt (3)

S

V − S

e

Xét đồ thị T^′= T ∪ {e} − {e^′}.

I

T^′là một cây.

Cây T^′cũng là cây bao trùm nhỏ nhất vì:

weight(T^′) = weight(T) + w(e) − w(e^′) và w(e) ≤ w(e^′).

16 / 64

Tính đúng đắn của Thuật toán Kruskal?

1

A

B

C

E

4

6

4

3

5

4

2

F

D

4

Bắt đầu với đồ thị rỗng và chọn cạnh từ E theo quy tắc sau.

Lặp lại việc thêm cạnh nhỏ nhất mà không tạo thành

chu trình.

17 / 64

Cài đặt thuật toán Kruskal

Sử dụng cấu trúc dữ liệu disjoint sets: mỗi tập là một thành phần

liên thông.

Disjoint sets có ba phép toán:

I

makeset(x): tạo ra một tập chỉ chứa phần tử x.

find(x): x thuộc tập nào?

union(x, y): hợp hai tập chứa x và y.

18 / 64

procedure kruskal(G, w)

Input: đồ thị liên thông vô hướng G = (V, E);

với trọng số cạnh w_e

Output: MST định nghĩa bởi tập cạnh X.

for all u ∈ V:

makeset(u)

X = ∅

Sắp xếp các cạnh e theo trọng số

for all {u, v} ∈ E, lấy không giảm theo trọng số:

if find(u) = find(v):

̸

thêm cạnh {u, v} vào X

union(u, v)

19 / 64

Cấu trúc dữ liệu Disjoint sets

I

Lưu trữ tập dùng cây có hướng.

Các nút là các phần tử của tập.

Mỗi nút x có một con trỏ tới nút cha π(x) của nó.

Ngoài ra mỗi nút có một rank để lưu trữ độ cao của cây con

từ nút này.

I

Phần tử ở gốc là đại diện, hoặc là tên, của tập.

Cha của gốc là chính nó.

20 / 64

Giáo trình Toán rời rạc - Bài 19: Thuật toán tham lam - Trần Vĩnh Đức