Từ câu nếu–thì đến quy tắc và mức phạt trong ASP

1. Cùng một câu nói có thể chứa ba yêu cầu khác nhau

Giảng viên A nói: “Nếu tôi đã dạy sáng thứ Hai thì tôi muốn tránh dạy sáng thứ Sáu.” Trong nghiệp vụ, từ “muốn” thường gợi ý một ưu tiên. Cần hỏi người đặt yêu cầu xem sáng thứ Sáu bị cấm hoàn toàn trong trường hợp đó, hay vẫn chấp nhận khi thiếu phòng hoặc khi phương án khác gây nhiều xung đột hơn.

Đặt P là A dạy sáng thứ Hai và Q là A dạy sáng thứ Sáu. Một yêu cầu cứng có thể diễn đạt bằng P → ¬Q trong logic mệnh đề. Cách hiểu ưu tiên chỉ phạt khi P ∧ Q xảy ra. Một nhãn suy diễn có thể ghi rằng A nên tránh sáng thứ Sáu khi P đúng, để giải thích lý do mà không tự giới hạn phương án.

2. Lập bảng chân trị để đọc đúng phạm vi

Dòng thứ hai là ca thử hữu ích. Khi A không dạy sáng thứ Hai, lịch dạy sáng thứ Sáu vẫn được phép và không có điểm phạt theo ưu tiên này. Nếu viết quy tắc phạt cho mọi lần dạy thứ Sáu thì sẽ làm sai ca đó. Nếu nhìn lịch và thấy A không dạy thứ Sáu, ta cũng chưa thể kết luận A dạy thứ Hai. Đây là suy luận ngược từ một điều kiện chưa đủ.

3. Tách nhãn suy diễn, kiểm tra và tối ưu

Mã sinh bốn tổ hợp để đối chiếu với bảng. nen_tranh(a,t6) là nhãn giải thích, còn vi_pham(a) chỉ xuất hiện khi cả hai buổi có mặt. Giá trị diem/1 cho biết chi phí của từng phương án. Cờ hard dùng để quan sát thay đổi khi chuyển ưu tiên thành điều kiện cấm.

% Liệt kê: clingo suy_luan_uu_tien.lp 0
% Chuyển ưu tiên thành cấm: clingo suy_luan_uu_tien.lp 0 -c hard=1
#const hard=0.

% Sinh mọi tổ hợp dạy sáng thứ Hai và sáng thứ Sáu.
{ day(a,t2); day(a,t6) }.

% Nhãn giải thích cho ưu tiên có điều kiện.
nen_tranh(a,t6) :- day(a,t2).
vi_pham(a) :- day(a,t2), day(a,t6).

% Điểm 0 nếu không vi phạm, 5 nếu vi phạm.
diem(D) :- D = #sum { 5,G : vi_pham(G) }.

% Bật chế độ cứng mới loại nghiệm có vi phạm.
:- hard=1, vi_pham(a).

#show day/2.
#show nen_tranh/2.
#show vi_pham/1.
#show diem/1.

Chạy clingo suy_luan_uu_tien.lp 0. Kết quả có bốn mô hình. Trong đó chỉ một mô hình chứa vi_pham(a) và diem(5). Chạy lại với -c hard=1 để kiểm tra còn ba mô hình. Nếu cài Clingo dưới dạng gói Python, thay clingo bằng python -m clingo.

4. Khi đưa vào bài toán lịch đầy đủ

Ví dụ liệt kê mọi tổ hợp để học cách suy luận. Trong mô hình lịch đầy đủ, các buổi dạy được suy ra từ phép gán lớp vào ca. Nếu cần tối ưu, thêm #minimize { 5,G : vi_pham(G) }. và định nghĩa rõ mỗi giảng viên bị tính một lần theo tuần hay theo một đơn vị khác. Nếu mô hình có nhiều tuần, đưa mã tuần vào quy tắc và khóa của từng khoản phạt để tránh gộp hai vi phạm độc lập.

Bài tập. Thêm ưu tiên “nếu dạy cả hai sáng thì nên xếp cùng cơ sở”. Lập bảng cho các trường hợp khác cơ sở và cùng cơ sở. Xác định trước khoản phạt mới cộng thêm vào khoản cũ hay thay thế khoản cũ.

Đọc thêm tại Potassco Guide về ràng buộc toàn vẹn và mục tiêu tối ưu.