Lập trình ràng buộc (Constraint Programming - CP) là một trong những phát
triển thú vịvà mạnh mẽnhất của ngôn ngữlập trình trong thập kỷgần đây[5,
7,10,11,24,28,36,37]. Được xây dựng trên cơsởlý thuyết toán học vững chắc,
nó đang phát triển và đặc biệt là nó cũng đang thu hút sựquan tâm mạnh mẽ
trong việc áp dụng vào lĩnh vực thương mại, nó trởthành phương pháp mô
hình hóa cho nhiều loại bài toán tối ưu, cụthểlà trong các ràng buộc có sự
hỗn tạp và các bài toán tìm kiếm có tính tổhợp.
Lý giải cho sựquan tâm trong CP thật đơn giản. Ngôn ngữlập trình ra đời
sớm là FORTRAN-66, rất gần với cấu trúc vật lý của máy tính. Vì vậy, xu
hướng chính của ngôn ngữlập trình là mang lại sựtựdo cho người lập trình
đối với việc định nghĩa các đối tượng và thủtục tương ứng với các thực thểvà
thao tác trong miền ứng dụng.
Ngôn ngữlập trình hướng đối tượng (Object Oriented Programming
Language) cung cấp một kỹthuật tốt cho việc khai báo các thành phần để
kiểm soát hành vi của thực thểtrong một miền bài toán cụthể. Tuy nhiên,
ngôn ngữlập trình truyền thống, bao gồm ngôn ngữlập trình hướng đối
tượng, cung cấp rất ít sựhỗtrợvới các thực thểmà người lập trình muốn diễn
tảnhững ràng buộcvà những quan hệ. Người lập trình mong muốn vai trò
của ngôn ngữ đểduy trì những quan hệvà tìm ra những đối tượng thỏa mãn.
Ví dụ, xét định luật Ôm sau:
U=I x R,
Công thức mô tảmối quan hệgiữa hiệu điện thế, cường độdòng điện và điện
trở. Trong ngôn ngữlập trình truyền thống, người lập trình không thểdùng
quan hệnày một cách trực tiếp, thay vào đó nó phải được mã hóa thành câu
9
Luận văn thạc sĩLập trình ràng buộc và bài toán người chơi gôn
lệnh mà từ đó việc tính toán giá trịcủa một thành phần dựa trên 2 thành tố
còn lại. Vì vậy, I có thể được suy ra từU và R bằng công thức sau:
I:= U/R,
Nhưng nếu giá trịcủa được tính từhai thành phần còn lại, một công thức khác
lại phát sinh:
R:= U/I,
Việc đòi hỏi người lập trình mô tảvà duy trì các quan hệgiữa các đối tượng
trong lập trình là hợp lý cho các ứng dụng có sửdụng. Tuy nhiên trong nhiều
ứng dụng, vấn đềquan trọng là mô hình các quan hệvà tìm ra các đối tượng
thỏa mãn. Vì lý do đó mà từcuối những năm 60, đã có nhiều chuyên gia quan
tâm đến các ngôn ngữlập trình cho phép người lập trình đơn giản hóa các
quan hệgiữa các trạng thái của đối tượng. Nó là vai trò thực thi cơbản nhằm
đảm bảo rằng những quan hệ đó hay những ràng buộc được duy trì. Những
ngôn ngữnhưvậy được coi là ngôn ngữCP (Constraint Programming).
