Bài giảng Toán rời rạc: Quy hoạch động - Trần Vĩnh Đức

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

56
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Quy hoạch động cung cấp cho người học những nội dung kiến thức như: Đườ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. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Quy hoạch động - Trần Vĩnh Đức

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