Backtracking, inference và heuristic cho CSP

Sau khi dùng constraint propagation để loại bớt các giá trị không thể xảy ra, ta vẫn thường phải thử các phép gán.

Cách cơ bản là Backtracking Search.

1. Từ brute force đến backtracking

Một cách rất ngây thơ:

Sinh tất cả phép gán.
Kiểm tra phép gán nào thỏa constraint.

Nếu có $n$ biến, mỗi biến có $d$ giá trị, số trường hợp có thể là:

d^n

Với ví dụ lịch thi 5 môn và 3 ngày ở bài trước, brute force phải kiểm tra:

3^5 = 243

Nghe vẫn nhỏ. Nhưng nếu có 20 môn và 5 khung thi:

5^{20} \approx 9.5 \times 10^{13}

Đây là lý do “thử hết” không còn thực tế khi bài toán lớn hơn một chút.

Backtracking tốt hơn ở điểm:

Vừa gán vừa kiểm tra. Nếu một phần lời giải đã vi phạm ràng buộc, dừng nhánh đó ngay.

2. Backtracking Search

BACKTRACK(assignment):
    nếu assignment đã hoàn chỉnh:
        return assignment

    var = chọn một biến chưa được gán

    for value trong domain(var):
        nếu value phù hợp với assignment hiện tại:
            gán var = value

            result = BACKTRACK(assignment)

            nếu result không failure:
                return result

            bỏ gán var

    return failure

3. Ví dụ cây tìm kiếm

Giả sử:

A, B, C \in \{Mon, Tue, Wed\}

và:

A \ne B, \qquad B \ne C

Backtracking không cần mở rộng các nhánh bên dưới một phép gán đã sai.

Trong ví dụ trên, nhánh A = Mon, B = Mon bị cắt ngay vì vi phạm $A \ne B$ . Ta không cần thử tiếp C = Mon, C = Tue, C = Wed ở dưới nhánh đó. Với bài toán lớn, mỗi lần cắt sớm như vậy có thể loại bỏ hàng nghìn nhánh con.

4. Nhưng chọn biến nào trước?

Nếu chọn ngẫu nhiên, cây search có thể vẫn rất lớn.

Heuristic giúp chọn thứ tự thông minh hơn.

5. Minimum Remaining Values - MRV

Chọn biến có ít giá trị còn lại nhất.

Ví dụ:

$D_A = \{Mon, Tue, Wed\}$ - 3 giá trị.
$D_B = \{Tue\}$ - 1 giá trị.
$D_C = \{Mon, Wed\}$ - 2 giá trị.

MRV chọn $B$ trước.

Tại sao?

Nếu $B$ chỉ còn một lựa chọn, sớm muộn ta cũng phải xử lý nó. Nếu lựa chọn đó làm bài toán thất bại, phát hiện sớm sẽ tránh search sâu vô ích.

MRV thường được gọi là chiến lược fail first.

Với lịch thi 5 môn:

Môn	Domain còn lại sau propagation	Số lựa chọn
AI	`{D2, D3, D4}`	3
DB	`{D3}`	1
WEB	`{D2, D4}`	2
ML	`{D2, D3}`	2
SE	`{D4}`	1

MRV sẽ chọn DB hoặc SE trước. Nếu DB = D3 dẫn tới mâu thuẫn, ta phát hiện ngay thay vì mất thời gian gán các môn còn lại.

6. Degree Heuristic

Nếu nhiều biến cùng có số giá trị còn lại như nhau, ưu tiên biến đang ràng buộc nhiều biến chưa gán khác nhất.

Ví dụ:

Nếu tất cả domain có cùng kích thước, $C$ là ứng viên tốt vì nó có nhiều quan hệ ràng buộc nhất.

Ý tưởng: xử lý điểm “khó” sớm.

7. Least Constraining Value - LCV

Sau khi chọn biến, ta còn phải chọn giá trị nào thử trước.

LCV ưu tiên giá trị loại bỏ ít lựa chọn nhất của các biến lân cận.

Ví dụ, với biến $C$ :

Chọn Tue làm ba biến khác mất một lựa chọn.
Chọn Wed chỉ làm một biến khác mất một lựa chọn.

LCV sẽ ưu tiên Wed.

Ví dụ cụ thể hơn với lịch thi:

Thử giá trị cho DB	Giá trị bị loại khỏi môn lân cận	Tổng số lựa chọn bị mất
DB = D2	WEB mất D2, SE mất D2, AI mất D2	3
DB = D3	WEB mất D3, SE mất D3, AI mất D3	3
DB = D4	WEB mất D4, SE mất D4, AI mất D4	3

Nếu mọi giá trị gây ảnh hưởng như nhau, LCV không giúp nhiều. Nhưng nếu AI đã bị cấm D4, còn WEB chỉ còn {D2, D4}, thì chọn DB = D2 có thể làm WEB chỉ còn D4, còn chọn DB = D3 không ảnh hưởng mạnh đến WEB. Khi đó LCV ưu tiên giá trị giữ lại nhiều lựa chọn hơn cho phần còn lại.

Có thể nhớ:

MRV / Degree: chọn biến khó trước.
LCV: với biến đã chọn, thử giá trị ít gây khó cho phần còn lại trước.

8. Inference trong lúc search

Sau mỗi phép gán, ta có thể tiếp tục propagate constraint.

Ví dụ:

Gán $A=Mon$ .
Vì $A \ne B$ , xóa Mon khỏi $D_B$ .
Nếu $D_B$ chỉ còn Tue, suy ra $B=Tue$ .
Tiếp tục lan truyền các hệ quả.

Đây là cách giảm mạnh search tree.

9. Maintaining Arc Consistency - MAC

Một chiến lược mạnh:

Sau mỗi phép gán trong backtracking, chạy arc-consistency trên các cung liên quan.

Ta bỏ thêm chi phí inference ở mỗi bước để đổi lấy một cây search nhỏ hơn.

Một cách nhìn thực dụng:

Chiến lược	Việc làm thêm	Lợi ích thường gặp
Backtracking cơ bản	Chỉ kiểm tra constraint đã liên quan	Dễ cài, nhưng có thể duyệt sâu mới biết sai
Forward checking	Sau khi gán, xóa giá trị không còn hợp lệ ở biến lân cận	Phát hiện domain rỗng sớm hơn
MAC	Duy trì arc consistency sau mỗi phép gán	Tốn hơn mỗi bước, nhưng giảm cây search mạnh hơn

10. Heuristic không thay đổi tính đúng đắn

MRV, Degree và LCV chủ yếu thay đổi thứ tự search.

Nếu triển khai đúng, chúng không biến nghiệm sai thành nghiệm đúng. Chúng giúp:

Tìm failure sớm hơn.
Tìm nghiệm nhanh hơn trong nhiều trường hợp.
Giảm số node phải duyệt.

Tuy nhiên, heuristic không đảm bảo cùng mức tăng tốc trên mọi bài toán.

11. Từ thuật toán nhập môn đến solver hiện đại

Trong bài học, ta tự hiểu:

Backtracking.
Arc consistency.
MRV.
Degree.
LCV.

Trong hệ thống thực tế, ta thường dùng solver đã được tối ưu nhiều năm.

Ví dụ OR-Tools CP-SAT hỗ trợ:

Biến nguyên và Boolean.
Constraint programming.
SAT-based reasoning.
Optimization objective.
Scheduling.

Điểm cần học không phải “tự viết solver tốt hơn OR-Tools”, mà là:

Biết chuyển bài toán thật thành biến, domain, constraint và objective đúng.

12. Chọn phương pháp nào?

Đây chỉ là quy tắc định hướng, không phải luật tuyệt đối.

13. Bài tập tư duy

Bài 1 - Lịch học nhóm

Có 5 thành viên và 4 khung giờ. Mỗi người chỉ rảnh ở một số khung giờ.

Hãy xác định:

Variables.
Domains.
Constraints.
Có cần objective không?

Bài 2 - Xếp lịch thi

Giả sử một môn bắt buộc thi vào buổi sáng và hai môn khác không được cùng ngày.

Ràng buộc nào là unary?
Ràng buộc nào là binary?
AC-3 có thể loại bỏ giá trị nào trước khi backtracking?

Bài 3 - So sánh chiến lược

Cho ba biến có domain:

D_A = \{1,2,3,4\}

D_B = \{1,2\}

D_C = \{1,2,3\}

Theo MRV, biến nào nên được chọn trước?

Bài 4 - Map bài toán sang công cụ

Với mỗi tình huống, hãy chọn hướng tiếp cận ban đầu:

Phân bổ ngân sách tuyến tính.
Xếp lịch thi.
Tối ưu tuyến giao hàng rất lớn.
Chọn số lượng máy chủ nguyên với chi phí nhỏ nhất.

Không cần tìm một thuật toán duy nhất đúng cho mọi trường hợp. Mục tiêu là giải thích vì sao mô hình được chọn phù hợp với cấu trúc bài toán.

Tóm tắt topic Optimization

Optimization hỏi: trong nhiều phương án, phương án nào tốt nhất hoặc đủ tốt?
Local Search cải thiện nghiệm bằng cách di chuyển trong neighborhood.
Hill Climbing nhanh nhưng dễ mắc local optimum.
Simulated Annealing đôi khi chấp nhận bước xấu để thoát local optimum.
Linear Programming tận dụng cấu trúc tuyến tính để tối ưu chính xác.
CSP biểu diễn bài toán bằng variables, domains và constraints.
Arc consistency giúp loại bỏ giá trị bất khả thi trước khi search.
Backtracking kết hợp MRV, Degree, LCV và inference có thể giảm mạnh không gian tìm kiếm.
Trong thực tế, chất lượng mô hình hóa thường quan trọng không kém solver.

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, CP-SAT Solver: https://developers.google.com/optimization/cp/cp_solver
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.