Đang chuẩn bị liên kết để tải về 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

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. | 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 28/04/2016 1 Trần Minh Thái - Phạm Đức Thành 4.1. Ý tưởng và nguyên lý 4.2. Công thức truy hồi 4.3. Một số bài toán quy hoạch động 4.4. Tóm tắt chương 4.5. Bài tập 28/04/2016 2 Trần Minh Thái - Phạm Đức Thành Nội dung Một ví dụ giới thiệu về bài toán quy hoạch: 28/04/2016 3 y O x R=1 “Trong mặt phẳng xOy, tìm điểm có tọa độ (x, y) sao cho x2+y2<=1 và x+y có giá trị tốt nhất” Trần Minh Thái - Phạm Đức Thành [4.1] Ý tưởng và nguyên lý Những điểm (x, y) thỏa điều kiện x2+y2<=1 là những điểm có tọa độ nằm trong hình tròn có tâm O (gốc tọa độ) và bán kính R=1. Vì thế, nghiệm cần tìm phải nằm trong hình tròn (O, 1). 28/04/2016 4 Trần Minh Thái - Phạm Đức Thành [4.1] Ý tưởng và nguyên lý Những đường thẳng có phương trình x + y = C là những đường thẳng vuông góc với đường phân giác thứ nhất Ta đi tìm số C lớn nhất mà đường thẳng x + y = C vẫn có điểm chung với đường tròn (O, 1), đó chính là tiếp tuyến với đường tròn, có phương trình là Với tiếp điểm (, ) chính là nghiệm của bài toán 28/04/2016 5 Trần Minh Thái - Phạm Đức Thành [4.1] Ý tưởng và nguyên lý 28/04/2016 6 y O x R=1 phân giác thứ nhất tiếp tuyến Trần Minh Thái - Phạm Đức Thành [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 đó: Có một hàm ƒ gọi là hàm mục tiêu (hay đánh giá). Một số hàm cho giá trị luận lý ǥ1, ǥ2, , ǥn (hàm ràng buộc). 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<=i<=n. Không tồn tại một x’ nào thỏa ràng buộc mà ƒ(x’) tốt hơn ƒ(x). 28/04/2016 7 Trần Minh Thái - Phạm Đức Thành [4.1] Ý tưởng và nguyên lý Với bài vừa xét ở trên, ta có: Hàm ƒ: ƒ(x,y) = x+y. Hàm ràng buộc ǥ: x2+y2<=1. Một nghiệm x là tốt nhất với ý nghĩa là lớn nhất. Các bài toán quy hoạch rất phong phú, đa dạng và nhiều ứng dụng thực tế. Tuy nhiên có một số bài toán chưa giải được. 28/04/2016 8 Trần | 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 28/04/2016 1 Trần Minh Thái - Phạm Đức Thành 4.1. Ý tưởng và nguyên lý 4.2. Công thức truy hồi 4.3. Một số bài toán quy hoạch động 4.4. Tóm tắt chương 4.5. Bài tập 28/04/2016 2 Trần Minh Thái - Phạm Đức Thành Nội dung Một ví dụ giới thiệu về bài toán quy hoạch: 28/04/2016 3 y O x R=1 “Trong mặt phẳng xOy, tìm điểm có tọa độ (x, y) sao cho x2+y2<=1 và x+y có giá trị tốt nhất” Trần Minh Thái - Phạm Đức Thành [4.1] Ý tưởng và nguyên lý Những điểm (x, y) thỏa điều kiện x2+y2<=1 là những điểm có tọa độ nằm trong hình tròn có tâm O (gốc tọa độ) và bán kính R=1. Vì thế, nghiệm cần tìm phải nằm trong hình tròn (O, 1). 28/04/2016 4 Trần Minh Thái - Phạm Đức Thành [4.1] Ý tưởng và nguyên lý Những đường thẳng có phương trình x + y = C là những đường thẳng vuông góc với đường phân giác thứ nhất Ta đi tìm số C lớn nhất mà đường thẳng x + y