Bài giảng Kỹ thuật lập trình: Chương 4 - Trần Minh Thái, Phạm Đức Thành

Bài giảng "Kỹ thuật lập trình - Chương 4:Phương pháp quy hoạch động" trình bày các nội dung: Ý tưởng và nguyên lý, công thức truy hồi, một số bài toán quy hoạch động. Cuối chương có phần bài tập để người đọc ôn luyện và vận dụng kiến thức đã học.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Chương 4 - Trần Minh Thái, Phạm Đức Thành Chương 4 Phương pháp quy hoạch động TRẦN MINH THÁI – minhthai@huflit.edu.vn ­ www.minhthai.edu.vn  PHẠM ĐỨC THÀNH –  phamducthanh@huflit.edu.vn ­ www.phamthao.com  9/17/16 Trần Minh Thái - Phạm Đức Thành 1 Nội dung v 4.1. Ý tưởng và nguyên lý v 4.2. Công thức truy hồi v 4.3. Một số bài toán quy hoạch động v 4.4. Tóm tắt chương v 4.5. Bài tập 9/17/16 Trần Minh Thái - Phạm Đức Thành 2 [4.1] Ý tưởng và nguyên lý v Một ví dụ giới thiệu về bài toán quy hoạch: “Trong mặt y phẳng xOy, tìm điểm có tọa độ R= 1 (x, y) sao cho x2+y2 [4.1] Ý tưởng và nguyên lý v Những điểm (x, y) thỏa điều kiện x2+y2 [4.1] Ý tưởng và nguyên lý 9/17/16 Trần Minh Thái - Phạm Đức Thành 5 [4.1] Ý tưởng và nguyên lý y phân giác thứ nhất R=1 tiếp tuyến O x 9/17/16 Trần Minh Thái - Phạm Đức Thành 6 [4.1] Ý tưởng và nguyên lý Bài toán trên gọi là tối ưu (bài toán quy hoạch). Trong đó: v Có một hàm ƒ gọi là hàm mục tiêu (hay đánh giá). v Một số hàm cho giá trị luận lý ǥ1, ǥ2, .., ǥn (hàm ràng buộc). v Một nghiệm x là tốt nhất khi: x thỏa điều kiện ràng buộc ǥi (x) = true, với mọi i: 1 [4.1] Ý tưởng và nguyên lý v Với bài vừa xét ở trên, ta có: v Hàm ƒ: ƒ(x,y) = x+y. v Hàm ràng buộc ǥ: x2+y2 Phương pháp quy hoạch động v Richard Bellman phát minh - 1953. v Ý tưởng của nguyên lý tối ưu Bellman là Ø “Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, với trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”. Ø “Nếu một cấu hình là tối ưu thì mọi cấu hình con của nó cũng là tối ưu”. 9/17/16 Trần Minh Thái - Phạm Đức Thành 9 Phương pháp quy hoạch v động Dùng để giải các bài toán tối ưu có bản chất là đệ quy: Ø Việc tìm phương án tối ưu có thể đưa về tìm tối ưu cho các bài toán con hữu hạn. Ø Thuật toán đệ quy đã tìm hiểu ở chương 3 đa số là dùng nguyên lý “chia để trị” và trong quy hoạch động cũng áp dụng nguyên lý này. 9/17/16 Trần Minh Thái - Phạm Đức Thành 10 Hai loại quy hoạch động v Phép phân giải đệ quy theo hướng top-down: Ø Bắt đầu từ bài toán lớn phân rã thành bài toán con. Ø Đi giải từng bài toán con. Việc giải bài toán con lại đưa về phép phân rã tiếp thành các bài toán con nhỏ hơn. v Phép phân giải đệ quy theo hướng bottom-up: Ø Bắt đầu giải các bài toán nhỏ (bài toán cơ sở). Ø Sau đó giải các bài toán lớn hơn (bài toán ban đầu). 9/17/16 Trần Minh Thái - Phạm Đức Thành 11 Hai loại quy hoạch động v Ví dụ: tính số hạng thứ n của dãy Fibonaci như sau: 9/17/16 Trần Minh Thái - Phạm Đức Thành 12 Hai loại quy hoạch động static int fiBoNaCi_QuyHoach_C1(int n) { int kq, Fn_1, Fn_2; if (n Hai loại quy hoạch động static int fiBoNaCi_QuyHoach_C2(int n) { int []Fn=new int[101]; Fn[0] = Fn[1] = 1; for (int i = 2; i Khái niệm v Bài toán quy hoạch động: là bài toán được giải theo phương pháp quy hoạch động. v Công thức truy hồi của quy hoạch động: là công thức phối hợp nghiệm của các bài toán con để có nghiệm cho bài toán lớn. v Bảng phương án của quy hoạch động: là Không gian lưu trữ lời giải của các bài toán con để tìm cách phối hợp chúng. 9/17/16 Trần Minh Thái - Phạm Đức Thành 15 Các bước cài đặt v Cần thỏa mãn các yêu cầu sau: Ø Phải phân rã được bài toán lớn thành các bài toán con và sự phối hợp lời giải đó cho ta lời giải cuối cùng của bài toán lớn. Ø Phải có đủ không gian bộ nhớ vật lý. Ø Quá trình phối hợp lời giải bài toán con đến bài toán ban đầu, phải có một số bước hữu hạn (tính dừng của chương trình). 9/17/16 Trần Minh Thái - Phạm Đức Thành 16 Các bước cài đặt v Bước 1: Phân tích bài toán, lập công thức truy hồi. v Bước 2: Giải tất cả các bài toán con và lưu vào bảng phương án (dùng mảng một chiều hoặc hai chiều). v Bước 3: Dùng công thức truy hồi để phối hợp các lời giải của những bài toán con, lặp cho đến khi tìm được lời giải ban đầu. v Bước 4: Dựa vào bảng phương án, truy vết tìm lời giải tối ưu. 9/17/16 Trần Minh Thái - Phạm Đức Thành 17 Các bước cài đặt v Ví dụ: Tính v B1: Phân tích bài toán, công thức truy hồi: 9/17/16 Trần Minh Thái - Phạm Đức Thành 18 Các bước cài đặt v B2: Giải bài toán con và lưu vào bảng phương án v Bảng phương án với n=4 F 0 1 2 3 4 0 1 1 1 1 2 1 1 3 1 1 4 1 1 9/17/16 Trần Minh Thái - Phạm Đức Thành 19 Các bước cài đặt v B3: Tính từ dòng i=2 đến n theo công thức truy hồi sau: F[i,k]=F[i-1,k]+F[i-1,k-1]; v Bảng phương án sau khi thực hiện B3 F 0 1 2 3 4 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 v B4: Kết quả bài toán lưu ở dòng cuối cùng và cột k 9/17/16 ...