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