Luận văn 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 .4KÍ HIỆU VÀ Ý NGHĨA CÁC TỪVIẾT TẮT.6PHẦN I. GIỚI THIỆU VỀLẬP TRÌNH RÀNG BUỘC .8PHẦN II. NHỮNG CƠSỞVỀBÀI TOÁN THỎA MÃN RÀNG BUỘC.18CHƯƠNG 1. GIỚI THIỆU NHỮNG KHÁI NIỆM CƠBẢN . 181.1. Những định nghĩa quan trọng trong CSP . 181.1.1. Định nghĩa miền và nhãn . 181.1.2. Định nghĩa ràng buộc . 201.1.3. Định nghĩa sựthỏa mãn . 211.1.4. Định nghĩa bài toán thỏa mãn ràng buộc (CSP): . 221.1.5. Nhiệm vụtrong bài toán CSP. 231.2. CSP cho ràng buộc nhịphân . 241.3. Một vài ví dụ. 241.3.1. Bài toán N-quân hậu. 241.3.2. Bài toán SEND+MORE=MONEY . 25CHƯƠNG 2. GIẢI BÀI TOÁN THỎA MÃN RÀNG BUỘC. 272.1. Rút gọn bài toán (Problem redution). 272.1.1 Các định nghĩa. 272.1.2 Việc rút gọn bài toán: . 282.1.3 Bài toán tối thiểu . 292.2. Tìm kiếm bộnghiệm . 302.2.1 Thuật toán quay lui đơn giản (Simple Backtracking) . 302.2.2 Không gian tìm kiếm của CSPs . 322.2.3 Đặc tính tổng quát của không gian tìm kiếm trong CSPs . 342.2.4 Kết hợp tìm kiếm và rút gọn bài toán . 352.2.5 Những điểm chọn trong tìm kiếm . 35CHƯƠ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 . 403.1. Một sốthuật toán nhằm rút gọn thuật toán. . 403.2. Một sốthuật toán nhằm tìm kiếm lới giải cho bài toán. 41PHẦN III. BÀI TOÁN NGƯỜI CHƠI GÔN .43 CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN. 441.1. Giới thiệu. 441.2. Những vấn đềcần giải quyết trong bài toán. 461.3. Sự đối xứng trong bài toán lập trình ràng buộc. 461.3.1. Định nghĩa sự đối xứng trong CSPs. 461.3.2. Các phương pháp loại bỏ đối xứng . 481.4. Sự đối xứng trong SGP . 49CHƯƠNG 2. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH TRONG BÀI TOÁN SGP . 512.1 Loại bỏ đối xứng tĩnh cơbản . 512.2 Loại bỏ đối xứng tĩnh bằng kỹthuật hạn chếmiền (ND) . 532.3 Loại bỏ đối xứng tĩnh bằng kỹthuật cố định một sốtay gôn . 55CHƯƠNG 3. CÁC MÔ HÌNH CÙNG PHƯƠNG PHÁP GIẢI SGP. 563.1 Mô hình dùng biến tập. 563.2 Mô hình dùng biến nguyên. 573.3 Mô hình kết hợp giữa biến tập và biến nguyên. 583.4 Mô hình AMPL . 60CHƯƠ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 . 624.1 Phương pháp SBDS. 624.1.1 Giới thiệu SBDS. 624.1.2 SBDS cho SGP. 654.2 Phương pháp SBDD . 664.2.1 Giới thiệu SBDD . 664.2.2 SBDD với DFS. 684.2.3 SBDD áp dụng vào SGP . 694.2.4 Kết quảkhi áp dụng SBDD cho SGP . 714.2.5 So sánh SBDS và SBDD. 73CHƯƠNG 5. MỘT SỐPHƯƠNG PHÁP LOẠI BỎ ĐỐI XỨNG ĐỘNG KHÁC CHO SGP . 755.1 Loại bỏ đối xứng với Intelligent-Backtracking (IB) . 755.1.1 Ý tưởng thuật toán. 75 5.1.2 Thuật toán. 775.2 Local Search cho SGP . 795.2.1 Mô hình. 795.2.2 Lân cận (Neighborhood) và thành phần Tabu . 795.2.3 Thuật toán. 80CHƯƠ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 . 816.1 Loại bỏ đối xứng trong SGP bằng nhiều điểm nhìn. 816.1.1 Một sốkhái niệm quan trọng . 816.1.2 Loại bỏ đối xứng bằng phương pháp nhiều “điểm nhìn”. 826.2 Loại bỏ đối xứng bằng hạn chếmiền và cố định một sốtay gôn . 886.3 So sánh với một sốkỹthuật khác. 90CHƯƠ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 . 977.1 Giới thiệu thuật toán. 977.2 Một sốthảo luận cùng kết quảxung quanh thuật toán. 997.3 Liên hệSGP với hình vuông Latin trực giao . 1017.3.1 Giới thiệu hình vuông Latin trực giao. 1017.3.2 Mối liên hệgiữa MOLS và SGP . 1047.3.3 Mối liên hệgiữa SGP và MOLR. 106PHẦN IV. KẾT LUẬN.107TÀI LIỆU THAM KHẢO.

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.