Ktl-icon-tai-lieu

Lập trình ràng buộc với bài toán Nquân hậu.

Được đăng lên bởi dinhthuy218
Số trang: 56 trang   |   Lượt xem: 3034 lần   |   Lượt tải: 4 lần
ĐẠI HỌC ĐÀ NẴNG
TRƢỜNG ĐẠI HỌC SƢ PHẠM
KHOA TIN
-------  -------

Đề tài:

Lập trình ràng buộc với bài toán Nquân hậu.

KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN KHOA HỌC
GVHD : Nguyễn Thanh Tuấn
SVTH : Nguyễn Thị Thu Hà
Đà Nẵng năm:2012

1

MỤC LỤC
LỜI CẢM ƠN ..................................................................................................... 3
LỜI NÓI ĐẦU ............................................................................................................ 4
PHẦN I. GIỚI THIỆU VỀ LẬP TRÌNH RÀNG BUỘC .............................................. 6
PHẦN II. NHỮNG CƠ SỞ VỀ BÀI TOÁN THỎA MÃN RÀNG BUỘC ................. 12
CHƢƠNG 1. GIỚI THIỆU NHỮNG KHÁI NIỆM CƠ BẢN .............................. 12
1.1.

Những định nghĩa quan trọng trong CSP .............................................. 12
1.1.1.

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

1.1.2.

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

1.1.3.

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

1.1.4.

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

1.2. CSP cho ràng buộc nhị phân ................................................................... 15
1.3. Ví dụ: Bài toán N-quân hậu .................................................................... 15
CHƢƠNG 2. GIẢI BÀI TOÁN THỎA MÃN RÀNG BUỘC .............................. 17
2.1.

2.2.

2.3.

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

Các định nghĩa .......................................................................... 17

2.1.2.

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

2.1.3.

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

Tìm kiếm bộ nghiệm ............................................................................ 18
2.2.1.

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

2.2.2.

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

2.2.3.

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

2.2.4.

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

Tổng hợp nghiệm ................................................................................. 21

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 .......
1
ĐẠI HỌC ĐÀ NẴNG
TRƢỜNG ĐẠI HỌC SƢ PHẠM
KHOA TIN
------- -------
Đề i:
Lập trình ràng buộc với bài tn N-
quân hu.
KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN KHOA HỌC
GVHD : Nguyn Thanh Tuấn
SVTH : Nguyn ThThu Hà
Đà Nẵng năm:2012
Lập trình ràng buộc với bài toán Nquân hậu. - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Lập trình ràng buộc với bài toán Nquân hậu. - Người đăng: dinhthuy218
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
56 Vietnamese
Lập trình ràng buộc với bài toán Nquân hậu. 9 10 358