Xem mẫu
- Thuật toán tham lam
Trần Vĩnh Đức
HUST
Ngày 1 tháng 9 năm 2019
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 64
- Tài liệu tham khảo
I S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2006.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 64
- Nội dung
Cây bao trùm nhỏ nhất
Mã hóa Huffman
Công thức Horn
Phủ các tập
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- ted edges are potential links, and the goal is to pick enough of the
Bài toán
nodes are connected. But this is not all; each link also has a main
flected in that edge’s weight. What is the cheapest possible networ
1
A C E
4 4
3
4 2 5
B 4 D 6 F
mediateIobservation is that the optimal set of edges cannot contain
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
e removingmáy.
an edge from this cycle would reduce the cost without
connectivity:
I Cần chọn một số kết nối để mạng liên thông;
I 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í
y1 Removing a cycle edge cannot disconnect a graph.
(tiền bảo trì).
solutionImust Mạngbe
vớiconnected
chi phí nhỏ nhất and làacyclic:
gì? undirected graphs of this
rees. The particular tree
CuuDuongThanCong.com we want is the one with minimum tota
https://fb.com/tailieudientucntt 4 / 64
- nodes are connected. But this is not all; each link also has a main
flected in that edge’s weight. What is the cheapest possible networ
1
A C E
4 4
3
4 2 5
B 4 D 6 F
mediate observation is that the optimal set of edges cannot contain
Tính chất
e removing ancạnh
Xóa một edge from
trên this cycle
chu trình would
không làm mất reduce
tính liên the cost
thông củawithout
đồ
connectivity:
thị.
y 1 Vậy,
Removing
mạng vớiachi
cycle
phí edge cannot
nhỏ nhất disconnect
phải là một cây. a graph.
solution must be connected and acyclic: undirected graphs of this
rees. The particular tree we want is the one with minimum tota
as the minimum spanning
CuuDuongThanCong.com tree. Here is its formal definition. 5 / 64
https://fb.com/tailieudientucntt
- 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ố we .
I Output: Một cây T = (V, E′ ) với E′ ⊆ E, với tổng trọng số
∑
weight(T) = we
e∈E′
là nhỏ nhất.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 64
- um spanning trees Input: An undirected graph G = (V, E ); edge weights we .
Tìm tocây
e asked bao atrùm
network collection of computers by linking selected
Output: A tree T = (V, E ′ ), with E ′ ⊆ E , that minimizes
his translates into a graph problem in which nodes are computers, !
s are potential links, and the goal is to pick enough of weight(T)
these edges
= we .
are connected. But this is not all; each link also has a maintenance e∈E ′
n that edge’s weight. WhatInisthe
thepreceding
cheapestexample,
possiblethe
network?
minimum spanning tree has a cost of
1 1
A C E A C E
4 4
3 4 2 5
4 2 5
B D F B 4 D F
4 6
However,
observation is that the optimal set this is notcannot
of edges the onlycontain
optimalasolution.
cycle, Can you spot anothe
ng an edge from this cycle would reduce the cost without compro-
vity: Đây có phải lời giải5.1.1 A greedy approach
tối ưu không?
Kruskal’s minimum spanning tree algorithm starts with the empty g
selects
moving a cycle edge cannot edges from
disconnect E according to the following rule.
a graph.
Repeatedly add the next lightest edge that doesn’t produce a cycl
must be connected and acyclic: undirected graphs of this kind are
e particular tree we wantInisother
the onewords, it constructs
with minimumthe treeweight,
total edge by edge and, apart from
avoid
inimum spanning tree. Here is cycles, simply
its formal picks whichever edge is cheapest at the moment.
definition.
CuuDuongThanCong.com
algorithm: every decision it makes is the one with the most obvi
https://fb.com/tailieudientucntt 7 / 64
- dges are potential links, and the goal is to pick enough o
esThuật toán Kruskal
are connected. But this is not all; each link also has a
d in that edge’s weight. What is the cheapest possible ne
1
A C E
4 4
3
4 2 5
B 4 D 6 F
ate observation is that the optimal set of edges cannot co
ovingBắtanđầuedge
với đồ thị rỗng và chọn cạnh từ E theo quy tắc sau.
from this cycle would reduce the cost wit
Lặp lại việc thêm cạnh nhỏ nhất mà không tạo thành
ectivity: chu trình.
Removing a cycle edge
CuuDuongThanCong.com cannot disconnect a graph.
https://fb.com/tailieudientucntt 8 / 64
- Ví dụ: Thuật toán Kruskal
1
7
8
5 2 3
7
9 5
15
4 5
6 9
8
11
6 7
Hình: Nguồn: tikz examples
CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 64
- Nhát
130 cắt 5.1
FigureĐịnh
5.2 nghĩa
T ∪ {e}. The addition of e (dotted) to T (solid lines) produces a
cycle. Xét
Thisđồcycle
thị must contain
G = (V, at least
E). Một nhátone
cắtother edge,
là một shown
cách chia here as e′ , across
tập đỉnh
the cutthành
(S, Vhai
− S).
nhóm: S và V − S.
S V −S
e
e
Hình: Nhát cắt và các cạnh nối giữa hai phân hoạch.
The correctness of Kruskal’s method follows from a certain cut property, which
is general enough to also justify a whole slew of other minimum spanning tree
algorithms.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 64
- B 1 D
Tính chất Cắt
Giả sử các cạnh X là một(b) phần của mộtA MST Algorithms
nào C 131 E
đó của
G = (V, E). Chọn một tập đỉnh bất kỳ S sao cho không có cạnh
property
nào at
củawork.
X nối(a)
giữa và VEdges
− S, vàX:
AnS undirected graph.
xét e là(b) SetcóX trọng
cạnh has số nhỏ
art of the MST T on the right. (c) If S = {A,
nhất nối hai phân hoạch này. Khi đó, X ∪ {e}
B B, C , D},Dthen
là một phần củaFmột
weightMSTedgesnàoacross
đó. the cut (S, V − S) is e = {D, E }. X ∪ {e}
own on the right.
1
(c)
3 A C E
A C E
2 2 The
1 cut:
e
2 3
B D F
B 1 D 4 F
S V −S
C E A C E
MST T :
CuuDuongThanCong.com ′
https://fb.com/tailieudientucntt 11 / 64
- C E A C E
Ví dụ A C E
MST T: A C E
Edges X: MST T :
D F B D F
B D F B D F
C A E A
C E AC CE E
The cut: e e
MST T : MST T :
B F D F
D B DF F
B D
S V −S
V −S
Nhát cắt S và V − S và một cây bao trùm nhỏ nhất.
e and e′ cross between S and V − S, and e is specifically the lightest edge
′ ′
ype.
ween Therefore
S and V w(e)
−≤ and),′eand
S,w(e is weight(T ) ≤ weight(T).
specifically Since
the lightest T isofan MS
edge
′
ust be the case
′ that weight(T )′ = weight(T) and that T is also an MST.
e) ≤ w(e ), and weight(T ) ≤ weight(T). Since T is an MST,
re 5.3 shows ′an
tCuuDuongThanCong.com
weight(T ) =example ofhttps://fb.com/tailieudientucntt
weight(T) theand cut property.
that T ′ is Which
also edge is e′ ?
an MST. 12 / 64
- Chứng
Figure 5.2minh Tính
T ∪ {e}. The chất Cắt
addition of e (dotted) to T (solid lines) produces a
cycle. This cycle must contain at least one other edge, shown here as e′ , across
the cut (S, V − S).
S V −S
e
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
The correctness
T thì Tính of Kruskal’s
chất method follows from a certain cut property, which
Cắt đúng.
is general enough to also justify a whole slew of other minimum spanning tree
algorithms.
5.1.2 The cut property
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 64
- Figure 5.2 T ∪ {e}. The addition of e (dotted) to T (solid lines) produces a
Chứng
cycle. This minh Tính
cycle must chấtatCắt
contain least (2)
one other edge, shown here as e′ , across
the cut (S, V − S).
S V −S
e
e
I Giả sử e không thuộc MST T. Xét T ∪ {e}.
The correctness of Kruskal’s method follows from a certain cut property, which
I Việc thêm cạnh e vào T sẽ tạo ra một chu trình.
is general enough to also justify a whole slew of other minimum spanning tree
I Chu trình này chứa ít nhất một cạnh e′ khác đi qua nhát cắt.
algorithms.
5.1.2 The cut property
Say that in the process of building
CuuDuongThanCong.com a minimum spanning tree (MST), we have already
https://fb.com/tailieudientucntt 14 / 64
- cycle. This cycle must contain at least one other edge, shown here as e′ , across
Chứng
the cut (S, minh
V − S).Tính chất Cắt (3)
S V −S
e
e
I Xét đồ thị T′ = (T ∪ {e}) − {e′ }.
The correctness of Kruskal’s method follows from a certain cut property, which
I T′ là một cây. Tại sao?
is general enough to also justify a whole slew of other minimum spanning tree
algorithms.
G = (V, E) là một cây nếu và chỉ nếu G liên thông và
5.1.2 The cut property
|E| = |V| − 1;
Say that in the process of building a minimum spanning tree (MST), we have already
chosen some edges and are https://fb.com/tailieudientucntt
CuuDuongThanCong.com so far on the right track. Which edge should we
15 /add
64
- cycle. This cycle must contain at least one other edge, shown here as e′ , across
Chứng
the cut (S, minh
V − S).Tính chất Cắt (3)
S V −S
e
e
I Xét đồ thị T′ = T ∪ {e} − {e′ }.
The correctness of Kruskal’s method follows from a certain cut property, which
I T′ là một cây.
is general enough to also justify a whole slew of other minimum spanning tree
I Cây T′ cũng là cây bao trùm nhỏ nhất vì:
algorithms.
′
5.1.2 The weight(T ) = weight(T) + w(e) − w(e′ ) và w(e) ≤ w(e′ ).
cut property
Say that in the process of building a minimum spanning tree (MST), we have already
chosen some edges and are https://fb.com/tailieudientucntt
CuuDuongThanCong.com so far on the right track. Which edge should we
16 /add
64
- uppose you are asked to network a collection of computers by linking select
Tính
airs đúng
of them. đắn
This của Thuật
translates toánproblem
into a graph Kruskal?in which nodes are computer
ndirected edges are potential links, and the goal is to pick enough of these edg
hat the nodes are connected. But this is not all; each link also has a maintenan
ost, reflected in that edge’s weight. What is the cheapest possible network?
1
A C E
4 4
3
4 2 5
B 4 D 6 F
One immediate observation is that the optimal set of edges cannot contain a cyc
ecause removing an edge from this cycle would reduce the cost without compr
Bắt đầu với đồ thị rỗng và chọn cạnh từ E theo quy tắc sau.
mising connectivity:
Lặp lại việc thêm cạnh nhỏ nhất mà không tạo thành
Property 1 chu
Removing
trình. a cycle edge cannot disconnect a graph.
o the solution must be connected and acyclic: undirected graphs of this kind a
alled trees. The particular tree we want is the one with minimum total weigh
nown as the minimum spanning
CuuDuongThanCong.com
tree. Here is its formal definition.
https://fb.com/tailieudientucntt 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.
I find(x): x thuộc tập nào?
I union(x, y): hợp hai tập chứa x và y.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 we
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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 64
- Cấu trúc dữ liệu Disjoint sets
I Lưu trữ tập dùng cây có hướng.
I Các nút là các phần tử của tập.
I Mỗi nút x có một con trỏ tới nút cha π(x) của nó.
I 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.
I Cha của gốc là chính nó.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 64
nguon tai.lieu . vn
