Constraint Satisfaction: bài toán thỏa ràng buộc

Có những bài toán mà câu hỏi đầu tiên không phải là “phương án nào tốt nhất?”, mà là:

Có cách sắp xếp nào thỏa tất cả điều kiện hay không?

Đó là nhóm Constraint Satisfaction Problem - CSP.

1. Ví dụ: xếp lịch thi

Giả sử khoa cần xếp lịch thi cho 5 môn trong 3 ngày. Để dễ đọc, ta ký hiệu:

Mã	Môn
AI	Nhập môn AI
DB	Cơ sở dữ liệu
WEB	Lập trình web
ML	Học máy
SE	Công nghệ phần mềm

Các ngày có thể thi:

\{D2, D3, D4\}

Trong đó D2, D3, D4 lần lượt là Thứ 2, Thứ 3, Thứ 4.

Nếu hai môn có nhiều sinh viên học chung, chúng không được cùng ngày:

Cặp môn	Số sinh viên học chung	Ràng buộc
AI - ML	38	$\mathrm{AI} \ne \mathrm{ML}$
AI - DB	22	$\mathrm{AI} \ne \mathrm{DB}$
DB - WEB	31	$\mathrm{DB} \ne \mathrm{WEB}$
WEB - SE	27	$\mathrm{WEB} \ne \mathrm{SE}$
ML - SE	19	$\mathrm{ML} \ne \mathrm{SE}$
DB - SE	15	$\mathrm{DB} \ne \mathrm{SE}$

Một lịch hợp lệ có thể là:

Môn	Ngày
AI	D2
DB	D3
WEB	D2
ML	D3
SE	D4

Kiểm tra nhanh:

AI khác ML và DB: AI ở D2, ML/DB ở D3.
DB khác WEB và SE: DB ở D3, WEB ở D2, SE ở D4.
WEB khác SE: WEB ở D2, SE ở D4.
ML khác SE: ML ở D3, SE ở D4.

Bài toán này chưa hỏi lịch nào “tốt nhất”; trước tiên chỉ hỏi: có lịch nào thỏa mọi ràng buộc hay không?

2. Ba thành phần của CSP

Một CSP gồm:

Variables - biến

X_1, X_2, \dots, X_n

Ví dụ:

\mathrm{AI}, \mathrm{DB}, \mathrm{WEB}, \mathrm{ML}, \mathrm{SE}

Domains - miền giá trị

Mỗi biến $X_i$ có một miền $D_i$ gồm các giá trị có thể nhận.

Ví dụ:

D_{\mathrm{AI}} = D_{\mathrm{DB}} = D_{\mathrm{WEB}} = D_{\mathrm{ML}} = D_{\mathrm{SE}} = \{D2, D3, D4\}

Constraints - ràng buộc

Quy định tổ hợp giá trị nào được phép.

Ví dụ:

\mathrm{AI} \ne \mathrm{ML}

\mathrm{DB} \ne \mathrm{WEB}

3. Constraint graph

Với các ràng buộc nhị phân, ta có thể biểu diễn CSP thành đồ thị:

Node: biến.
Edge: có ràng buộc trực tiếp giữa hai biến.

Nếu ràng buộc là “khác ngày”, bài toán trở thành một dạng graph coloring: mỗi màu tương ứng một ngày thi.

Nhìn graph giúp ta thấy môn nào “khó”:

DB nối với 3 môn khác, nên nếu chọn sai ngày cho DB, nhiều môn bị ảnh hưởng.
SE cũng nối với 3 môn khác.
AI, WEB, ML nối ít hơn một chút.

Đây là lý do các heuristic ở bài sau thường ưu tiên biến có nhiều ràng buộc hoặc ít lựa chọn còn lại.

4. Hard constraint và soft constraint

Hard constraint

Bắt buộc phải thỏa.

Ví dụ:

Hai môn có sinh viên học chung không được trùng ca.
Một phòng không thể tổ chức hai kỳ thi cùng lúc.

Soft constraint

Không bắt buộc, nhưng dùng để phân biệt lời giải tốt và kém.

Ví dụ:

Hạn chế sinh viên thi hai môn liên tiếp.
Ưu tiên môn đông sinh viên vào ca sáng.

Khi có soft constraints và objective, CSP có thể mở rộng thành một bài toán constraint optimization.

5. Unary, binary và global constraints

Unary constraint

Chỉ liên quan một biến.

Ví dụ:

A \ne Mon

Binary constraint

Liên quan hai biến.

Ví dụ:

A \ne B

Global constraint

Liên quan nhiều biến cùng lúc.

Ví dụ AllDifferent:

AllDifferent(A, B, C, D)

Global constraints thường cho phép solver khai thác cấu trúc tốt hơn so với việc tách thành rất nhiều ràng buộc nhỏ.

6. Node Consistency

Một biến có node consistency khi mọi giá trị còn trong domain đều thỏa các unary constraints của biến đó.

Ví dụ:

D_A = \{Mon, Tue, Wed\}

và:

A \ne Mon

Ta xóa Mon:

D_A = \{Tue, Wed\}

Đây là một dạng constraint propagation: dùng ràng buộc để loại bỏ sớm các giá trị chắc chắn không thể dùng.

7. Arc Consistency

Xét ràng buộc nhị phân giữa $X$ và $Y$ .

$X$ là arc-consistent đối với $Y$ nếu:

Với mọi giá trị $x \in D_X$ , tồn tại ít nhất một giá trị $y \in D_Y$ sao cho cặp $(x,y)$ thỏa ràng buộc giữa $X$ và $Y$ .

Viết gọn:

\forall x \in D_X, \; \exists y \in D_Y: C(X=x, Y=y) = true

Ví dụ

Giả sử:

D_A = \{Tue, Wed\}

D_B = \{Wed\}

và:

A \ne B

Nếu $A=Tue$ , ta có thể chọn $B=Wed$ - hợp lệ.
Nếu $A=Wed$ , không còn giá trị nào cho $B$ - không hợp lệ.

Vì vậy Wed phải bị loại khỏi $D_A$ .

Sau khi revise:

D_A = \{Tue\}

8. Thuật toán REVISE

REVISE(X, Y):
    revised = false

    for mỗi x trong domain(X):
        nếu không tồn tại y trong domain(Y)
        sao cho constraint(X=x, Y=y) đúng:
            xóa x khỏi domain(X)
            revised = true

    return revised

Ý tưởng rất quan trọng:

Không cần đợi đến khi thử một phép gán hoàn chỉnh mới phát hiện sai. Ta có thể loại bỏ các lựa chọn vô vọng từ trước.

9. AC-3

AC-3 áp dụng REVISE lặp lại trên các cung của đồ thị ràng buộc.

AC-3 không nhất thiết giải xong bài toán. Nó chủ yếu thu hẹp domain để search sau đó dễ hơn.

10. Constraint propagation có tác dụng gì?

Nếu mỗi biến ban đầu có 10 giá trị và có 8 biến, số phép gán thô có thể lên tới:

10^8

Nếu propagation làm mỗi domain giảm còn 3 giá trị, không gian thô giảm xuống:

3^8 = 6561

Không phải mọi CSP đều giảm mạnh như vậy, nhưng đây là lý do inference trước khi search rất có giá trị.

11. CSP trong thực tế

Các bài toán phù hợp:

Xếp thời khóa biểu.
Xếp lịch thi.
Phân ca nhân viên.
Sudoku, N-Queens.
Lập lịch máy trong nhà máy.
Phân bổ phòng và tài nguyên.

Các solver hiện đại thường hỗ trợ nhiều dạng ràng buộc mạnh hơn rất nhiều so với ví dụ nhập môn.

OR-Tools, chẳng hạn, cung cấp CP-SAT cho các bài toán rời rạc với biến nguyên và Boolean.

12. Câu hỏi tự kiểm tra

Variable, domain và constraint trong Sudoku là gì?
Tại sao arc consistency là có hướng: $X \rightarrow Y$ không đồng nghĩa hoàn toàn với $Y \rightarrow X$ ?
AC-3 có đảm bảo tìm ra nghiệm hoàn chỉnh không?
Hard constraint và soft constraint khác nhau thế nào?

Tài liệu tham khảo

Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach, 4th ed., Chapter 6: https://aima.cs.berkeley.edu/
Alan K. Mackworth. “Consistency in Networks of Relations.” Artificial Intelligence, 8(1), 1977, 99-118. https://doi.org/10.1016/0004-3702(77)90007-8
Google OR-Tools, Constraint Optimization: https://developers.google.com/optimization/cp
Google OR-Tools, Employee Scheduling example: https://developers.google.com/optimization/scheduling/employee_scheduling
Berkeley CS188 Textbook, CSP ordering heuristics: https://inst.eecs.berkeley.edu/~cs188/textbook/csp/ordering.html
CS50 AI, Lecture 3 - Optimization: https://cs50.harvard.edu/ai/notes/3/

Bản tiếng Anh đang soạn.