Luận văn: Lập trình ràng buộc với bài toán người chơi gôn

Lập trình ràng buộc là một trong những phát triển thú vị và mạnh mẽ nhất của ngôn ngữ lập trình trong thập kỷ gần đây .Được xây dựng trên cơ sở lý thuyết toán học vững chắc , nó đang phát triển và đặc biệt là nó cũng đang thu hút sự quan tâm mạnh mẽ trong việc áp dụng vào lĩnh vực thương mại , nó trở thành phương pháp mô hình hóa cho nhiều loại bài toán tối ưu , cụ thể là trong các ràng buộc có sự hỗn tạp và các bài toán tìm kiếm...
Nội dung trích xuất từ tài liệu:
Luận văn: Lập trình ràng buộc với bài toán người chơi gôn BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI -------------------------------------- LUẬN VĂN THẠC SỸ KHOA HỌC LẬP TRÌNH RÀNG BUỘC VỚI BÀI TOÁN NGƯỜI CHƠI GÔN NGHÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ: NGUYỄN VĂN HẬU Người hướng dẫn khoa học: PGS. TS. NGUYỄN THANH THUỶ TS. FRANCISCO AZEVEDO HÀ NỘI 2006 1 MỤC LỤC LỜI NÓI ĐẦU .......................................................................................................4 KÍ HIỆU VÀ Ý NGHĨA CÁC TỪ VIẾT TẮT......................................................6 PHẦN I. GIỚI THIỆU VỀ LẬP TRÌNH RÀNG BUỘC ................................8 PHẦN II. NHỮNG CƠ SỞ VỀ BÀI TOÁN THỎA MÃN RÀNG BUỘC ....................18 CHƯƠNG 1. GIỚI THIỆU NHỮNG KHÁI NIỆM CƠ BẢN ....................... 18 1.1. Những định nghĩa quan trọng trong CSP ........................................... 18 1.1.1. Định nghĩa miền và nhãn ............................................................ 18 1.1.2. Định nghĩa ràng buộc .................................................................. 20 1.1.3. Định nghĩa sự thỏa mãn .............................................................. 21 1.1.4. Định nghĩa bài toán thỏa mãn ràng buộc (CSP): ........................ 22 1.1.5. Nhiệm vụ trong bài toán CSP...................................................... 23 1.2. CSP cho ràng buộc nhị phân .............................................................. 24 1.3. Một vài ví dụ ...................................................................................... 24 1.3.1. Bài toán N-quân hậu.................................................................... 24 1.3.2. Bài toán SEND+MORE=MONEY ............................................. 25 CHƯƠNG 2. GIẢI BÀI TOÁN THỎA MÃN RÀNG BUỘC.................... 27 2.1. Rút gọn bài toán (Problem redution).................................................. 27 2.1.1 Các định nghĩa............................................................................. 27 2.1.2 Việc rút gọn bài toán: .................................................................. 28 2.1.3 Bài toán tối thiểu ......................................................................... 29 2.2. Tìm kiếm bộ nghiệm .......................................................................... 30 2.2.1 Thuật toán quay lui đơn giản (Simple Backtracking) ................. 30 2.2.2 Không gian tìm kiếm của CSPs .................................................. 32 2.2.3 Đặc tính tổng quát của không gian tìm kiếm trong CSPs ........... 34 2.2.4 Kết hợp tìm kiếm và rút gọn bài toán ......................................... 35 2.2.5 Những điểm chọn trong tìm kiếm ............................................... 35 CHƯƠNG 3. THUẬT TOÁN NHẰM RÚT GỌN VÀ TÌM KIẾM LỜI GIẢI CHO BÀI TOÁN.............................................................................................. 40 3.1. Một số thuật toán nhằm rút gọn thuật toán. ....................................... 40 3.2. Một số thuật toán nhằm tìm kiếm lới giải cho bài toán...................... 41 PHẦN III. BÀI TOÁN NGƯỜI CHƠI GÔN ...............................................43 Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn 2 CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN...................................................... 44 1.1. Giới thiệu............................................................................................ 44 1.2. Những vấn đề cần giải quyết trong bài toán....................................... 46 1.3. Sự đối xứng trong bài toán lập trình ràng buộc.................................. 46 1.3.1. Định nghĩa sự đối xứng trong CSPs............................................ 46 1.3.2. Các phương pháp loại bỏ đối xứng ............................................. 48 1.4. Sự đối xứng trong SGP ...................................................................... 49 CHƯƠNG 2. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH TRONG BÀI TOÁN SGP ............................................................................................... 51 2.1 Loại bỏ đối xứng tĩnh cơ bản ............................................................. 51 2.2 Loại bỏ đối xứng tĩnh bằng kỹ thuật hạn chế miền (ND) .................. 53 2.3 Loại bỏ đối xứng tĩnh bằng kỹ thuật cố định một số tay gôn ............ 55 CHƯƠNG 3. CÁC MÔ HÌNH CÙNG PHƯƠNG PHÁP GIẢI SGP.............. 56 3.1 Mô hình dùng biến tập........................................................................ 56 3.2 Mô hình dùng biến nguyên................................................................. 57 3.3 Mô hình kết hợp giữa biến tập và biến nguyên.................................. 58 3.4 Mô hình AMPL .................................................................................. 60 CHƯƠNG 4. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP THÊM RÀNG BUỘC TRONG THỜI GIAN TÌM KIẾM CHO SGP ..................................... 62 4.1 Phương pháp SBDS........................................................................... 62 4.1.1 Giới thiệu SBDS.......................................................................... 62 4.1.2 SBDS cho SGP............................................................................ 65 4.2 Phương pháp SBDD .......................................................................... 66 4.2.1 Giới thiệu SBDD ......................................................................... 66 4.2.2 SBDD với DFS.............. ...