DATA STRUCTURE AND ALGORITHM Dynamic Programming
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Qui hoạch động
Dr. Dao Nam Anh
1
Data Structure and Algorithm
Resource - Reference
Slides adapted from James B D Joshi, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne,
“Algorithms” Princeton University, 2011, Addison Wesley
• Algorithm in C (Parts 1-5 Bundle)- Third Edition
by Robert Sedgewick, Addison-Wesley
• Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học
Sư Phạm, 2002
2
Data Structure and Algorithm
Divide and Conquer Chia và Trị
• Một số chương trình đệ qui gọi chính nó cho hai
Chia vấn đề này thành 2 phần và thực hiện từng
phần • Chi phí thời gian: TN = Tk + TN-k + 1
• Many recursive programs use recursive calls on two subsets of inputs
(two halves usually)
Divide the problem and solve them – divide and conquer paradigm
Complexity: TN = Tk + TN-k + 1
3
tập dữ liệu có kích thước ½
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
2 3 1 7
Item max(Item a[], int l, int r) { Item u, v;
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
4
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2 3 1 7
2
Item max(Item a[], int l, int r) { Item u, v;
2 3 1 7
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
5
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2 3 1 7
2
Item max(Item a[], int l, int r) { Item u, v;
3
1 7 2 3
2 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
6
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2 3 1 7
2
Item max(Item a[], int l, int r) { Item u, v;
3
4 2
1 7 2 3
2 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
7
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2 3 1 7
2
Item max(Item a[], int l, int r) { Item u, v;
3
5
4 2
1 7 2 3
2 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
8
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2 3 1 7
2
Item max(Item a[], int l, int r) { Item u, v;
3
6
5
4 2
3
1 7 2 3
2 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
9
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2
3
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 7
3
6
5
4 2
3
2 3 1 7
2 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
10
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2
3
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 8 7
3
6
5
4 2
3
2 3 1 7
2 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
11
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2
3
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 8 7
3
6
9
5
4 2
3
2 3 1 7
1 3 2 7
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
12
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2
3
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 8 7
3
6
9
5
4 2
10 1
3
2 3 1 7
2 7 1 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
13
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
2
3
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 8 7
3
6
12
9
5
11
4 2
10 1
7
3
2 3 1 7
2 7 1 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
14
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
1
13
2
3
7
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 8 7
3
6
12
9
5
11
4 2
10 1
7
3
2 3 1 7
2 7 1 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
15
}
Data Structure and Algorithm
Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị
7
1
1
13
2
3
7
Item max(Item a[], int l, int r) { Item u, v; 2 3 1 7 8 7
3
6
12
9
5
11
4 2
10 1
7
3
2 3 1 7
2 7 1 3
int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v;
16
}
Data Structure and Algorithm
Dynamic programming Qui hoạch động
• Các thuật toán đệ quy có ưu điểm dễ cài đặt, tuy nhiên do bản chất của quá trình đệ quy, các chương trình này thường kéo theo những đòi hỏi lớn về không gian bộ nhớ và một khối lượng tính toán khổng lồ.
• Quy hoạch động (Dynamic programming) là
một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu trữ toàn bộ hay một phần kết quả tính toán tại mỗi bước với mục đích sử dụng lại.
17
Data Structure and Algorithm
Dynamic programming Qui hoạch động
• Bản chất của quy hoạch động là thay thế mô hình tính toán “từ trên xuống” (Top-down) bằng mô hình tính toán “từ dưới lên” (Bottom-up).
• Từ “programming” ở đây không liên quan gì tới việc lập trình cho máy tính, đó là một thuật ngữ mà các nhà toán học hay dùng để chỉ ra các bước chung trong việc giải quyết một dạng bài toán hay một lớp các vấn đề.
• Không có một thuật toán tổng quát để giải tất cả các
bài toán quy hoạch động.
18
Data Structure and Algorithm
Dynamic programming Qui hoạch động
• Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
• Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất ( bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).
19
Data Structure and Algorithm
Dynamic programming Knapsack problem - Bài toán Cái túi
• Trong siêu thị có n gói hàng, các gói hàng có
trọng lượng khác nhau W[i], có giá trị khác nhau V[i]. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M.
• Hỏi tên trộm sẽ lấy đi những gói hàng nào để
• Knapsack problem
Given
» N types of items of varying size and value » One knapsack (belongs to a thief!)
20
được tổng giá trị lớn nhất.
Data Structure and Algorithm
Find: the combination of items that maximize the total value
Dynamic programming Knapsack problem - Bài toán Cái túi
Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …, i} với giới hạn trọng lượng j.
Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M].
21
Data Structure and Algorithm
Dynamic programming Knapsack problem - Bài toán Cái túi
Với giới hạn trọng lượng j, việc chọn tối ưu
trong số các gói {1, 2, …, i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng:
a. Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng là j. Tức là
F[i, j] = F[i - 1, j]
22
Data Structure and Algorithm
Dynamic programming Knapsack problem - Bài toán Cái túi
b. Nếu có chọn gói thứ i (chỉ xét tới trường hợp này khi mà W[i] ≤ j) thì F[i, j] bằng giá trị gói thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng j - W[i]. Tức là về mặt giá trị thu được:
F[i, j] = V[i] + F[i - 1, j - W[i]]
Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max trong 2 giá trị thu được ở trên.
23
Data Structure and Algorithm
Dynamic programming Knapsack problem - Bài toán Cái túi
Knapsack size: 17
int knap(int cap) { int i, space, max, t;
for (i = 0, max = 0; i < N; i++)
0 1 2 3 4
if ((space = cap - items[i].size) >= 0)
A B C D E
Item
if ((t = knap(space) + items[i].val) > max) max = t;
3 4 7 8 9
Size
return max;
}
4 5 10 11 13
Val
int knap(int M) { int i, space, max, maxi, t;
if (maxKnown[M] != unknown) return maxKnown[M]; for (i = 0, max = 0; i < N; i++)
if ((space = M-items[i].size) >= 0)
if ((t = knap(space) + items[i].val) > max) { max = t; maxi = i; }
maxKnown[M] = max; itemKnown[M] = items[maxi];
return max; }
24
Data Structure and Algorithm
Discussion – Câu hỏi
• https://sites.google.com/site/daonamanhedu/data-
25
structure-algorithm
