Mã hóa lớp cần nhiều ca liên tiếp

1. Chọn một biến quyết định

Với lớp thực hành cần hai ca, ta chọn một ca bắt đầu rồi suy ra các ca chiếm dụng. Nếu chọn hai ca độc lập, cần thêm điều kiện liên tiếp và dễ chấp nhận cặp nằm ở hai ngày. Ví dụ dùng bốn ca nối tiếp trong cùng ngày, đánh số từ 1 đến 4. Trong dữ liệu thật, nên biểu diễn quan hệ kế tiếp để bỏ qua các cặp nằm qua giờ nghỉ hoặc qua ngày.

2. Tách miền khỏi ràng buộc xung đột

Thời lượng của một lớp là d và ca bắt đầu là s. Ca cuối mang số s + d − 1. Miền của s chỉ gồm các giá trị khiến ca cuối không vượt giới hạn ngày. Sau khi suy ra mọi ca bị chiếm, quy tắc xung đột chỉ cần kiểm tra hai lớp cùng dùng phòng ở một ca. Điều kiện này áp dụng giống nhau cho lớp dài một và nhiều ca.

3. Đối chiếu bằng lịch tay

Lớp B dài một ca và bị cố định ở ca 3. Lớp A dài hai ca, nên bắt đầu ở 2 sẽ chiếm ca 2 và 3, còn bắt đầu ở 3 sẽ chiếm ca 3 và 4. Cả hai đều xung đột. Phương án duy nhất cho A là bắt đầu ở 1. Nếu bộ kiểm chứng chỉ so ca bắt đầu, phương án A bắt đầu ở 2 sẽ lọt qua.

Nếu chưa có Clingo, cài bằng python -m pip install clingo.

Chạy ví dụ bằng python -m clingo asp_ca_lien_tiep.lp -n 0.

lop(a,2). lop(b,1).
ca(1..4).
ung_vien(L,S) :- lop(L,D), ca(S), S+D-1<=4.
1 { bat_dau(L,S) : ung_vien(L,S) } 1 :- lop(L,_).
:- not bat_dau(b,3).
chiem(L,T) :- bat_dau(L,S), lop(L,D), ca(T), T>=S, T<S+D.
:- chiem(a,T), chiem(b,T).
#show bat_dau/2.
#show chiem/2.

4. Thử bộ dữ liệu có ngắt quãng

Tạo hai ngày, mỗi ngày ba ca, rồi đặt lớp dài hai ca ở ca cuối ngày đầu. Bộ kiểm chứng phải từ chối ngay cả khi mã ca ngày sau nối tiếp về số học. Đối chiếu hai mã hóa trên một tập nhỏ gồm ngày thường, ca bị khóa, giờ nghỉ và lớp dài đúng bằng số ca trong ngày.

Đọc thêm Tài liệu ngôn ngữ ASP của Potassco.