›
›

Giáo trình Toán rời rạc - Bài 20: Quy hoạch động - Trần Vĩnh Đức

Download
Quy hoạch động  
Trần Vĩnh Đức  
HUST  
Ngày 7 tháng 9 năm 2019  
1 / 61  
Tài liệu tham khảo  
▶
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,  
Algorithms, July 18, 2006.  
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  
Đồ thị phi chu trình (DAG): Nhắc lại  
Trong đồ thị phi chu trình, ta có thể sắp xếp thứ tự các đỉnh sao  
cho nó chỉ có cung đi đi từ trái sang phải.  
3
6
3
A
C
B
2
1
1
2
1
2
4
6
1
A
S
B
D
E
1
C
4
S
E
2
1
D
Hình: Đồ thị phi chu trình G và biểu diễn dạng tuyến tính của nó.  
4 / 61  
Đường đi ngắn nhất trên DAG  
3
6
A
C
B
2
1
1
2
1
2
4
6
1
A
S
B
D
E
1
C
4
S
E
2
1
3
D
Hình: Đồ thị phi chu trình G và 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}  
5 / 61  
Thuật toán tìm đường đi ngắn nhất cho DAG  
3
1
2
4
6
1
A
S
B
D
E
C
2
1
Thuật toán  
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)}  
6 / 61  
3
1
2
4
6
1
A
S
B
D
E
C
2
1
Bài tập  
Làm thế nào để tìm đường đi dài nhất trong DAG?  
7 / 61  
Ý tưởng quy hoạch động  
3
1
2
4
6
1
A
S
B
D
E
C
2
1
Hình: Để giải bài toán D ta cần giải bài toán con C và B.  
▶
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.  
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  
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  
ai , ai , . . . , ai  
1
2
k
ở đó 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à:  
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.  
11 / 61  
DAG của dãy tăng  
2
5
8
6
3
6
9
7
Hình: DAG G = (V, E) của dãy 5, 2, 8, 6, 3, 6, 9, 7.  
Ta xây dựng DAG G = (V, E) cho dãy a1, a2, . . . , an như sau:  
▶
V = {a1, a2, . . . , an}, và  
▶
có cung (ai, aj) ∈ E nếu i < j và ai < aj.  
Bài toán tìm dãy tăng dài nhất được đưa về bài toán tìm đường đi  
dài nhất trên DAG.  
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.  
13 / 61  
Bài tập  
Hãy tìm đường đi dài nhất trên DAG sau:  
2
5
8
6
3
6
9
7
14 / 61  
Tìm đường đi dài nhất  
2
5
8
6
3
6
9
7
▶
▶
Làm thế nào tìm được đường đi dài nhất từ các L-giá trị?  
Ta quản lý các cạnh trên đường đi bởi con trỏ ngược prev(j)  
giống như trong tìm đường đi ngắn nhất.  
▶
Dãy tối ưu có thể tìm được theo con trỏ ngược này.  
15 / 61  
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}  
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  
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 U N N - Y  
- S N O W - Y  
S U N - - N Y  
Chi phí: 3  
Chi phí: 5  
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.  
▶
▶
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).  
20 / 61  
Tải về để xem bản đầy đủ
pdf 61 trang Thùy Anh 26/04/2022 4100
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 20: Quy hoạch động - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_toan_roi_rac_bai_20_quy_hoach_dong_tran_vinh_duc.pdf