- NGUYỄN QUỲNH TRANG HƢỚNG TIẾP CẬN QUY HOẠCH RÀNG BUỘC TRONG VIỆC GIẢI CÁC BÀI TOÁN TỐI ƢU TỔ HỢP: LÝ THUYẾT VÀ CÁC CÔNG CỤ LUẬN VĂN THẠC SĨ KỸ THUẬT. - NGUYỄN QUỲNH TRANG HƢỚNG TIẾP CẬN QUY HOẠCH RÀNG BUỘC TRONG VIỆC GIẢI CÁC BÀI TOÁN TỐI ƢU TỔ HỢP: LÝ THUYẾT VÀ CÁC CÔNG CỤ Chuyên ngành : Kỹ thuật máy tính và Truyền thông LUẬN VĂN THẠC SĨ KỸ THUẬT. - 8 CHƢƠNG I: QUY HOẠCH RÀNG BUỘC. - Bài toán thỏa mãn ràng buộc (CSP. - Ví dụ CSP. - Dùng các ràng buộc để tỉa không gian tìm kiếm. - Tìm kiếm quay lui. - Ví dụ. - Chiến lƣợc tìm kiếm. - Ràng buộc (Constraint. - Ràng buộc nhị phân (Binary Constraint. - Ràng buộc cho 3 biến (Ternary Constraint. - Ràng buộc kênh (Channeling Constraints. - Ràng buộc cụ thể hóa (Reified Constrants. - Ràng buộc chung (Global constraint. - Ràng buộc đọc. - Ví dụ về các bài toán đƣợc giải quyết bằng Choco. - Ví dụ 1: Bài toán con hậu N-Queens. - Ví dụ 2: Bài toán Magic square. - 48 CHƢƠNG 3: ÁP DỤNG THƢ VIỆN CHOCO VÀO BÀI TOÁN ỨNG DỤNG: “XẾP LỊCH HỌC CHO CÁC LỚP CAO HỌC BÁCH KHOA. - Phát biểu bài toán. - 61 6 BẢNG CÁC KÝ HIỆU VIẾT TẮT BẢNG CÁC THUẬT NGỮ CHUYÊN NGÀNH Các thuật ngữ Ý nghĩa Constraint satisfaction problem Bài toán thỏa mãn ràng buộc Constraint programming Quy hoạch ràng buộc Backtracking Quay lui Search tree Cây tìm kiếm Constraint propagation Lan truyền ràng buộc Branching Phân nhánh Application Programming Interface Giao diện lập trình ứng dụng Ký hiệu Từ viết tắt CSP Constraint satisfaction problem CP Constraint programming AC Arcs consistency API Application Programming Interface 7 DANH SÁCH HÌNH VẼ ĐƢỢC SỬ DỤNG Hình 2-1: Ví dụ về bài toán thỏa mãn ràng buộc Hình 2-2: Thuật toán AC3 Hình 2-3: Cây tìm kiếm Hình 2-4: Các kiểu phân nhánh Hình 2-5: Phương pháp first-fail trong lập trình Comet Hình 3-1: Các cách khai báo biến IntegerVariable trong thư viện Choco. - Hình 3-2: Bài toán khai báo biến RealVariable Hình 3-3: Bài toán khai báo biến SetVariable Hình 4-1: Dữ liệu đầu vào của bài toán 8 MỞ ĐẦU Ngày nay với sự phát triển mạnh mẽ của Công Nghệ thông tin góp phần mang lại những thành tựu rực rỡ cho các lĩnh vực, hoạt động trong đời sống và trong xã hội. - Đóng góp quan trọng vào sự phát triển và ứng dụng CNTT, ngôn ngữ lập trình ràng buộc trong thư viện Choco thật sự mang lại tiện ích lớn trong việc giải quyết các bài toán tối ưu tổ hợp như lập lịch, lập kế hoạch. - Lý do chọn đề tài Trong lĩnh vực nghiên cứu khoa học máy tính, các bài toán về tối ưu tổ hợp được đánh giá là các bài toán khó NP[1, 6], đặc trưng bởi bộ dữ liệu lớn, các ràng buộc phức tạp. - Trên thế giới có rất nhiều những công trình nghiên cứu, các thuật toán được ứng dụng và phát triển để giải quyết vấn đề này: các thuật toán quay lui, vét cạn, các thuật toán về quy hoạch động. - Do đó, đây vẫn là bài toán khó chưa có lời giải tối ưu nhất. - Trong những năm gần đây, Quy hoạch ràng buộc nổi (Constraint Programming - CP) nổi lên như một công nghệ quan trọng, giải quyết hiệu quả các bài toán tối ưu tổ hợp, ứng dụng thành công trong nhiều lĩnh vực: hàng không, khoa học máy tính, công nghệ sản xuất … CP thực sự là một giải pháp tối ưu, được giới chuyên môn đánh giá cao về khả năng giải quyết các vấn đề phức tạp trong cuộc sống thực tế. - Mục đích nghiên cứu của luận văn, đối tƣợng, phạm vi nghiên cứu Mục đích: Tìm hiểu cơ sở lý thuyết và các công cụ hướng tiếp cận quy hoạch ràng buộc để giải các bài toán tối ưu tổ hợp. - 9 Đối tượng: Tìm hiểu một thư viện (Choco) hỗ trợ việc mô hình hóa và giải các bài toán tối ưu tổ hợp bằng quy hoạch ràng buộc. - Chƣơng 1: Tìm hiểu về bài toán tối ưu tổ hợp (CSP) với hướng tiếp cận quy hoạch ràng buộc (CP). - Trong chương này chúng tôi trình bày định nghĩa về bài toán tối ưu tổ hợp và quy hoạch ràng buộc, đưa ra các ví dụ minh họa về bài toán này. - Chúng tôi nêu ra cách thức để giải bài toán tối ưu tổ hợp hướng tiếp cận quy hoạch ràng buộc Chƣơng 2: Ở chương 2 chúng tôi tập trung vào tìm hiểu công cụ để giải bài toán thỏa mãn ràng buộc. - Trong luận văn này chúng tôi tìm hiểu về thư viện Choco. - Chƣơng 3:Từ những kiến thức tìm hiểu về thư viện Choco, trong chương này chúng tôi tập trung áp dụng để giải bài toán trong thực tế. - Ở đây chúng tôi xây dựng bài toán ứng dụng. - Qua việc xây dựng chương trình, em đã nắm bắt được: cách thức để giải quyết các ràng buộc trong bài toán tối ưu tổ hợp và cách viết một chương trình để thực thi công việc trên thư viện Choco. - 10 Sử dụng phần mềm Eclipse, thư viện Choco áp dụng giải một bài toán tối ưu tổ hợp cụ thể: Bài toán xếp lịch học cho các lớp cao học Bách Khoa. - Nội dung: Chƣơng 1: Quy hoạch ràng buộc. - Chƣơng 2: Thư viện Choco Chƣơng 3: Áp dụng thư viện Choco vào bài toán ứng dụng:“ Xếp lịch học cho các lớp cao học Bách Khoa” 11 CHƢƠNG I: QUY HOẠCH RÀNG BUỘC 1.1. - Bài toán thỏa mãn ràng buộc (CSP) 1.1.1. - Định nghĩa: Định nghĩa cổ điển về bài toán thỏa mãn ràng buộc như sau. - Một bài toán CSP gồm 3 thành phần (X,D,C) trong đó. - D là miền giá trị (Domains): D = (D1,D2. - Dn), là tập hợp các giá trị mà biến X có thể nhận. - C là ràng buộc (Constraints): C = (C1,C2. - Ct) là một tập hợp các ràng buộc. - Ví dụ 1: Bài toán con hậu N-Queens Cho bàn cờ kích thước n*n có n con hậu. - Variables: X = {Xi | i [1,n]} một biến là đại diện cho một cột và ràng buộc mỗi con hậu phải trên một cột khác nhau. - Constraints: là tập hợp các ràng buộc: o Hai con hậu không cùng nằm trên hàng: Xi Xj i j n o Hai con hậu không cùng nằm trên một đường chéo: Xi – i Xj – j i j n Xi + i Xj + j i j n 12 - Ví dụ 2: Bài toán Magic Square Cho các số nguyên dương từ 1 đến 2n. - Quy hoạch ràng buộc: 1.2.1. - Tổng quan Quy hoạch ràng buộc (Constraint Programming - CP) là một hướng tiếp cận mạnh để giải các bài toán tối ưu tổ hợp. - CP đã được áp dụng trong việc giải nhiều bài toán tối ưu kinh điển như lập lịch (Scheduling) [1], lập thời khóa biểu (TimeTabling) [8], lập tuyến điều hành xe (Vehicle Routing) [9], phân công ca trực (Nurse Rostering) [10. - CP là sự kết hợp giữa hai thành phần cơ bản là tỉa không gian tìm kiếm (Constraint Propagation) và phân nhánh (Branching). - Tỉa không gian tìm kiếm là cơ chế sử dụng các ràng buộc của bài toán để loại bỏ bớt các giá trị không phù hợp trong miền giá trị của các biến mô hình bài toán. - Sử dụng các ràng buộc để tỉa không gian tìm kiếm không đảm bảo tìm ra được lời giải thỏa mãn tất cả các ràng buộc bởi lẽ các ràng buộc được xem xét một cách độc lập với nhau và không có sự tương trợ nhau 13 trong quá trình tỉa miền giá trị của các biến. - Khi đó, chúng ta phải sử dụng các chiến lược phân nhánh để tìm kiếm lời giải. - Việc phân nhánh thông thường là thử lần lượt từng giá trị còn lại trong miền giá trị của một biến nào đó và gán giá trị cho biến đó. - Ví dụ: Hình 2-1: Ví dụ về bài toán thỏa mãn ràng buộc N Biến X = {X1, X2, X3} N Miền: D(x1. - C3: X2 + X3 = 5 Để giải bài toán này đầu tiên chúng ta sẽ sử dụng phương pháp tỉa không gian tìm kiếm dựa vào các ràng buộc. - Sau khi xét ràng buộc C1: X1 X2 ta có thể tỉa được giá trị 4 trong miền D(x1) vì không thỏa mãn ràng buộc. - Tương tự khi xét ràng buộc C2: X1 + X2 = X3, ta có thể tỉa được giá 14 trị 3 vì 3 + 1 = 4 mà giá trị 4 không thuộc miền giá trị của X3. - Tiếp theo ta lại tỉa giá trị 1 của trong miền D(x3) vì không thỏa mãn ràng buộc c2. - Vậy ta có miền giá trị mới của bộ biến là: N D(x1. - 2, 3} Sau khi sử dụng phương pháp tỉa không gian tìm kiếm, ta tiếp tục giải bài toán bằng cách sử dụng các chiến lược phân nhánh. - Với x1 =2 thì miền giá trị của x3 rỗng vì không thỏa mãn ràng buộc c3 do đó loại. - Với x1 = 1 ta loại bỏ được giá trị 3 trong miền D(x2) vì không thỏa mãn ràng buộc c2. - Ta có miền giá trị mới của bộ biến là: N D(x1. - 2, 3} Với miền giá trị mới này ta tiếp tục tìm kiếm bằng cách xét từng biến của x2. - Với x2 = 1 thì miền giá trị D(x3) rỗng vì không thỏa mãn ràng buộc c3. - Ta loại miền giá trị này: D(x1. - Ta xét x2 = 2 khi đó ta tìm được lời giải của bài toán vì các giá trị biến của từng miền đều thỏa mãn cả 3 ràng buộc. - {3} là đáp án của bài toán. - Dùng các ràng buộc để tỉa không gian tìm kiếm 1.2.2.1. - Một bài toán thỏa mãn ràng buộc gồm 3 thành phần N (X, D,C): X = (X1. - D(Xn), D(xi) Z là tập các giá trị của xi. - Ce} là tập các ràng buộc, biến X(cj) X. - I là một lời giải bộ phận(Instantiation) của bài toán thỏa mãn ràng buộc. - I là một bộ giá trị của bộ biến Y = (X1,…,Xk) là tập con của bộ biến X. - Các biến X1 đến Xn của bộ biến X được thay thế bởi các giá trị
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt