- Một số khái niệm cơ bản về phương pháp quy hoạch động. - Các bước giải quyết bài toán bằng phương pháp quy hoạch động. - So sánh phương pháp quy hoạch động với các phương pháp khác. - Phương pháp quy hoạch động và phương pháp đệ quy. - Phương pháp quy hoạch động và phương pháp vét cạn. - Cài đặt chương trình cho một số bài toán đơn giản thường gặp. - Ví dụ 1: Bài toán tính a n (n là số nguyên dương. - Ví dụ 4: Bài toán tháp Hà Nội. - Ví dụ 5: Bài toán cái túi. - Bài toán 1: Dãy con có tổng bằng S. - Bài toán 2: Dãy con có tổng lớn nhất. - Bài toán 3: Chia kẹo. - QHĐ Quy hoạch động. - QHD Quy hoạch động. - PP Phương pháp. - Trong đó, mỗi thuật toán chỉ áp dụng cho những lớp bài toán phù hợp. - Quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure).. - Phương pháp quy hoạch động là một phương pháp hiệu quả trong việc giải bài toán tối ưu hoá rời rạc. - Có một số bài toán sử dụng phương pháp quy hoạch động lại cho hiệu quả cao hơn so với các phương pháp khác. - Trong các kỳ thi học sinh giỏi tỉnh và cao hơn hiện nay, từ 30% đến 40% các bài thi cần đến quy hoạch động và đây là những bài toán khó, đòi hỏi học sinh phải có tư duy lập trình cao. - Có thể có những cách khác để giải bài toán đó. - Hiểu rõ các thuật toán là bước đầu giúp các em học sinh tự tin đồng thời phân tích bài toán và xác định phương pháp giải đúng đắn sẽ giúp các em có thành tích tốt hơn. - Vì vậy tôi chọn đề tài “Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán đơn giản trong Tin học” làm đề tài nghiên cứu. - Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán đơn giản trong Tin học.. - Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu.. - Quy hoạch động trong ngành khoa học máy tính: Là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure).. - Phương pháp 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). - Ý tưởng cơ bản của phương pháp quy hoạch động là tránh tính toán lại các bài toán con đã xét, nói cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ.. - Một bài toán P muốn giải bằng phương pháp quy hoạch động cần có 2 đặc điểm sau:. - Bài toán P thỏa mãn nguyên lý tối ưu Bellman, nghĩa là có thể sử dụng lời giải tối ưu của các bài toán con từ mức thấp nhất để tìm dần lời giải tối ưu cho bài toán con ở mức cao hơn và cuối cùng là lời giải tối ưu cho bài toán P.. - Bài toán P có các bài toán con phủ chồng lên nhau, nghĩa là không gian bài toán con “hẹp” không tạo dạng hình cây.. - Các bước giải quyết bài toán bằng phương pháp quy hoạch động.. - Áp dụng nguyên lý tối ưu của Bellman ta phân rã bài toán ban đầu thành các bài toán con có cùng cấu trúc sao cho việc giải quyết bài toán con cấp i phụ thuộc vào kết quả của các bài toán con trước đó. - Cụ thể hóa bước này là ta phải xây dựng được hàm mục tiêu F(i) là nghiệm của bài toán con cấp i.. - Bước 2: Xác định các bài toán cơ sở.. - Bài toán cơ sở là các bài toán con nhỏ nhất mà ta có thể biết ngay kết quả hoặc tính được kết quả dễ dàng. - Đây chính là cơ sở để tính nghiệm cho các bài toán cấp lớn hơn.. - Căn cứ vào ý nghĩa của hàm mục tiêu, tìm mối quan hệ giửa các bài toán con các cấp, ta tiến hành xây dựng công thức tính kết quả của bài toán cấp i dựa vào kết quả của các bài toán con cấp trước đó.. - Sử dụng công thức truy hồi và nghiệm các bài toán cơ sở tính nghiệm tất cả các bài toán con và lưu trữ chúng vào bảng phương án.. - Bước 5: Kết luận nghiệm của bài toán.. - Dựa vào bảng phương án chỉ ra nghiệm của bài toán. - Bài toán 1: Tính a n (n là số nguyên dương. - Bước 1: Hàm mục tiêu: f(i) là lũy thừa của a i - Bước 2: Các bài toán cơ sở: f(0. - f(i) 1 a a*a 1 a*a 2 a*a 3 a*a 4 a*a 5 - Bước 5: Nghiệm f(n) của bài toán. - Bài toán 2: Tính n!. - Bước 1: Hàm mục tiêu: f(i) là giai thừa của số i - Bước 2: Các bài toán cơ sở: f(0. - f(i Bước 5: Nghiệm F(n) của bài toán. - Bài toán 3: Tìm số Fibonaci thứ N?. - Bước 2: Các bài toán cơ sở: f(0. - f(i Bước 5: Nghiệm f(n) của bài toán. - Bài toán 4: Tháp Hà Nội. - Bước 2: Các bài toán cơ sở: f(1. - Bài toán 5: Bài toán cái túi. - Bước 2: Các bài toán cơ sở: F[0,j. - So sánh phương pháp quy hoạch động với các phương pháp khác 2.1. - Về mặt nguyên tắc phương pháp quy hoạch động rất giống với phương pháp đệ quy.. - Giống nhau: Cả hai phương pháp đều sử dụng lời giải của các bài toán có kích thước bé hơn, đồng dạng với bài toán ban đầu để đưa ra lời giải của bài toán ban đầu.. - Quy hoạch động Đệ quy. - Gọi thực hiện các bài toán cả hai chiều:. - Các kết quả trung gian được lưu lại, khi giải các bài toán lớn hơn chỉ cần cần lấy ra không cần tính toán lại.. - Gọi thực hiện các bài toán có kích thước lớn trước rồi đến các bài toán có kích thước bé hay thực hiện các bài toán từ trên xuống (top - down). - Trong hầu hết các bài toán thì quy hoạch động chiếm ưu thế hơn đệ quy nhưng trong một vài trường hợp cả hai bài toán thực hiện đều như nhau. - Ví dụ 1: Bài toán tính a n (n là số nguyên dương). - Như vậy trong bài này khi ta dùng đệ quy để giải bài toán. - Mỗi bài toán con sẽ được lưu lại vào mảng f trước khi tính những bài toán con lớn hơn. - Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.. - Đặc điểm của lời giải bài toán theo phương pháp quy hoạch động: giải quyết bài toán đệ quy từ mức thấp trước, lời giải của chúng được lưu lại và được sử dụng. - Nếu tính toán như trên, chúng ta có rất nhiều bài toán con sẽ được tính đi tính lại, điển hình là các số f(1) và f(2).. - Đặc điểm của lời giải đệ quy: thực hiện bài toán từ việc phân tích ở mức cao xuống mức thấp.. - 14 để tìm lời giải của các bài toán ở mức cao hơn.. - Ưu điểm là chạy rất nhanh - Nhược điểm của nó là rất khó tìm ra thuật toán, với một số bài toán có thể sẽ không có thuật toán quy hoạch động.. - Vét cạn là một trong những thuật toán giải bài toán tối ưu. - Thuật toán vét cạn là thuật toán tìm phương án tối ưu của bài toán bằng cách lựa chọn một phương án trong tập hợp tất cả các phương án của bài toán để tìm ra phương án tối ưu. - Vì trong đề tài chỉ nói đến những bài toán đơn giản nên thường là những bài toán dễ tìm ra phương pháp giải và phương pháp giải thường dùng là đệ quy hoặc quy hoạch. - Nên phần ví dụ trong SKKN này mỗi bài toán tôi chỉ xin phép đề cập đến mối tương quan giữa hai phương pháp là đệ quy và quy hoạch động. - Giúp người học dể hiểu, dễ phân biệt và rút ra được cái hay và cái chưa hay của quy hoạch động trong từng bài toán.. - Ví dụ 1: Bài toán tính a n (n là số nguyên dương).. - Cách xác định bài toán - Input: a, n. - Output: giá trị a n Ý tưởng của bài toán. - Trong bài toán này có giá trị chặn là n = 0 Cài đặt chương trình. - Phương pháp QHĐ Phương pháp ĐQ. - Ví dụ 2: Tính n! (n là số nguyên dương) Cách xác định bài toán. - Output: giá trị giai thừa của n Ý tưởng của bài toán. - Trong bài toán này có hai giá trị chặn là n = 0 và n = 1 Cài đặt chương trình. - Ta thấy rằng trong trường hợp này phương pháp quy hoạch động không hơn gì phương pháp đệ quy.. - Cách xác định bài toán - Input: n. - Output: giá trị fibonacci của n Ý tưởng của bài toán. - Nhận xét: Trong bài toán này khi chạy thử với giá trị n nhỏ thì thấy số lần lặp không hơn nhau nhiều. - Như vậy, trong bài toán này ta chọn PP QHĐ sẽ nhanh hơn ĐQ rất nhiều.. - Ý tưởng của bài toán. - Nhận xét: Trong bài toán này cả hai phương pháp đều có số lần lặp như nhau.. - Cách xác định bài toán. - Giải quyết bài toán trong các trường hợp sau:. - Bài toán con nhỏ nhất.. - Nhận xét: Trong bài toán này ta thấy PP QHĐ có số lần lặp ít hơn rất nhiều so với PP ĐQ.. - Kết quả ra ghi ra file DAYCON.OUT Nếu bài toán vô nghiệm ghi số 0.. - Nếu bài toán có nghiệm thì trên dòng thứ nhất ghi số 1. - Học sinh được học theo nội dung trình bày trong sáng kiến sẽ có cái nhìn toàn diện hơn, tự tin hơn khi đối mặt với bài toán trong Tin học từ đó các em sẽ thích học và chủ động tìm hiểu kiến thức. - Một số học sinh có tiến bộ rõ rệt khi tiếp cận các bài toán sử dụng phương pháp QHĐ.. - “Giúp học sinh tiếp cận với thuật toán quy hoạch động bằng một số bài toán đơn giải trong Tin học” được hoàn thiện hơn và trở thành một tài liệu hay, hữu ích trong việc dạy và học lập trình.. - Trần Lê Hồng Dũ, Phạm Ngọc Chí Nhân – Trường THPT Bến Tre, Các bài toán về quy hoạch động.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt