i ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Thùy
ỨNG DỤNG NGÔN NGỮ LẬP TRÌNH RÀNG BUỘC
COMET VÀO BÀI TOÁN
LẬP THỜI KHÓA BIỂU
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin

Hà Nội – 2010

ii ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

Em cũng xin chân thành cảm ơn Ban Giám hiệu trường Đại học Công nghệ
cùng quí thày cô trong Khoa công nghệ thông tin đã tạo điều kiện để em học tập
và hoàn thành tốt khóa học.
Trong khóa luận không thể tránh khỏi những thiếu sót. Em rất mong nhận
được được những đóng góp quí báu của thày cô và các bạn để khóa luận được
hoàn thiện hơn. Hà Nội, tháng 5 năm 2010
Sinh viên
Nguyễn Thị Thùy
2

TÓM TẮT KHÓA LUẬN
Lập Thời khóa biểu là công việc cần thiết và quan trọng mà tất cả các tổ
chức giáo dục phải thực hiện nhằm đƣa ra biểu đồ kế hoạch năm học, lịch giảng
dạy và học tập cho giáo viên, học sinh. Trƣớc đây, khi CNTT chƣa đƣợc phát triển
mạnh mẽ và ứng dụng rộng rãi thì công việc này thƣờng đƣợc thực hiện một cách
thủ công trên giấy, tiêu tốn nhiều chi phí, thời gian và công sức.
Bài toán lập Thời khóa biểu tronng trƣờng học là một một trƣờng hợp riêng
của bài toán lập lịch đƣợc xếp vào hàng các bài toán khó chƣa có giải thuật tối ƣu

CHƢƠNG 2: LẬP TRÌNH RÀNG BUỘC 11
2.1. Lập trình ràng buộc là gì? 11
2.2. Nguồn gốc lập trình ràng buộc 11
2.3. Mô hình lập trình ràng buộc 12
2.4. Ứng dụng của ngôn ngữ lập trình ràng buộc (CP) 14
CHƢƠNG 3: NGÔN NGỮ LẬP TRÌNH COMET 16
3.1. COMET là gì? 16
3.2. Lập trình Comet 17
3.2.1. Mô hình lập trình Comet 17
3.2.2. Ví dụ 20
3.3. Ƣu điểm của Comet 23 4

CHƢƠNG 4: ỨNG DỤNG COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU
26
4.1. Đặt vấn đề xây dựng bài toán 26
4.2. Giải quyết bài toán 28
4.3. Thực nghiệm 30
4.3.1. Các chức năng quản lý giảng viên, môn học, phòng học, khoa
31
4.3.2. Chức năng phân công giảng dạy 36
4.3.3. Chức năng xếp Thời khóa biểu 37
4.3.4. Chức năng xem thời khóa biểu theo tên lớp, tên giảng viên, tên
phòng học 38
CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 40
TÀI LIỆU THAM KHẢO 41
LP
Logic Programming BẢNG CÁC THUẬT NGỮ CHUYÊN NGÀNH
Các thuật ngữ
Ý nghĩa
Artificial Intelligence
Trí tuệ nhân tạo
Application Programming Interface
Giao diện lập trình ứng dụng
Constraint Programming
Lập trình ràng buộc
Logic Programming
Lập trình logic
Search
Tìm kiếm
Search Tree
Cây tìm kiếm

6

DANH SÁCH HÌNH ẢNH ĐƢỢC SỬ DỤNG
Hình 1-1. Bài toán 4-Hậu 8
Hình 1-2. Một nhánh trong cây tìm kiếm của bài toán 4-Hậu 9
Hình 2-1. Mô hình CP 12
Hình 2-2. Ứng dụng CP vào phân tích chuỗi protein 15
Hình 3-1. Thành phần tìm kiếm trong Comet 19
Hình 3-2. Code bài toán 16-Hậu bằng Comet 20
Hình 3-3. Kết quả bài toán 16-Hậu bằng Comet 22

và kỹ năng. Trên thế giới có rất nhiều những công trình nghiên cứu, các thuật toán
đƣợc ứng dụng và phát triển để giải quyết vấn đề này: các thuật toán quay lui, vét
cạn, các thuật toán về quy hoạch động. Tuy nhiên, trong lập trình truyền thống
chƣa có giải thuật hiệu quả nhất, đáp ứng đƣợc thời gian xử lý là đa thức. Do đó,
đây vẫn là bài toán khó chƣa có lời tối ƣu nhất.
Trong những năm gần đây, CP nổi lên nhƣ một công nghệ quan trọng, giải
quyết hiệu quả các bài toán tối ƣu hóa tổ hợp, ứng dụng thành công trong nhiều
lĩnh vực: hàng không, khoa học máy tính, công nghiệp sản xuất…CP thực sự là
một giải pháp tối ƣu, đƣợc giới chuyên môn đánh giá cao về khả năng giải quyết
các vấn đề phức tạp trong cuộc sống thực thế.
Dƣới đây, ta sẽ xét bài toán N-Hậu trong lập trình truyền thống với giải
thuật vét cạn, quay lui.
Bài toán N-Hậu
Bài toán 4-queens là bài toán đặt 4 quân hậu trên bàn cờ vua kích thƣớc 4*4
sao cho không có quân hậu nào có thể “ăn” đƣợc quân hậu khác, hay nói cách khác
không quân hậu nào có thể di chuyển theo quy tắc cờ vua. Do đó, lời giải của bài
8

toán là một cách xếp bốn quân hậu trên bàn cơ vua sao cho không có hai quân nào
đứng trên cùng hàng, hoặc cùng cột hoặc cùng đƣờng chéo.

Hình 1-1. Bài toán 4-Hậu
Đây là bài toán tổ hợp kinh điển, có nhiều giải thuật: quay lui, vét cạn, quy
hoạch động. Tuy nhiên, độ phức tạp của các thuật toán này thƣờng là Chƣa có
giải thuật thỏa mãn thời gian chạy là đa thức. Dƣới đây, ta xét bài toán này trong
môi trƣờng lập trình truyền thống ( bằng ngôn ngữ lập trình C/C++ hoặc Java )
với giải thuật vét cạn, quay lui (gọi đệ quy). Tƣ tƣởng cơ bản của giải thuật vét
cạn, quay lui là ta thử đặt một quân cờ vào một ô trong bàn cơ, sau đó lần lƣợt đặt
từng quân cơ tiếp theo vào các ô cờ khác. Trong trƣờng hợp không thỏa mãn điều
kiện ràng buộc của bài toán (Không có hai quân cờ nào “ăn” đƣợc nhau) thì quay

 Chƣơng 3: Ngôn ngữ lập trình Comet
 Chƣơng 4: Áp dụng Comet vào bài toán ứng dụng “Lập thời khóa
biểu” cho trường đại học
 Chƣơng 5: Kết luận và hướng phát triển. 11

CHƢƠNG 2
LẬP TRÌNH RÀNG BUỘC
Trong một vài năm gần đây, lập trình ràng buộc (CP) đã thu hút sự chú ý
một số lƣợng lớn các chuyên gia CNTT vì khả năng giải quyết các vấn đề khó
khăn trong thực tế. Theo [5] CP đƣợc ACM (Association for Computing Achinery)
nhận định là một trong những hƣớng chiến lƣợc trong nghiên cứu tin học. Tuy
nhiên CP vẫn là một trong những công nghệ ít đƣợc biết đến và hiểu rõ.

programming (1980s) , concurrent constraint programming(1990s). Và hiện nay,
Comet đƣợc đánh giá là ngôn ngữ lập trình ràng buộc có ƣu thế nổi bật nhất.
Chúng ta sẽ tìm hiểu ngôn ngữ lập trình Comet trong chƣơng tiếp theo.
2.3. Mô hình lập trình ràng buộc
CP = Model + Search
Hình 2-1. Mô hình CP[3]

Bản chất của CP là kiến trúc hai thành phần: một mô hình lƣu trữ ràng
buộc và mô hình tìm kiếm. Mô hình lƣu trữ ràng buộc là tập hợp các ràng buộc mô
tả thuộc tính của biến, các mối liên quan, ràng buộc của biến trên miền giá trị, là
một hệ thống lý luận về các thuộc tính cơ bản của hệ thống ràng buộc. Mô hình lƣu
trữ ràng buộc chứa đựng các ràng buộc đã tích lũy tại một số bƣớc tính toán, hỗ trợ
13

các truy vấn và toán tử thực hiện trên trên nó. Thành phần tìm kiếm trong CP là
duyệt cây với thuật toán backtracking, về bản chất giống nhƣ phƣơng pháp tìm
kiếm nhánh và cận của lập trình truyền thống.
Bài toán: SEND + MORE = MONEY
Để hiểu rõ thêm về các ràng buộc, chúng ta hãy xét một bài toán chơi chữ
cổ điển của Henry Dudeney công bố trên tạp chí Strand năm 1924[10].
Phƣơng trình của bài toán

Mỗi ký tự đại diện cho một con số khác sau, các chữ số hàng đầu của một
số nhiều hơn một chữ số phải là những số khác không. Và một lời giải đúng là tìm
ra giá trị số tƣơng ứng cho từng ký tự và thỏa mãn phƣơng trình trên.
Ở đây. Chúng ta sẽ đề cập đến một phƣơng pháp, áp dụng lập trình ràng
buộc vào giải quyết bài toán.
Code bài toán
sendmore(Digits) :-
Digits = [S,E,N,D,M,O,R,Y], % Khởi tạo biến

mẽ, các doanh nghiệp tổ chức thƣơng mại không ngừng ra đời và phát triển lớn
mạnh. Bên cạnh đó, khoa học kỹ thuật công nghệ thu đƣợc những thành tựu rực rỡ,
đem đến những công nghệ tiên tiến nhất và hàng loạt công nghệ, kỹ thuật đƣợc
ứng dụng rộng rãi và thành công trong các ngành kinh tế, thƣơng mại, góp phần
thúc đẩy sự tăng trƣởng kinh tế. Xu hƣớng hiện nay, các ngành công nghiệp, các
lĩnh vực hoạt động sản xuất ứng dụng công nghệ CP ngày càng tăng lên nhanh
chóng. Số lƣợng các công ty ứng dụng thành công công nghệ này tăng lên hàng
năm, có thể kể tên một số công ty, tổ chức điển hình: sân bay Quốc tế Hong Kong,
British Airway, SAS, Swissair, cảng Quốc tế Hong Kong, Michelin, Dassault,
Ericsson[5] … Đối với lĩnh vực hàng không, CP đƣợc ứng dụng để lập lịch các
chuyến bay, hoạt động chuyển phát nhanh…Trong công nghiệp sản xuất, CP ứng
dụng trong việc quản lý chuỗi cung ứng sản xuất, lập lịch, phẩn bổ tài nguyên,
nguồn lực …
15

Không chỉ đƣợc ứng dụng thành công trong các ngành kinh tế, công nghệ
CP còn đƣợc ứng dụng thành công trong các lĩnh vực khác nhƣ:
- Lĩnh vực khoa học máy tính: Đồ họa máy tính (thể hiện gắn kết hình học
trong phân tich phối cảnh), xử lỹ ngôn ngữ tự nhiên (phân tích cú pháp), hệ
thống cơ sở dữ liệu (bảo đảm/phục hồi tính nhất quán của dữ liệu) …
- Lĩnh vực đời sống, sinh hoạt: Lập thời gian biểu, lập lịch…
- Lĩnh vực sinh học: phân tích phân tử sinh học (chuỗi DNA-protein)…
Kỹ thuật lập trình ràng buộc có thể sử dụng hiệu quả để dự đoán cấu trúc
của một phân tử protein, đƣợc coi là vấn đề quan trọng nhất trong tin sinh học. Hình 2-2. Ứng dụng CP vào phân tích chuỗi protein

tìm kiếm địa phƣơng dựa trên ràng buộc, giải quyết lập trình ràng buộc, giải quyết
lập trình toán học.

17

3.2. Lập trình Comet
3.2.1. Mô hình lập trình Comet
Cấu trúc chung của chƣơng trình code bởi comet[8]
import cotfd:
Solver <CP> cp ();
// khai báo biến
solver <cp>{
// post các ràng buộc
} using {
// Tìm kiếm
}

Cấu trúc chung của chƣơng trình code comet gồm 3 phần: phần khai báo
các biến, phần đƣa ra các ràng buộc (constraint) và phần tìm kiếm (constraint-
based local search)
 Khai báo biến (variables)
Trong cấu trúc chƣơng trình Comet, khi khai báo biến là biến ràng buộc
phải khai báo kèm theo tập xác định của biến. Có thể khai báo biến theo cấu trúc
sau:
Ví dụ: Khai báo một biến nguyên có miền giá trị [1, 10]
var <CP> {int} x (cp,1 10);
Hoặc
set {int} dom = {1,3,7};
var <CP> {int} y (cp,dom);
18

Chức năng
alldifferent
Ràng buộc tất cả các biến phải khác
nhau
binaryKnapsack
Ràng buộc tổng khối lƣợng các danh
mục
cardinality
Ràng buộc về số lần xuất hiện của
mỗi giá trị
Table
Ràng buộc tuples hợp lệ
 Tìm kiếm (Search)
Cũng giống nhƣ mô hình Search trong CP, Search trong Comet gồm hai
thành phần: Duyệt cây (Search Tree) và chiến lƣợc tìm kiếm (strategy). Tuy nhiên,
tìm kiếm trong mô hình của lập trình ràng buộc là cách thức duyệt cây không đơn
định với một thuật toán tìm kiếm backtracking ( mặc định của thuật toán duyệt
cây là tìm kiếm theo độ sâu) còn tìm kiếm trong Comet có thể là đơn định, tại mỗi
nút của cây tìm kiếm bạn thể kiếm soát những nhánh cây con dƣới cái nút đó.

Hình 3-1. Thành phần tìm kiếm trong Comet

20

3.2.2. Ví dụ
Bài toán: 16-Hậu
Bài toán 16-Hậu chỉ là mở rộng hơn của bài toán 4-Hậu, điều kiện ràng
buộc của hai bài toán là nhƣ nhau. Ở chƣơng mở đầu, ta đã xét bài toán 4-Hậu
trong lập trình truyền thống với giải thuật vét cạn và quay lui. Trong chƣơng này,
ta sẽ xét bài toán 16-Hậu với ngôn ngữ lập trình ràng buộc Comet để thấy đƣợc

Cấu trúc chƣơng trình Comet phân rõ mô hình hai thành phần: phần đƣa ra
các ràng buộc nằm trong khối lệnh solver<cp>{} và phần tìm kiếm lời giải nằm
trong khối lệnh using {}. Chƣơng trình Comet rất đơn giản, chúng ta chỉ đƣa ra
các ràng buộc của bài toán và điều kiện tìm kiếm mà không cần quan tâm chƣơng
trình sẽ tìm kiếm nhƣ thế nào. Đó là một thế mạnh của ngôn ngữ lập trình Comet.
Bên cạnh đó, sự phân chia rõ từng thành phần giúp cho ngƣời lập trình dễ dàng
thêm bớt các ràng buộc mà không ảnh hƣởng gì đến sự vận hành chƣơng trình.
22

Lời giải của bài toán

Hình 3–3. Kết quả bài toán 16 – queens bằng Comet
Công cụ lập trình Comet hiện nay hay đƣợc sử dụng là Comet Studio. Đây là kết
quả bài toán sắp xếp 16 quân hậu trên bàn cờ 16*16 nhƣ đã nêu ở trên. Kết quả
của chƣơng trình là các mảng một chiều 2 chiều với các số 0 và 1. Số 1 biểu thị vị
trí có thể đặt quân hậu trên bàn cờ. Số 0 là vị trị không đƣợc phép đặt quân hậu.

23

3.3. Ƣu điểm của Comet
 Là ngôn ngữ lập trình hƣớng đối tƣợng có cấu trúc gần giống ngôn ngữ lập