Tài liệu Luận văn thạc sĩ phương pháp quy hoạch động và vận dụng kết hợp giải các bài toán chuyên tin bậc thpt

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA THÁI PHONG NGHĨA THÁI PHONG NGHĨA * PHƯƠNG PHÁP QUY HOẠCH ĐỘNG VÀ VẬN DỤNG KẾT HỢP GIẢI CÁC BÀI TOÁN CHUYÊN TIN BẬC THPT KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH * KHÓA K32 Đà Nẵng - Năm 2018 ĐẠI HỌC ĐÀ NẴNG TRƢỜNG ĐẠI HỌC BÁCH KHOA ------------------ THÁI PHONG NGHĨA PHƢƠNG PHÁP QUY HOẠCH ĐỘNG VÀ VẬN DỤNG KẾT HỢP GIẢI CÁC BÀI TOÁN CHUYÊN TIN BẬC THPT Chuyên ngành : Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SỸ Khoa học máy tính NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TSKH TRẦN QUỐC CHIẾN Đà Nẵng – Năm 2018 i LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả Thái Phong Nghĩa ii MỤC LỤC Trang MỞ ĐẦU .................................................................................................................................... 1 1. Lý do chọn đề tài ................................................................................................................ 1 2. Mục tiêu nghiên cứu ........................................................................................................... 2 3. Đối tƣợng và phạm vi nghiên cứu ...................................................................................... 2 4. Phƣơng pháp nghiên cứu .................................................................................................... 2 5. Ý nghĩa khoa học và thực tiễn của đề tài ............................................................................ 2 CHƢƠNG 1: LÝ THUYẾT VỀ QUY HOẠCH ĐỘNG ............................................................ 3 1.1. Giới thiệu về phƣơng pháp quy hoạch động................................................................... 3 1.1.1. Bài toán tối ƣu .......................................................................................................... 3 1.1.2. Nguyên lý Bellman ................................................................................................... 4 1.1.3. Bảng phƣơng án ........................................................................................................ 4 1.2. Nhận dạng bài toán quy hoạch động. .............................................................................. 5 1.3. Ƣu điểm của quy hoạch động. ......................................................................................... 5 1.4. Các bƣớc thực hiện quy hoạch động ............................................................................... 6 1.4.1. Xây dựng công thức truy hồi .................................................................................... 6 1.4.2. Tổ chức dữ liệu và chƣơng trình .............................................................................. 7 1.4.3. Làm tốt (tối ƣu thuật toán nếu đƣợc): ....................................................................... 7 1.4.4. Truy vết tìm phƣơng án tối ƣu .................................................................................. 7 1.5. Các lớp bài toán quy hoạch động và ứng dụng ............................................................... 8 1.5.1. Dạng 1: Dãy con đơn điệu dài nhất .......................................................................... 8 1.5.1.1. Mô hình ............................................................................................................. 8 1.5.1.2. Công thức QHĐ ................................................................................................. 8 1.5.1.3. Cài đặt ................................................................................................................ 8 1.5.1.4. Một số bài toán là biến thể cùng lớp của “dãy con đơn điệu dài nhất” ............. 9 1.5.2. Dạng 2: Chia kẹo .................................................................................................... 10 1.5.2. 1. Mô hình .......................................................................................................... 10 1.5.2. 2. Công thức ....................................................................................................... 10 1.5.2. 3. Cài đặt ............................................................................................................. 10 1.5.2. 4. Một số bài toán biến thể cùng lớp với bài toán “chia kẹo” ............................ 11 1.5.3. Dạng 3: Xâu con chung dài nhất ............................................................................ 12 1.5.3. 1. Mô hình .......................................................................................................... 12 1.5.3. 2. Công thức QHĐ .............................................................................................. 12 1.5.3. 3. Cài đặt ............................................................................................................. 12 1.5.3. 4. Một số bài toán là biến thể cùng lớp của “Xâu con chung dài nhất” ............. 13 1.5.4. Một số dạng khác: .................................................................................................. 14 1.6. Hạn chế của quy hoạch động ......................................................................................... 14 CHƢƠNG 2: GIỚI THIỆU MỘT SỐ THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU ĐỂ KẾT HỢP VỚI PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ............................................................... 15 2.1. Bài toán 1: Phần thƣởng ................................................................................................ 15 2.2. Bài toán 2: Đoạn con liên tiếp có tổng lớn nhất ............................................................ 17 iii 2.3 Quy hoạch động dựa trên bài toán đã đƣợc sắp xếp. ...................................................... 19 2.3.1 Sắp xếp .................................................................................................................... 19 2.3.2 Phát biểu bài toán ................................................................................................... 20 2.3.3 Các thuật toán sắp xếp thông dụng ......................................................................... 20 2.3.3.1 Thuật toán sắp xếp nổi bọt (Bubble Sort) ........................................................ 20 2.3.3.2 Thuật toán sắp xếp nhanh (Quick Sort) ........................................................... 22 2.3.3.4 Sắp xếp bằng đếm phân phối (Distribution Counting) ..................................... 24 2.3.3.5 Một số bài toán ................................................................................................ 24 2.4. Quy hoạch động kết hợp xử lý Bit để mô tả trạng thái bài toán. ................................... 29 2.4.1. Bit và các thao tác xử lý Bit. .................................................................................. 29 2.4.1.1 Quy ƣớc về vị trí của các bit. ............................................................................ 29 2.4.1.2 Các phép toán logic .......................................................................................... 29 2.4.1.3 Một số ứng dụng ............................................................................................... 31 2.4.2 Một số bài toán cùng lớp có thể dùng quy hoạch động kết hợp bit. ........................ 33 CHƢƠNG 3: CÀI ĐẶT CHƢƠNG TRÌNH MINH HỌA BẰNG FREE PASCAL ............... 45 3.1 Bài toán : Robot .............................................................................................................. 45 3.2 Bài toán : Đoạn con gối nhau dài nhất ........................................................................... 45 3.3 Bài toán : Chọn ô ............................................................................................................ 46 3.4 Bài toán : Sherry ............................................................................................................. 48 KẾT LUẬN VÀ KIẾN NGHỊ .................................................................................................. 51 1. Kết quả đạt đƣợc ............................................................................................................... 51 2. Kiến nghị và hƣớng phát triển .......................................................................................... 52 DANH MỤC TÀI LIỆU THAM KHẢO ................................................................................. 53 PHỤ LỤC 1. Code bài: “Phần thƣởng” 2. Code bài: “Đoạn con liên tiếp có tổng lớn nhất” 3. Code bài: “Robot” 4. Code bài: “Đoạn gối nhau dài nhất” 5. Code bài: “Chọn ô” 6. Code bài: “Sherry” iv PHƢƠNG PHÁP QUY HOẠCH ĐỘNG VÀ VẬN DỤNG KẾT HỢP GIẢI CÁC BÀI TOÁN CHUYÊN TIN BẬC THPT Học viên: Thái Phong Nghĩa Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 Trƣờng Đại học Bách khoa. Tóm tắt - Quy hoạch động là một chuyên đề rất hay và mạnh của tin học, đã vậy thực hiện quy hoạch động trên dãy bit lại còn cho kết quả khả quan hơn nữa. Nhƣ chúng ta đã biết, phép xử lí bit có thời gian thực hiện rất nhỏ, nhỏ hơn phép số học toán thông thƣờng. Vì vậy, trong luận văn này, phạm vi dữ liệu mà tôi muốn đề cập đến là bit và quy hoạch động trên dãy bit. Bên cạnh đó luận văn cũng trình bày một số cách quy hoạch trên dãy đã đƣợc sắp xếp cùng với một số bài toán điển hình dùng để minh họa cho quy hoạch động. Các bài toán đƣợc phân tích, thiết kế và cài đặt theo phƣơng pháp quy hoạch động và phƣơng pháp khác nhằm để so sánh và thấy đƣợc ƣu điểm của phƣơng pháp quy hoạch động (chủ yếu là về mặt thời gian chạy của thuật toán). Luận văn cũng đã cho thấy có sự cùng dạng của một lớp các bài toán có thể chuyển về xử lý bằng cách mô tả các trạng thái của bài toán bằng dãy bit và từ đó thực hiện quy hoạch động trên dãy bit đó để đạt đƣợc kết quả tối ƣu. Từ khóa – Quy hoạch động; sắp xếp; xử lý bit; trạng thái của bài toán; Bài toán tối ƣu. DYNAMIC PROGRAMMING METHOD AND COMBINATION OF OTHERS TO SOLVE ADVANCED PROBLEMS IN INFORMATICS AT HIGH SCHOOL LEVEL Abstract – Dynamic programming is a great and powerful subject of informatics, so implementing dynamic programming on the series of bit is more important. As we all know, bit processing has a very small execution time, which is smaller than regular arithmetic operations. The dissertation, therefore, aims to delve into bit and dynamic programming on the series of bit. In addition, the thesis also presents some of the planning methods on the designed series of bit along with some typical problems used to illustrate the dynamic programming. The problems are analyzed, designed and implemented by dynamic programming and other methods to compare and find the advantages of the dynamic programming (mainly in terms of execution time of algorithms). The thesis also shows the similarity of a class of mathematical problems that can be transferred to the process by describing the states of the problem by the series of bit and from which dynamic programming on that series of bit is to achieve optimal results. Keywords – Dynamic programming; sort; bit processing; the state of the problem; optimal problem. v DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Các ký hiệu O() A[i,j] B[i] Abs() Độ phức tạp thuật toán Mảng 2 chiều có tên là A, chứa giá trị tại dòng i, cột j Mảng 1 chiều có tên B, chứa giá trị tại cột i Hàm cho giá trị tuyệt đối trong Pascal Các chữ viết tắt Từ viết tắt Nội dung THPT Trung học phổ thông Bubble sort Quick Sort Distribution Counting Code Sắp xếp nổi bọt Sắp xếp nhanh Diễn giải Trƣờng cấp 3 trong hệ giáo dục phổ thông Tên thuật toán Tên thuật toán Đếm phân phối Tên thuật toán Mã lệnh Test Bộ dữ liệu kiểm thử Input Dữ liệu vào Output Dữ liệu ra Các câu lệnh chƣơng trình Dùng kiểm tra tính đúng đắn của chƣơng trình Thông thƣờng là file tệp văn bản chứa dữ liệu để chƣơng trình lấy dữ liệu từ đây vào xử lý. Thông thƣờng là file tệp văn bản chứa dữ liệu đã đƣợc chƣơng trình xuất kết quả ra theo yêu cầu của đề bài. vi DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 2.1 Bảng minh họa kết quả bài toán “Phần thưởng” 15 2.2 Bảng lưu giá trị của F[i,j] bài toán “Phần thưởng” 16 2.3 Tìm giá trị hình vuông lớn nhất bài toán “Phần thưởng” 17 2.4 Bảng phương án tính F[n,x] của bài “Chọn ô”. 36 2.5 Bảng lưu vết bài toán “Chọn ô” 38 2.7 Các bảng Fx, vet, V thể hiện quá trình truy vết cho bài toán “Sherry” 41 vii DANH MỤC CÁC HÌNH Số hiệu hình Tên hình Trang 1.1 Các tiêu chí của bài toán tối ưu 3 2.6 Đồ thị biểu diễn đường đi giữa các thành phố bài toán “Sherry” 40 3.1 Kết quả chạy chương trình với m = 6 và n=5, bài “Robot”. 45 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 Kết quả chạy chương trình với n=5, bài “Đoạn con gối nhau dài nhất”. Kết quả chạy chương trình bằng PP QHĐ kết hợp bit với n=3, bài “Chọn ô”. Kết quả chạy chương trình bằng PP QHĐ thông thường với n=3, bài “Chọn ô”. Kết quả chạy chương trình bằng PP QHĐ kết hợp bit với n=20, bài “Chọn ô”. Kết quả chạy chương trình bằng PP QHĐ thông thường với n=20, bài “Chọn ô”. Kết quả chạy chương trình bằng PP QHĐ kết hợp bit với n=6, bài “Sherry”. Kết quả chạy chương trình bằng PP Duyệt quay lui với n=6, bài “Sherry”. Kết quả chạy chương trình bằng PP QHĐ kết hợp bit với n=10, bài “Sherry”. Kết quả chạy chương trình bằng PP Duyệt quay lui với n=10, bài “Sherry”. Kết quả chạy chương trình bằng PP QHĐ kết hợp bit với n=16, bài “Sherry”. 45 46 46 47 47 48 48 49 49 50 1 MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay nhiệm vụ phát hiện, đào tạo và bồi dƣỡng học sinh giỏi là một nhiệm vụ trọng tâm của các trƣờng THPT Chuyên của tất cả các tỉnh thành trong cả nƣớc, nhằm mục đích phát hiện bồi dƣỡng và đào tạo nhân tài, tạo ra một đội ngũ học sinh chất lƣợng cao làm tiền đề để phát triển nâng cao hơn nữa ở bậc đại học, sau đại học cho các em học sinh. Môn Tin học tự hào cũng là một môn học quan trọng không kém nên đƣợc đƣa vào chƣơng trình thi học sinh giỏi các cấp hằng năm nhƣ: thi học sinh giỏi cấp Tỉnh (thành phố), thi học sinh giỏi Olympic 30/04 (từ Đà Nẵng trở vào phía Nam), thi học sinh giỏi Quốc gia, bên cạnh đó còn có thi Tin học trẻ không chuyên (cấp Tỉnh và Toàn quốc). Cùng với nhiệm vụ quan trọng của cả nƣớc là đào tạo và bồi dƣỡng nhân tài nói chung trong các lĩnh vực khoa học tự nhiên và khoa học xã hội, môn tin học nói riêng vẫn đƣợc sự quan tâm của Bộ giáo dục và đào tạo, Sở giáo dục và đào tạo các tỉnh thành trong cả nƣớc, nên luôn có các kỳ thi học sinh giỏi môn tin học cho các em học sinh, bên cạnh đó còn có các cuộc thi cho sinh viên ở bậc đại học nhƣ: Olympic Tin học sinh viên, Mùa hè sáng tạo, Nhân tài đất Việt, ... và các cuộc thi quốc tế: ACM ICPC (International Collegiate Programming Contest), Google Summer of code, Top Coder, ... Trong vai trò là một giáo viên Tin học giảng dạy tại trƣờng THPT Chuyên Nguyễn Thiện Thành – TP Trà Vinh, hàng năm đều phải tham gia vào công tác bồi dƣỡng học sinh giỏi của bộ môn, cho đến nay qua nhiều năm bồi dƣỡng, bản thân tôi nhận thấy, trong cấu trúc của các đề thi học sinh giỏi môn Tin học, số lƣợng các bài toán trong một đề thi có thể giải bằng phƣơng pháp quy hoạch động thƣờng chiếm từ 30 – 70% của một đề thi, bởi khi ra đề thi ban tổ chức thƣờng rãi đều các chuyên mục của các phƣơng pháp nhƣ: duyệt, qui hoạch động và các thuật toán ứng dụng mô hình đồ thị, ... tuy nhiên trong đó có một số bài toán duyệt và ứng dụng mô hình đồ thị vẫn có thể áp dụng phƣơng pháp quy hoạch động để giải. Vì vậy có thể nói, quy hoạch động là một chuyên đề rất quan trọng mà mỗi học sinh thi tham gia đội tuyển học sinh giỏi đều phải nắm đƣợc nếu muốn đạt các thứ hạng cao ở các kỳ thi. Với những lý do thiết thực đó, tôi xin chọn thực hiện đề tài: “PHƢƠNG PHÁP QUY HOẠCH ĐỘNG VÀ VẬN DỤNG KẾT HỢP GIẢI CÁC BÀI TOÁN CHUYÊN TIN BẬC THPT”. 2 2. Mục tiêu nghiên cứu Xây dựng và phân tích có hệ thống các bài tập có thể giải bằng phƣơng pháp Quy hoạch động, phân lớp chúng thành các lớp bài toán bằng cách nhận diện dựa trên kinh nghiệm của ngƣời học từ các bài toán quy hoạch động điển hình, kinh điển. Vận dụng kết hợp để giải các bài toán chuyên Tin trong công tác bồi dƣỡng học sinh giỏi môn Tin học. Giúp cho học sinh đạt kết quả cao hơn trong các kỳ thi, có thể dùng làm tài liệu tham khảo để hỗ trợ cho học sinh giáo viên tin học dạy bồi dƣỡng chuyên tin, và trên hết giúp củng cố lại kiến thức về phƣơng pháp quy hoạch động cho bản thân. 3. Đối tƣợng và phạm vi nghiên cứu  Phƣơng pháp quy hoạch động.  Các bài toán tối ƣu có thể giải bằng phƣơng pháp quy hoạch động.  Các đề thi học sinh giỏi tin học các cấp. 4. Phƣơng pháp nghiên cứu  Nghiên cứu lý thuyết về phƣơng pháp quy hoạch động, nhận dạng các bài toán có thể giải bằng phƣơng pháp quy hoạch động và phân tích các ƣu điểm của nó từ đó kết hợp thêm các phƣơng pháp khác để áp dụng giải các bài toán tối ƣu.  Thiết kế thuật toán dựa trên phƣơng pháp quy hoạch động.  Dùng Free Pascal để cài đặt chƣơng trình, chạy thử nghiệm trên một số bộ dữ liệu kiểm thử, đánh giá kết quả.  Áp dụng bồi dƣỡng học sinh giỏi. 5. Ý nghĩa khoa học và thực tiễn của đề tài Ý nghĩa khoa học:  Nghiên cứu và phân tích phƣơng pháp quy hoạch động  Vận dụng kết hợp vào việc giải các bài toán chuyên tin. Ý nghĩa thực tiễn:  Giúp cho học sinh đạt kết quả cao hơn trong các kỳ thi học sinh giỏi Tin học.  Làm tài liệu tham khảo để hỗ trợ cho học sinh giáo viên tin học dạy bồi dƣỡng chuyên tin. 3 CHƢƠNG 1 - LÝ THUYẾT VỀ QUY HOẠCH ĐỘNG 1.1. Giới thiệu về phƣơng pháp quy hoạch động Trong ngành khoa học máy tính, phƣơng pháp quy hoạch động là một phƣơng pháp làm 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 phụ thuộc nhau và cấu trúc con tối ƣu [14]. Phƣơng pháp quy hoạch động cùng nguyên lý tối ƣu đƣợc nhà toán học Mỹ R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phƣơng pháp này đã đƣợc áp dụng để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật công nghệ, tổ chức sản xuất, kế hoạch hoá kinh tế… Tuy nhiên cần lƣu ý rằng có một số bài toán mà cách giải bằng quy hoạch động tỏ ra không thích hợp. Quy hoạch động là kỹ thuật thiết kế bottom-up (từ dƣới lên). Nó đƣợc bắt đầu với những trƣờng hợp con nhỏ nhất (thƣờng là đơn giản nhất và giải đƣợc ngay). Bằng cách tổ hợp các kết quả đã có (không phải tính lại) của các trƣờng hợp con, sẽ đạt tới kết quả của trƣờng hợp có kích thƣớc lớn dần lên và tổng quát hơn, thông qua công thức truy hồi, cho đến khi cuối cùng đạt tới lời giải của trƣờng hợp tổng quát nhất, đó cũng là giá trị tối ƣu cần tìm. 1.1.1. Bài toán tối ưu Trong thực tế, ta thƣờng gặp một số loại bài toán tối ƣu sau [2]: Có một đại lƣợng f hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối cùng là giá trị của f phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối ƣu của f. Giá trị của f phụ thuộc vào những đại lƣợng xuất hiện trong bài toán mà mỗi bộ giá trị của chúng đƣợc gọi là một trạng thái của hệ thống và phụ thuộc vào cách thức đạt đƣợc giá trị f trong từng giai đoạn mà mỗi cách tổ chức đƣợc gọi là một điều khiển. Đại lƣợng f thƣờng đƣợc gọi là hàm mục tiêu và quá trình đạt đƣợc giá trị tối ƣu của f đƣợc gọi là quá trình điều khiển tối ưu. Hình 1.1 Các tiêu chí của bài toán tối ưu thường là chi phí hoặc giá trị 4 1.1.2. Nguyên lý Bellman Bellman phát biểu nguyên lý tối ƣu (cũng gọi là nguyên lý Bellman) mà ý tƣởng cơ bản là nhƣ sau: “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”. Chú ý rằng nguyên lý này được thừa nhận mà không chứng minh. Phƣơng pháp tìm điều khiển tối ƣu theo nguyên lý Bellman thƣờng đƣợc gọi là quy hoạch động. Thuật ngữ này nói lên thực chất của quá trình điều khiển là động: có thể trong một số bƣớc đầu tiên lựa chọn điều khiển tối ƣu dƣờng nhƣ không tốt nhƣng tựu chung cả quá trình lại là tốt nhất. Ta có thể giải thích ý này qua bài toán sau: Cho một dãy N số nguyên A1, A2,…,AN. Hãy tìm cách xoá đi một số ít nhất số hạng để dãy còn lại là đơn điệu hay nói cách khác hãy chọn một số nhiều nhất các số hạng sao cho dãy B gồm các số hạng đó theo trình tự xuất hiện trong dãy A là đơn điệu. Quá trình chọn B đƣợc điều khiển qua N giai đoạn để đạt đƣợc mục tiêu là số lƣợng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn hay không chọn Ai vào dãy B. Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lƣợt 1, 8, 10 thì chỉ chọn đƣợc 3 số hạng nhƣng nếu bỏ qua 8 và 10 thì ta chọn đƣợc 5 số hạng 1, 2, 4, 6, 7. Khi giải một bài toán bằng cách “chia để trị” chuyển việc giải bài toán kích thƣớc lớn về việc giải nhiều bài toán cùng kiểu có kích thƣớc nhỏ hơn thì thuật toán này thƣờng đƣợc thể hiện bằng các chƣơng trình con đệ quy. Khi đó, trên thực tế, nhiều kết quả trung gian phải tính lặp đi lặp lại nhiều lần. 1.1.3. Bảng phương án Ý tƣởng cơ bản của quy hoạch động thật đơn giản: tránh tính toán lại mọi thứ hai lần, mà lƣu giữ kết quả đã tìm kiếm đƣợc vào một bảng - gọi là bảng phƣơng án, làm giả thiết cho việc tìm kiếm những kết quả của trƣờng hợp sau. Chúng ta sẽ làm đầy dần giá trị của bảng này bởi các kết quả của những trƣờng hợp trƣớc đã đƣợc giải. Kết quả cuối cùng chính là kết quả của bài toán cần giải. 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 độ. Đồng thời nó cũng khắc phục đƣợc việc tính toán lặp lại của đệ quy. Trong một số trƣờng hợp, khi giải một bài toán A, trƣớc hết ta tìm họ bài toán A(p) phụ thuộc tham số p (có thể p là một véc tơ) mà A(p0)=A với p0 là trạng thái ban đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng cách áp 5 dụng nguyên lý tối ƣu của Bellman. Cuối cùng cho p=p0 sẽ nhận đƣợc kết quả của bài toán A ban đầu. 1.2. Nhận dạng bài toán quy hoạch động Quy hoạch động là một phƣơng pháp hữu hiệu để giải quyết một bài toán tối ƣu. Có một vài yếu tố mà ngƣời lập trình cần chú ý khi nhận diện bài toán có thể giải bằng phƣơng phƣơng pháp quy hoạch động hay không đó là: - Thuộc dạng bài toán tối ƣu. - Có dạng tƣơng tự với các lớp bài toán về quy hoạch động điển hình, cơ bản. - Gặp bài toán có tính chất truy hồi. - Lời giải bài toán ở bƣớc sau đƣợc xây dựng thông qua lời giải bài toán ở bƣớc trƣớc. - Tìm đƣợc công thức truy hồi để phối hợp các bài toán con thành bài toán lớn hơn. - Kích thƣớc bài toán không quá lớn. Nhƣng để phát hiện ra và cài đặt tốt một bài quy hoạch động là rất khó khăn. Thƣờng thì chúng ta hay tiếp cận với những bài toán quy hoạch động mà đọc lên đã có ngay dạng hay phƣơng pháp giải, nhƣng nhƣ vậy là chƣa đủ bởi lẽ quy hoạch động không dừng lại ở đó. Chúng ta chỉ có thể giác ngộ tƣ tƣởng để giải một bài quy hoạch động chứ chúng ta không thể học hết đƣợc toàn bộ mọi phƣơng pháp quy hoạch. Vì vậy cách tốt nhất để giải đƣợc một bài toán quy hoạch động đòi hỏi tƣ duy tốt trong lập trình, và quan trọng là phải có kinh nghiệm, mà kinh nghiệm thì cần phải tích lũy bằng cách giải thật nhiều bài toán về quy hoạch động với nhiều dạng khác nhau. 1.3. Ƣu điểm của quy hoạch động Có nhiều phƣơng pháp để giải một bài toán tối ƣu. Có thể kể đến nhƣ: tham lam (Greedy), nhánh cận (Branch and Bound), vét cạn, … Tuy nhiên đa số các phƣơng pháp đó thƣờng ít có hiệu quả do thƣờng cài đặt dƣới dạng thủ tục đệ qui (nhánh cận), hoặc cho lời giải gần đúng chứ không phải tối ƣu (tham lam), hoặc có thể tìm đƣợc lời giải tối ƣu nhƣng lại quá lâu (vét cạn). Về bản chất, đệ qui và quy hoạch động là tƣơng tự nhau, tức là đều cùng giải các bài toán con để kết hợp tìm ra nghiệm của bài toán sau cùng. Nhƣng trong khi đệ qui thực hiện việc giải bài toán con lặp đi lặp lại nhiều lần gây lãng phí tài nguyên và thời gian thì quy hoạch động khắc phục đƣợc điều đó bằng cách mỗi bài toán con chỉ giải 1 lần và lƣu trữ chúng lại để sử dụng cho những bài toán lớn hơn. Trong khi phƣơng pháp nhánh cận chỉ là một bƣớc cải tiến của cách cài đặt đệ qui quay lui, phƣơng pháp này sẽ gặp khó trong trƣờng hợp đặt cận không đủ tốt để có 6 thể loại bỏ bớt các trƣờng hợp không cần xét. Suy cho cùng nhánh cận có tốt hơn nhƣng không đáng kể. Phƣơng pháp vét cạn thì lại có nhƣợc điểm riêng, mặc dù trên lý thuyết thì có thể cho đƣợc phƣơng án tối ƣu. Nhƣng thực tế vét cạn là xét tất cả mọi khả năng có thể có của nghiệm, từ đó chọn ra nghiệm tối ƣu. Do đó vét cạn chỉ khả thi trong trƣờng hợp bài toán có kích thƣớc dữ liệu nhỏ. Vì vậy có thể nói quy hoạch động giải quyết đƣợc hầu nhƣ tất cả các nhƣợc điểm của các phƣơng pháp trên. 1.4. Các bƣớc thực hiện quy hoạch động 1.4.1. Xây dựng công thức truy hồi Dựa vào nguyên lý tối ƣu tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tƣơng quan quyết định của bƣớc đang xử lý với các bƣớc đã xử lý trƣớc đó. Hoặc tìm cách phân rã bài toán thành các “bài toán con” tƣơng tự có kích thƣớc nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thƣớc đã cho với kết quả của các “bài toán con” cùng kiểu có kích thƣớc nhỏ hơn của nó nhằm xây dựng công thức truy hồi. Về một cách xây dựng công thức truy hồi: Giả sử bài toán mà ta cần tìm là chi phí tối ƣu dạng Max. Gọi Fi là giá trị lớn nhất khi xét đến phần tử thứ i. Tùy theo bài toán, ta có thể nhận ra các bài toán cơ sở của nó một cách rõ ràng và hiển nhiên. Thông thƣờng các giá trị này là F0 hoặc F1 hoặc F2 … Khởi tạo bằng cách gán các giá trị ban đầu cho chúng. Từ các giá trị ban đầu nêu trên, ta tăng dần số lƣợng các phần tử lên (tăng độ lớn của bài toán), tìm điểm chung trong cách tính các phần tử từ bài toán cơ sở (F0 hoặc F1) đến bài toán đang xét (Fi). Từ đó ta có đƣợc công thức truy hồi. Thông thƣờng công thức truy hồi có dạng: Fi = Max(Fi-1, Fi) {với i = 1 ... n} (*) Trong đó - Fi là giá trị lớn nhất khi xét đến phần tử thứ i. - Max là hàm lấy giá trị lớn nhất của 1 trong các đối số của nó. - Fi-1 là bài toán con đã tối ƣu ở bƣớc liền kề trƣớc đó. - Fi-1 cũng đƣợc tính theo công thức Fi-1 = Max(Fi-2, Fi-1) - Và Fi-2 = Max(Fi-3, Fi-2) - … cho đến 7 - F1 - F0 1.4.2. Tổ chức dữ liệu và chương trình Tổ chức dữ liệu sao cho đạt các yêu cầu sau:  Dữ liệu đƣợc tính toán dần theo các bƣớc.  Dữ liệu đƣợc lƣu trữ để giảm lƣợng tính toán lặp lại.  Kích thƣớc miền nhớ dành cho lƣu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu đƣợc chọn phù hợp, nên chọn đơn giản dễ truy cập. Cụ thể  Các giá trị của Fi thƣờng đƣợc lƣu trữ trong một bảng (mảng một chiều hoặc hai, ba chiều, … ).  Cần lƣu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang giải.  Dựa vào công thức (*) và các giá trị đã có trong bảng để tìm dần các giá trị còn lại của bảng.  Ngoài ra còn cần mảng lƣu trữ nghiệm tƣơng ứng với các giá trị tối ƣu trong từng gian đoạn.  Dựa vào bảng lƣu trữ nghiệm và bảng giá trị tối ƣu trong từng giai đoạn đã xây dựng, tìm ra kết quả bài toán. 1.4.3. Làm tốt (tối ưu thuật toán nếu được) Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thƣớc miền nhớ. Thƣờng tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trƣớc. Trong một số trƣờng hợp có thể thay mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0, 1 bởi mảng hai chiều mới bằng cách dùng kỹ thuật xử lý bit. 1.4.4. Truy vết tìm phương án tối ưu Thông thƣờng kết quả tối ƣu của một bài toán quy hoạch động là sau khi đã giải đƣợc bài toán sau cùng (bài toán thứ n, hay Fn), nếu bảng phƣơng án là mảng 2 chiều thì hoặc là giá trị tối ƣu (GTTU) nằm ở cột cuối hoặc là GTTU nằm ở dòng cuối. Từ các vị trí chứa các GTTU đó, ta tiến hành truy vết ngƣợc trở về đi qua các bài toán con trƣớc nó cũng đã đạt đƣợc GTTU, cho đến khi trở về bài toán cơ sở ban đầu thì dừng. Vậy để có thể truy vết đƣợc thì ta phải tiến hành đánh dấu tại GTTU của bài toán thứ i mà ta đạt đƣợc. Cụ thể, khi tiến hành cài đặt công thức (*) ở trên, ta phải lƣu vết: 8 If Fi-1 > Fi Then Begin Fi := Fi-1 Lƣu vết {chọn Fi-1} End Else Lƣu vết {không chọn Fi-1} 1.5. Các lớp bài toán quy hoạch động và ứng dụng Chúng ta đều biết rằng điều khó nhất để giải một bài toán quy hoạch động (QHĐ) là biết rằng nó là một bài toán QHĐ và tìm đƣợc công thức QHĐ của nó. Rất khó nếu ta mò mẫm từ đầu, nhƣng nếu chúng ta đƣa đƣợc bài toán cần giải về một bài toán QHĐ kinh điển thì sẽ dễ dàng hơn nhiều. Do đó, tìm hiểu mô hình, công thức và cách cài đặt những bài toán QHĐ kinh điển là một việc rất cần thiết. Trong phần này, tôi xin giới thiệu một số bài toán QHĐ kinh điển và những biến thể của chúng. Phần này chủ yếu tập trung vào giới thiệu mô hình, công thức và một số gợi ý trong cài đặt chứ không đi chi tiết vào việc phát biểu bài toán, mô tả input/output, chứng minh công thức hay viết chƣơng trình cụ thể. [7] 1.5.1. Dạng 1: Dãy con đơn điệu dài nhất 1.5.1.1. Mô hình Cho dãy a1,a2,..an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. 1.5.1.2. Công thức QHĐ Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a 1 đến ai và phần tử cuối cùng là ai. Ta có công thức QHĐ để tính L(i) nhƣ sau: L(1)=1 L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i và aj ≤ ai). 1.5.1.3. Cài đặt Bảng phƣơng án là một mảng một chiều L để lƣu trữ các giá trị của hàm QHĐ L(i). Đoạn chƣơng trình tính các giá trị của mảng L nhƣ sau: for i := 1 to n do begin L[i] := 1; for j:=1 to i - 1 do if (a[j]<=a[i]) and (L[i] ai3 <... hoặc i1 > ai2 < a i3 >... các chỉ số phải cách nhau ít nhất L: i2 - i1 ≥ L, i3 -i2 ≥ L... chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |ai1 - ai2| ≤ U, |ai2 - ai3| ≤ U... Ý tưởng thuật toán: Gọi L(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là ai và phần tử cuối cùng lớn hơn phần tử đứng trƣớc. Tƣơng tự, P(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là ai và phần tử cuối cùng nhỏ hơn phần tử đứng trƣớc. Ta dễ dàng suy ra: L(i) = max(1, P(j)+1): j ≤ i - L và ai - U ≤ aj < ai. P(i) = max(1, L(j)+1): j ≤ i - L và ai < aj ≤ ai + U. 1.5.2. Dạng 2: Chia kẹo 1.5.2. 1. Mô hình Cho dãy a1, a2,.. an. Tìm một dãy con của dãy đó có tổng bằng S. 1.5.2. 2. Công thức Đặt L(i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1,a2,..ai. Ngƣợc lại thì L(i,t)=0. Nếu L(n,S)=1 thì đáp án của bài toán trên là 'có'. Ta có thể tính L(i,t) theo công thức: L(i,t) = 1 nếu L(i - 1,t)=1 hoặc L(i-1,t - a[i])=1. 1.5.2. 3. Cài đặt Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phƣơng án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i -1. Bảng phƣơng án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và đƣợc tính nhƣ sau: L[t]:=0; L[0]:=1; for i := 1 to n do for t := S downto a[i] do if (L[t]=0) and (L[t - a[i]]=1) then L[t]:=1; Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(nm), với m là tổng của n số. 11 1.5.2. 4. Một số bài toán biến thể cùng lớp với bài toán “chia kẹo” a) Bài toán: Chia kẹo Cho n gói kẹo, gói thứ i có ai viên. Hãy chia các gói thành 2 phần sao cho chênh lệch giữa 2 phần là ít nhất. Ý tưởng thuật toán: Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn: S ≤ T/2. Có một dãy con của dãy a có tổng bằng S. Khi đó sẽ có cách chia với chênh lệch 2 phần là T - 2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại. b) Bài toán: Market (Olympic Balkan 2000) Ngƣời đánh cá Clement bắt đƣợc n con cá, khối lƣợng mỗi con là ai, đem bán ngoài chợ. ở chợ cá, ngƣời ta không mua cá theo từng con mà mua theo một lƣợng nào đó. Chẳng hạn 3 kg, 5kg... Ví dụ: có 3 con cá, khối lƣợng lần lƣợt là: 3, 2, 4. Mua lƣợng 6 kg sẽ phải lấy con cá thứ 2 và và thứ 3. Mua lƣợng 3 kg thì lấy con thứ nhất. Không thể mua lƣợng 8 kg. Nếu bạn là ngƣời đầu tiên mua cá, có bao nhiêu lƣợng bạn có thể chọn? Ý tưởng thuật toán: Thực chất bài toán là tìm các số S mà có một dãy con của dãy a có tổng bằng S. Ta có thể dùng phƣơng pháp đánh dấu của bài chia kẹo ở trên rồi đếm các giá trị t mà L[t]=1. c) Bài toán: Điền dấu Cho n số tự nhiên a1,a2,...,an. Ban đầu các số đƣợc đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu '?': a1?a2?...?an. Cho trƣớc số nguyên S, có cách nào thay các dấu '?' bằng dấu + hay dấu - để đƣợc một biểu thức số học cho giá trị là S không? Ý tưởng thuật toán: Đặt L(i,t)=1 nếu có thể điền dấu vào i số đầu tiên và cho kết quả bằng t. Ta có công thức sau để tính L: L(1,a[1]) =1. L(i,t)=1 nếu L(i - 1,t+a[i])=1 hoặc L(i - 1,t - a[i])=1. Nếu L(n,S)=1 thì câu trả lời của bài toán là có. Khi cài đặt, có thể dùng một mảng 2 chiều (lƣu toàn bộ bảng phƣơng án) hoặc 2 mảng một chiều (để lƣu dòng i và dòng i - 1). Chú ý là chỉ số theo t của các mảng phải có cả phần âm (tức là từ - T đến T, với T là tổng của n số), vì trong bài này chúng ta dùng cả dấu - nên có thể tạo ra các tổng âm. Bài này có một biến thể là đặt dấu sao cho kết quả là một số chia hết cho k. Ta có thuật giải tƣơng tự bài toán trên bằng cách thay các phép cộng, trừ bằng các phép cộng và trừ theo môđun k và dùng mảng đánh dấu với các giá trị từ 0 đến k - 1 (là các số dƣ có thể có khi chia cho k). Đáp số của bài toán là L(n,0). d) Bài toán: Expression (ACM 10690)