Thạc Sĩ Lập trình ràng buộc với bài toán người chơi gôn

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
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 68
4.2.3 SBDD áp dụng vào SGP . 69
4.2.4 Kết quả khi áp dụng SBDD cho SGP . 71
4.2.5 So sánh SBDS và SBDD . 73
CHƯƠNG 5. MỘT SỐ PHƯƠNG PHÁP LOẠI BỎ ĐỐI XỨNG ĐỘNG
KHÁC CHO SGP . 75
5.1 Loại bỏ đối xứng với Intelligent-Backtracking (IB) 75
5.1.1 Ý tưởng thuật toán . 75
5.1.2 Thuật toán 77
5.2 Local Search cho SGP 79
5.2.1 Mô hình . 79
5.2.2 Lân cận (Neighborhood) và thành phần Tabu 79
5.2.3 Thuật toán 80
CHƯƠNG 6. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH VÀ
THÊM RÀNG BUỘC DƯ THỪA ĐỂ GIẢI SGP . 81
6.1 Loại bỏ đối xứng trong SGP bằng nhiều điểm nhìn . 81
6.1.1 Một số khái niệm quan trọng 81
6.1.2 Loại bỏ đối xứng bằng phương pháp nhiều “điểm nhìn” 82
6.2 Loại bỏ đối xứng bằng hạn chế miền và cố định một số tay gôn 88
6.3 So sánh với một số kỹ thuật khác . 90
CHƯƠNG 7. GIẢI SGP TRONG MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT VÀ
MỐI LIÊN QUAN VỚI CÁC HÌNH VUÔNG LATIN TRỰC GIAO 97
7.1 Giới thiệu thuật toán . 97
7.2 Một số thảo luận cùng kết quả xung quanh thuật toán . 99
7.3 Liên hệ SGP với hình vuông Latin trực giao . 101
7.3.1 Giới thiệu hình vuông Latin trực giao . 101
7.3.2 Mối liên hệ giữa MOLS và SGP . 104
7.3.3 Mối liên hệ giữa SGP và MOLR . 106
PHẦN IV. KẾT LUẬN .107
TÀI LIỆU THAM KHẢO 113