Xem mẫu
- Quy hoạch động
Trần Vĩnh Đức
HUST
Ngày 7 tháng 9 năm 2019
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 61
- Tài liệu tham khảo
▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2006.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 61
- Nội dung
Đường đi ngắn nhất trên DAG
Dãy con tăng dài nhất
Khoảng cách soạn thảo
Bài toán cái túi
Nhân nhiều ma trận
Đường đi ngắn nhất
Tập độc lập trên cây
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- At the conclusion of our study of shortest paths (Chapter 4), we observed that the problem is
Đồespecially
thị phi easy chu trình
in directed (DAG):
acyclic Nhắc
graphs (dags). lại
Let’s recapitulate this case, because it lies at
the heart of dynamic programming.
The special distinguishing feature of a dag is that its nodes can be linearized; that is, they
can be arranged on a line so that all edges go from left to right (Figure 6.1). To see why
this helps with
Trong đồ thịshortest paths,trình,
phi chu suppose
tawecówant
thểtosắp
figure outthứ
xếp distances
tự cácfrom nodesao
đỉnh S to the
other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its
cho nó chỉ có cung đi đi từ trái sang phải.
Figure 6.1 A dag and its linearization (topological ordering).
6 3
A B
1 2
2 4 6 1 1
S 4 1 E S C A B D E
2 3 1 1 2
C D
Hình: Đồ thị phi chu trình G và 169
biểu diễn dạng tuyến tính của nó.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 61
- this helps with shortest paths, suppose we want to figure out distances from node S to the
other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its
Đường đi ngắn nhất trên DAG
Figure 6.1 A dag and its linearization (topological ordering).
6 3
A B
1 2
2 4 6 1 1
S 4 1 E S C A B D E
2 3 1 1 2
C D
Hình: Đồ thị phi chu trình G và 169
biểu diễn dạng tuyến tính của nó.
▶ Xét nút D của đồ thị, cách duy nhất để đi từ S đến D là phải
qua B hoặc C.
▶ Vậy, để tìm đường đi ngắn nhất từ S tới D ta chỉ phải so sánh
hai đường:
dist(D) = min{dist(B) + 1, dist(C) + 3}
CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 61
- ness, let’s focus on node D. The only way to get to it is through its
Thuật toán tìm đường đi ngắn nhất cho DAG
linearization (topological ordering).
3
B
2
2 4 6 1 1
1 E S C A B D E
1 1 2
D
Thuật toán
169
Khởi tạo mọi giá trị dist(.) bằng ∞
dist(s) = 0
for each v ∈ V \ {s}, theo thứ tự tuyến tính:
dist(v) = min(u,v)∈E {dist(u) + ℓ(u, v)}
CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 61
- paths, suppose we want to figure out distances from node S to the
ness, let’s focus on node D. The only way to get to it is through its
linearization (topological ordering).
3
B
2
2 4 6 1 1
1 E S C A B D E
1 1 2
D
Bài tập 169
Làm thế nào để tìm đường đi dài nhất trong DAG?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 61
- Ý tưởng quy hoạch động
linearization (topological ordering).
3
B
2
2 4 6 1 1
1 E S C A B D E
1 1 2
D
Hình: Để giải bài toán D ta cần giải bài toán con C và B.
169
▶ Quy hoạch động là kỹ thuật giải bài toán bằng cách xác
định một tập các bài toán con và giải từng bài toán con một,
nhỏ nhất trước,
▶ dùng câu trả lời của bài toán nhỏ để hình dung ra đáp án của
bài toán lớn hơn,
▶ cho tới khi toàn bộ các bài toán được giải.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 61
- Nội dung
Đường đi ngắn nhất trên DAG
Dãy con tăng dài nhất
Khoảng cách soạn thảo
Bài toán cái túi
Nhân nhiều ma trận
Đường đi ngắn nhất
Tập độc lập trên cây
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Bài toán dãy con tăng dài nhất
Cho dãy số a1 , a2 , . . . , an . Một dãy con là một tập con các số lấy
theo thứ tự, nó có dạng
ai1 , ai2 , . . . , aik
ở đó 1 ≤ i1 < i2 < · · · < ik ≤ n, và dãy tăng là dãy mà các phần
tử tăng dần. Nhiệm vụ của bạn là tìm dãy tăng có số phần tử
nhiều nhất.
Ví dụ
Dãy con dài nhất của dãy 5, 2, 8, 6, 3, 6, 9, 7 là:
CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 61
- Bài tập
Hãy tìm dãy con tăng dài nhất của dãy
5, 3, 8, 6, 2, 6, 9, 7.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 61
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 171
DAG của dãy tăng
Figure 6.2 The dag of increasing subsequences.
5 2 8 6 3 6 9 7
Hình: DAG G = (V, E) của dãy 5, 2, 8, 6, 3, 6, 9, 7.
In this example, the arrows denote transitions between consecutive elements of the opti-
mal solution. More generally, to better understand the solution space, let’s create a graph of
all permissible transitions: establish a node i for each element a i , and add directed edges (i, j)
whenever it is possible for ai and aj to be consecutive elements in an increasing subsequence,
that is, whenever i < j and ai < aj (Figure 6.2).
Noticedựng
Ta xây that (1) this graph
DAG G =G (V, = (V,E) is a dag,
E) cho dãysince
a1 ,allaedges (i, j) have i < j, and (2)
2 , . . . , an như sau:
there is a one-to-one correspondence between increasing subsequences and paths in this dag.
Therefore,
▶ V =our {agoal
1 , ais2simply }, the
, . . . , toanfind vàlongest path in the dag!
Here is the algorithm:
▶ có cung (ai , aj ) ∈ E nếu i < j và ai < aj .
for j = 1, 2, . . . , n:
Bài toánL(j)tìm
= 1 dãy
+ max{L(i)tăng: (i,
dài j) ∈nhất
E} được đưa về bài toán tìm đường đi
return maxj L(j)
dài nhất trên DAG.
L(j) is the length of the longest path—the longest increasing subsequence—ending at j (plus
1, since strictly speaking we need
CuuDuongThanCong.com to count nodes on the path, not edges). By reasoning in the
https://fb.com/tailieudientucntt 12 / 61
- Tìm đường đi dài nhất trên DAG
for j = 1, 2, . . . , n:
L(j) = 1 + max{L(i) : (i, j) ∈ E}
return maxj L(j)
▶ L(j) là độ dài của đường đi dài nhất kết thúc tại j.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 61
- gupta, C.H. Papadimitriou, and U.V. Vazirani
Bài tập
e 6.2 The
Hãydag
tìmofđường
increasing
đi dàisubsequences.
nhất trên DAG sau:
5 2 8 6 3 6 9 7
this example, the arrows denote transitions between consecutive elements of th
lution. More generally, to better understand the solution space, let’s create a gr
missible transitions: establish a node i for each element a i , and add directed edge
ver it is possible for ai and ahttps://fb.com/tailieudientucntt
CuuDuongThanCong.com j to be consecutive elements in an increasing subseq
14 / 61
- Tìm đường đi dài nhất
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 171
Figure 6.2 The dag of increasing subsequences.
5 2 8 6 3 6 9 7
In this example, the arrows denote transitions between consecutive elements of the opti-
▶ Làm thế nào tìm được đường đi dài nhất từ các L-giá trị?
mal solution. More generally, to better understand the solution space, let’s create a graph of
all▶permissible transitions: establish a node i for each element a i , and add directed edges (i, j)
Ta quản lý các cạnh trên đường đi bởi con trỏ ngược prev(j)
whenever it is possible for ai and aj to be consecutive elements in an increasing subsequence,
that is, whenever
giống j and aitìm
nhưi
- Ta có nên dùng đệ quy?
Có nên dùng đệ quy để tính công thức sau?
L(j) = 1 + max{L(i) : (i, j) ∈ E}
CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 61
- Nội dung
Đường đi ngắn nhất trên DAG
Dãy con tăng dài nhất
Khoảng cách soạn thảo
Bài toán cái túi
Nhân nhiều ma trận
Đường đi ngắn nhất
Tập độc lập trên cây
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Khoảng cách soạn thảo
▶ Khi chương trình kiểm tra chính tả bắt gặp lỗi chính tả, nó sẽ
tìm trong từ điển một từ gần với từ này nhất.
▶ Ký hiệu thích hợp cho khái niệm gần trong trường hợp này là
gì?
Ví dụ
Khoảng cách giữa hai xâu SNOWY và SUNNY là gì?
S - N O W Y - S N O W - Y
S U N N - Y S U N - - N Y
Chi phí: 3 Chi phí: 5
CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 61
- Khoảng cách soạn thảo
Định nghĩa
Khoảng cách soạn thảo của hai xâu x và y là số tối thiểu phép
toán soạn thảo (xóa, chèn, và thay thế) để biến đổi xâu x thành
xâu y.
Ví dụ
Biến đổi xâu SNOWY thành xâu SUNNY.
S - N O W Y
S U N N - Y
▶ chèn U,
▶ thay thế O → N, và
▶ xóa W.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 61
- Lời giải quy hoạch động
Câu hỏi
Bài toán con là gì?
▶ Để tìm khoảng cách soạn thảo giữa hai xâu x[1 . . . m] và
y[1 . . . n],
▶ ta xem xét khoảng cách soạn thảo giữa hai khúc đầu
x[1 . . . i] và y[1 . . . j].
▶ Ta gọi đây là bài toán con E(i, j).
▶ Ta cần tính E(m, n).
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 61
nguon tai.lieu . vn
