Luận Văn Lập trình ràng buộc với bài toán N-quân hậu

MỤC LỤC

LỜI CẢM ƠN 4

LỜI NÓI ĐẦU 5

PHẦN I. GIỚI THIỆU VỀ LẬP TRÌNH RÀNG BUỘC 7

PHẦN II. NHỮNG CƠ SỞ VỀ BÀI TOÁN THỎA MÃN RÀNG BUỘC 13

CHƯƠNG 1. GIỚI THIỆU NHỮNG KHÁI NIỆM CƠ BẢN 13

1.1. Những định nghĩa quan trọng trong CSP 13

1.1.1. Định nghĩa miền và nhãn 13

1.1.2. Định nghĩa ràng buộc 15

1.1.3. Định nghĩa sự thỏa mãn 15

1.1.4. Định nghĩa bài toán thỏa mãn ràng buộc (CSP) 16

1.2. CSP cho ràng buộc nhị phân 16

1.3. Ví dụ: Bài toán N-quân hậu 17

CHƯƠNG 2. GIẢI BÀI TOÁN THỎA MÃN RÀNG BUỘC 18

2.1. Rút gọn bài toán (Problem redution) 18

2.1.1. Các định nghĩa 18

2.1.2. Việc rút gọn bài toán 19

2.1.3. Bài toán tối thiểu 19

2.2. Tìm kiếm bộ nghiệm 20

2.2.1. Thuật toán quay lui đơn giản (Simple Backtracking) 20

2.2.2. Đặc tính tổng quát của không gian tìm kiếm trong CSPs 21

2.2.3. Kết hợp tìm kiếm và rút gọn bài toán 22

2.2.4. Những điểm chọn trong tìm kiếm 22

2.3. Tổng hợp nghiệm 23

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 24

3.1. Một số thuật toán nhằm rút gọn bài toán 24

3.2. Một số thuật toán nhằm tìm kiếm lời giải cho bài toán 25

PHẦN III. BÀI TOÁN N-QUÂN HẬU 27

CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN 28

1.1. Giới thiệu bài toán 28

1.2. Lịch sử bài toán 31

1.3. Những vấn đề cần giải quyết trong bài toán 31

CHƯƠNG 2. SỰ ĐỐI XỨNG TRONG BÀI TOÁN N-QUÂN HẬU 32

2.1. Sự đối xứng trong bài toán lập trình ràng buộc 32

2.1.1. Định nghĩa sự đối xứng trong CSPs 32

2.1.2. Các phương pháp loại bỏ đối xứng 32

2.2. Sự đối xứng trong bài toán N-quân hậu 34

CHƯƠNG 3. LOẠI BỎ ĐỐI XỨNG CHO BÀI TOÁN N-QUÂN HẬU 39

3.1. Loại bỏ đối xứng trước khi tìm kiếm nghiệm 39

3.1.1. Giới thiệu về hình vuông Latin trực giao 39

3.1.2. Liên hệ bài toán N-quân hậu với hình vuông Latin trực giao 42

3.1.3. Loại bỏ đối xứng bằng phương pháp thêm ràng buộc trước khi tìm kiếm nghiệm 43

3.2. Loại bỏ đối xứng trong khi tìm kiếm nghiệm (Symmetry Breaking During Seach_SBDS) 44

3.2.1. Giới thiệu về phương pháp SBDS 44

3.2.2. Phương pháp SBDS cho bài toán N-quân hậu 45

3.3. Loại bỏ đối xứng nhờ việc nhận ra sự ưu thế (Symmetry Breaking by Dominance Detection_SBDD) 50

3.3.1. Giới thiệu về phương pháp SBDD 50

3.3.2. Phương pháp SBDD với DFS 52

3.3.3. Phương pháp SBDD cho bài toán N-quân hậu 53

3.3.4. So sánh SBDD với SBDS 56

PHẦN IV. KẾT LUẬN 57

TÀI LIỆU THAM KHẢO 59



Lời nói đầu


Ngày nay cùng với sự phát triển không ngừng của nền khoa học kỹ thuật thế giới là sự phát triển vượt bậc của ngành công nghệ thông tin nói chung và ngành Tin học nói riêng.

Ở nước ta nhằm góp phần vào công cuộc Công nghiệp hóa-hiện đại hóa đất nước, vấn đề tin học hóa đã và đang được triển khai.Việc ứng dụng tin học vào thực tế là một nhu cầu rất cần thiết. Nhận thức được điều này nên khi còn trên ghế nhà trường, chúng tôi đã được tìm hiểu qua một số ứng dụng Tin học, cụ thể là việc ứng dụng tin học vào giải quyết một số bài toán ứng dụng.

Để xây dựng một ứng dụng tin học vào giải quyết các bài toán cụ thể, điều đầu tiên là cần nắm được vấn đề đặt ra của bài toán đó. Sau đó ta liên hệ với thực tế xem xét, đưa ra cách thức giải quyết bài toán đó tức là tìm giải thuật tương ứng với vấn đề yêu cầu của bài toán đó. Vì vậy để đạt được hiệu quả cao thì cần tìm những cách thức, giải thuật mới cả chiều sâu và rộng mang tính ưu việt nhất.

Bài toán N-quân hậu trên bàn cờ là một trong những bài toán ứng dụng tin học mà xung quanh nó rất nhiều thuật toán để giải quyết như: thuật toán quay lui, nhánh cận,

Được sự nhất trí của khoa Tin và sự chỉ dẫn của thầy Nguyễn Thanh Tuấn, Chúng tôi đã được nhận đề tài: “Lập trình ràng buộc với bài toán N-quân hậu”. Đề tài này được hoàn thành từ những hiểu biết tích góp qua sách vở, từ những kinh nghiệm học hỏi anh chị đi trước và những tài liệu sẽ được trích dẫn rõ ràng.

Đề tài gồm những nội dung chính sau:

Phần I: Giới thiệu về lập trình ràng buộc

Phần II: Những cơ sở về bài toán thỏa mãn ràng buộc

Chương 1: Giới thiệu những khái niệm cơ bản

Chương 2: Giải bài toán thỏa mãn ràng buộc

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

Phần III: Bài toán N- quân hậu trên bàn cờ

Chương 1: Giới thiệu bài toán

Chương 2: Sự đối xứng trong bài toán N-quân hậu

Chương 3: Loại bỏ đối xứng trong bài toán N-quân hậu

Phần IV: Kết luận


_______________________________________

TÀI LIỆU THAM KHẢO


Tiếng Việt

1. Nguyễn Văn Hậu, luận văn thạc sỹ: Lập trình ràng buộc với bài toán người chơi gôn

Tiếng Anh

1. Cohen D., Jeavons P., Jefferson C., Karen E. P. and Smith B. (2005) “Symmetry Definitions for Constraint Programming”, Proceeding of Principles and Practice of Constraint Programming - CP 2005.

Constraint Programming online, http://www.cp-online.org/

2. Flener P., Frisch A., Hnich B., Kiziltan Z., Miguel I., Walsh T. (2002), “Breaking row and column symmetry in matrix models”, Proceeding of Principles and Practice of Constraint Programming - CP 2002.

3. Gent I.P., and Smith B. (2000), “Symmetry breaking during search in contraint programming”, W. Horn, editor, EACI’2000.

4. Harvey W. (2001), “Symmetry Breaking and the Social Golfer Problem”, Proceedings of SymCon-01: Symmetry in Constraints.

5. Kiziltan Z. (2004), “Symmetry Breaking Ordering Constraints”, PhD thesis, Department of Information Science, Uppsala University.

6. Marriott K., and Stuckey P.J. (1998), Programming with Constraints: An Introduction, MIT Press.

7. Sellmann M., and Van Hentenryck P. (2005), “Structural symmetry breaking”, Proceeding of IJCAI'05 workshop on Modelling and Solving Problems with Constraints.

8. Puget J.F. (2005), “Breaking symmetries in all different problems”, Proceeding of 19th IJCAI (2005), pp. 272-277.