Bài giảng Cơ sở lập trình nâng cao - Chương 8: Phương pháp thiết kế thuật toán Quy hoạch động - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − QUY HOẠCH ĐỘNG − 
Chương 8 
Nội dung 
Giới thiệu 
Quy hoạch động và Chia để trị 
Quy hoạch động và Bài toán tối ưu 
Nguyên lý tối ưu của Bellman 
Sơ đồ cài đặt 
Các ví dụ 
Hình ảnh 
Giới thiệu 
Quy hoạch động – Dynamic Programming do nhà toán học người Mĩ Richard Bellman (1920 – 1984) phát minh vào năm 1957 
Quy hoạch động – Dynamic Programming là phương pháp để giải quyết một lớp lớn các bài toán tối ưu thỏa theo nguyên lý tối ưu Bellman 
Giới thiệu 
Dựa trên phương pháp Quy hoạch động, nhiều thuật toán nổi tiếng đã ra đời: Một số thuật toán nổi tiếng dựa trên phương pháp Quy hoạch động 
Thuật toán Dijkstra 
Thuật toán Ford – Bellman 
Thuật toán Floyd 
Thuật toán Viterbi 
Thuật toán huấn luyện Adaptive Critic 
Thuật toán Cocke – Younger – Kasami 
Quy hoạch động và Chia để trị 
Bài toán con trùng lắp(Overlapping subproblems) 
Phương pháp 
Phương pháp Quy hoạch động gần giống với phương pháp Chia để trị. 
Cả hai phương pháp dùng để giải quyết bài toán bằng cách kết hợp các lời giải của các bài toán con. 
Phương pháp 
Phương pháp Chia để trị: Là phương pháp từ trên xuống dưới (top – down) với ý tưởng: 
[Divide] Chia bài toán lớn thành những bài toán nhỏ hơn và độc lập nhau 
[Solve] Giải quyết các bài toán nhỏ 
[Combine] Kết hợp các lời giải bài toán nhỏ để hình thành lời giải bài toán lớn 
Phương pháp 
Hạn chế của phương pháp Chia để trị: 
Khi dùng phương pháp chia để trị để chia 1 bài toán lớn thành các bài toán con, các bài toán con lại chia nhỏ thành nhiều bài toán con nhỏ hơn nữa,  	 Đôi khi một bài toán con được yêu cầu giải nhiều lần 	 Chương trình chạy chậm 
Phương pháp 
Phương pháp Quy hoạch động: Là phương pháp giải quyết bài toán bằng cách: 
[Solve & Restore] Giải quyết các bài toán nhỏ nhất, rồi lưu kết quả lại 
[Combine & Restore] Kết hợp các lời giải của bài toán nhỏ để hình thành lời giải của bài toán lớn, rồi lưu kết quả lại 
2 Tiếp cận cài đặt Quy hoạch động 
Tiếp cận từ Dưới lên (Bottom Up): 
Toàn bộ các bài toán con nhỏ nhất cần giải sẽ được giải trước 
Sử dụng các kết quả để tìm nghiệm của bài toán lớn hơn 
Quá trình tiếp tục cho đến khi bài toán cuối được giải 
2 Tiếp cận cài đặt Quy hoạch động 
Sơ đồ cài đặt 
void SolveSmallProblems(){} void SolveSubProblems(){} void Trace(){} void DynamicProgramming(){	SolveSmallProvlems();	SolveSubProblems();	//Trace();	} 
2 Tiếp cận cài đặt Quy hoạch động 
Ưu điểm của tiếp cận Bottom – Up 
Tốn ít bộ nhớ 
Khuyết điểm của tiếp cận Bottom – Up 
Cài đặt dài hơn tiếp cận Top – Down 
Vì để tiết kiệm bộ nhớ nên bài toán con nào dùng xong mà không dùng nữa thì bỏ đi Sau khi giải xong sẽ không xem được trình tự quá trình giải (không lưu lại lịch sử) 
2 Tiếp cận cài đặt Quy hoạch động 
Tiếp cận từ trên xuống (Top Down) – Dùng đệ qui có nhớ (Memoization) 
[Divide] Chia bài toán thành các bài toán con 
[Solve] 
Trước khi giải bài toán con, chúng kiểm tra xem bài toán này đã được giải trước đó chưa. 
Nếu đã giải thì lấy lời giải trong bảng ra 
Nếu chưa giải thì giải 
Sau khi có lời giả thì chúng lưu kết quả lại vào bảng 
[Combine] Kết hợp các lời giải của các bài toán con thành lời giải của bài toán 
2 Tiếp cận cài đặt Quy hoạch động 
Sơ đồ cài đặt 
void DynamicProgramming(A, x){	 if (A đã giải quyết)	x = LoiGiai(A) ; // Lấy lời giải từ bộ nhớ	 if (A du nho) 	 LoiGiai(A) = Solve(A); //lưu lời giải bài	 //toán A vào bộ nhớ	 else 	{	- Phan chia A thanh A 0 , A 1 , , A n-1 	- for (i=0; i<n; i++)	DynamicProgramming(A i , x i )	- Ket hop cac nghiem x i de duoc nghiem x	- LoiGiai(A) = x;	}} 
2 Tiếp cận cài đặt Quy hoạch động 
Ưu điểm của tiếp cận Top – Down 
Cài đặt ngắn gọn 
Có thể quan sát các bài toán con cần giải 
Khuyết điểm của tiếp cận Top – Down 
Tốn nhiều bộ nhớ vì phải lưu toàn bộ các bài toán con đã giải vì không biết bài toán con đó còn dùng nữa hay không 
Ví dụ 
Tính số Fibonacci thứ n 
Nếu n=1 hay n=2 
Nếu n >2 
Hai tiếp cận bằng Quy hoạch động 
Dùng tiếp cận từ trên xuống 
Dùng tiếp cận từ dưới lên 
Ví dụ 
cài đặt 
void QHD_TopDown( int n){} 
Ví dụ 
cài đặt 
void QHD_BottomUp( int n){} 
Quy hoạch động và Bài toán tối ưu 
Phương pháp 
Định nghĩa Quy hoạch động: Quy hoạch động là phương pháp giải quyết các bài toán tối ưu bằng cách tạo ra một chuỗi các quyết định xác định . Với mỗi quyết định, các bài toán con được giải quyết theo cùng cách sao cho lời giải tối ưu của bài toán ban đầu có thể được tìm thấy từ các lời giải tối ưu của các bài toán con . 
Phương pháp 
Phương pháp Quy hoạch động dựa trên nguyên tắc tối ưu của Bellman 
Nguyên lý tối ưu của Bellman: 
Trong một quá trình quyết định có nhiều giai đoạn, Lời giải tối ưu có thuộc tính: 
Dù trạng thái ban đầu và các quyết định ban đầu như thế nào đi nữa thì những quyết định còn lại phải tạo thành lời giải tối ưu mà không phụ thuộc vào trạng thái được sinh ra từ những quyết định ban đầu 
Phương pháp 
Bellman’s Principle of Optimality 
An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. 
Phương pháp 
Chúng ta gọi: 
Hàm mục tiêu là f 
Giá trị tối ưu là f* 
Các quyết định là d 1 , d 2 ,  
Phương pháp 
Nguyên lý tối ưu của Bellman: 
Nói cách khác ngắn gọn hơn: 
Lời giải tối ưu cho bài toán P phải chứa lời giải tối ưu của các bài toán con của P ( Lời giải tối ưu có lời giải con tối ưu ) 
Nguyên lý trên phù hợp với nhận xét rằng: Nếu lời giải mà có lời giải con không tối ưu thì khi thay lời giải con đó bằng lời giải con tối ưu sẽ cho lời giải tối ưu hơn lời giải ban đầu 
Phương pháp 
Giả thiết: Nếu xmy là đường tối ưu từ x đến y. Đường đi này qua m thì my là đường đi tối ưu 
Chứng minh: Giả sử không đúng. Thế thì có một đường khác là đường c là đường đi tối ưu từ m đến y. Nghĩa là: Đường đi từ x đến m, rồi theo đường c đến y sẽ tối ưu hơn đường đi ban đầu. 
Đều này mâu thuẫn với giả thiết là xmy là đường đi tối ưu từ x đến y 
m 
x 
c 
y 
Phương pháp 
Nhận xét: 
Nguyên lý tối ưu của Bellman còn được gọi là thuộc tính cấu trúc con tối ưu (Optimal substructure) 
Việc giải bài toán tối ưu sẽ đưa về giải bài toán con tối ưu cùng dạng 
Để việc tính toán của phương pháp DP đạt hiệu quả thì các lời giải của các bài toán con được sử dụng nhiều lần chỉ nên được giải 1 lần rồi lưu trữ lại để sử dụng lại sau này 
Phương pháp 
Các bước giải bài toán tối ưu theo Quy hoạch động: 
Bước 1 [Xác định cấu trúc con tối ưu]: 
Chọn số tham số cho Hàm mục tiêu f 
(Hàm mục tiêu dùng để biểu diễn cấu trúc con của bài toán) 
Số tham số của hàm mục tiêu f phụ thuộc vào 
Số đại lượng tham gia vào bài toán 
Cấu trúc con tối ưu của từng bài toán tối ưu cụ thể 
Phương pháp 
Bước 2 [Tính toán Trường hợp Cơ bản]: 
Tính hàm mục tiêu f với các giá trị đơn giản nhất để biết hướng xây dựng các giá trị của hàm f 
Bước 3 [Tính toán Trường hợp Tổng quát]: 
Tìm công thức cho hàm mục tiêu f 
(Công thức/phương trình quy hoạch động) 
(Công thức/phương trình Bellman) 
Phương pháp 
Bước 4: [Tạo bảng phương án] 
Tạo bảng lưu trữ các giá trị của hàm mục tiêu theo công thức đã tìm được trong bước 3 
Bước 5: [Truy vết] 
Nếu bài toán yêu cầu chỉ ra tuần tự các quyết đã thực hiện, chúng ta cần truy vết từ quyết định cuối về quyết định ban đầu 
Các ví dụ 
Ví dụ 1: [Dãy con tăng dài nhất] 
Cho dãy số nguyên A = a 1 , a 2 , , a n (n ≤ 1000, -10000 ≤ a i ≤ 10000). Dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. 
Yêu cầu: Hãy tìm một dãy con tăng của dãy A và có số phần tử nhiều nhất 
Các ví dụ 
Các ví dụ 
Ví dụ 2: [ Đ ường đi lớn nhất] 
Cho hình chữ nhật kích thước mxn (n,m ≤100 ), mỗi ô chứa một số nguyên. Có thể di chuyển từ ô (i, j) đến 1 trong 3 ô kề bên phải (i-1, j+1) (i, j+1) và (i+1, j+1) thuộc hình chữ nhật. 
Yêu cầu: Hãy tìm một cách di chuyển từ một ô nào đó thuộc cột 1 đến 1 ô nào đó thuộc cột n sao cho tổng các số của các ô đi qua là lớn nhất. 
Các ví dụ 
Các ví dụ 
Ví dụ 3: [Dãy con chung dài nhất] 
Cho 2 dãy số nguyên 
A = (a 1 , a 2 , , a n ). 
B=(b 1 , b 2 , , b m ) (n, m ≤ 100, -10000 ≤ a i , b j ≤ 10000). 
Yêu cầu: Hãy tìm một dãy C tăng và dài nhất, trong đó C là dãy con của A và C là dãy con của B 
Các ví dụ 
HẾT CHƯƠNG 8