Trọng số phạt hay thứ tự ưu tiên?

1. Cùng là lịch khả thi, lịch nào được ưu tiên?

Giả sử phòng đào tạo đã kiểm tra ba lịch A, B và C. Cả ba đều đáp ứng sức chứa, loại phòng và các điều kiện chống trùng. Khi chọn lịch để công bố, nhóm lập lịch muốn giảm hai đại lượng. P là số lần giảng viên đổi cơ sở trong ngày, còn Q là số lớp học từ 15:00. Mỗi đại lượng phản ánh một ảnh hưởng khác nhau, nên cần làm rõ cách đánh đổi trước khi cộng điểm.

Khi tối thiểu hóa w × P + Q, lịch B thắng với w = 5, còn lịch A thắng với w = 8. Nếu chính sách quy định giảm số lượt chuyển cơ sở trước, rồi mới xét số lớp muộn, lịch A luôn đứng trước B và C trong bảng này. Hai cách chọn phản ánh hai chính sách khác nhau. Nên ghi rõ chính sách để người đọc giải thích được vì sao lịch thay đổi khi chỉnh một trọng số.

2. Suy ra ngưỡng đảo thứ hạng

So sánh A với B. Chênh lệch điểm B trừ A bằng (w + 2) − 9 = w − 7. B có điểm nhỏ hơn khi w < 7, hòa khi w = 7 và kém hơn khi w > 7. Tương tự, so A với C ta có 2w − 9. Khi xét trọng số nguyên dương, w = 8 đủ để A đứng đầu ba lịch mẫu. Nếu chỉ thử w bằng 5 và 10, kết quả cho biết có đảo thứ hạng nhưng chưa cho biết mức hòa nằm ở đâu.

Giả sử ta muốn tổng có trọng số luôn tương đương với thứ tự từ điển trên một miền rộng hơn. Nếu P nguyên và hai giá trị khác nhau cách ít nhất một đơn vị, còn Q nằm trong đoạn [0,9], thay đổi một đơn vị ở P đóng góp ít nhất w. Thay đổi ở Q có thể bù tối đa 9. Vậy w > 9 bảo đảm cải thiện P thắng mọi bù trừ từ Q. Cận này dùng cho toàn miền đã nêu, còn 8 chỉ đủ trên ba lịch trong bảng.

3. Kiểm chứng ngưỡng và diễn giải các trường hợp hòa

"""So sánh tổng có trọng số với ưu tiên theo thứ tự từ điển."""
from itertools import product

LICH = {
    "A": (0, 9),
    "B": (1, 2),
    "C": (2, 0),
}


def tot_nhat_theo_tong(lich, w):
    return min(lich, key=lambda ten: w * lich[ten][0] + lich[ten][1])


def tot_nhat_theo_tu_dien(lich):
    return min(lich, key=lich.get)


if __name__ == "__main__":
    assert tot_nhat_theo_tu_dien(LICH) == "A"
    for w in (1, 5, 7, 8, 10):
        scores = {ten: w * p + q for ten, (p, q) in LICH.items()}
        print(f"w={w:2}: {scores}; chọn {tot_nhat_theo_tong(LICH, w)}")

    # w=7 làm A và B hòa. w=8 đủ để tách ba lịch đã biết.
    assert 7 * LICH["A"][0] + LICH["A"][1] == 7 * LICH["B"][0] + LICH["B"][1]
    assert tot_nhat_theo_tong(LICH, 5) == "B"
    assert tot_nhat_theo_tong(LICH, 8) == "A"

    # Chứng thực bằng liệt kê cho toàn miền 0 <= Q <= 9.
    # Khi P cải thiện ít nhất một đơn vị, w=10 luôn giữ ưu tiên.
    pairs = list(product(range(3), range(10)))
    assert sorted(pairs) == sorted(pairs, key=lambda pair: 10 * pair[0] + pair[1])

Chạy python trong_so_va_uu_tien.py. Chương trình in điểm từng lịch và kiểm tra rằng cách sắp theo cặp (P,Q) trùng với cách sắp theo 10 × P + Q trên miền kiểm tra. Ở w bằng 7, hai lịch A và B hòa. Hàm min trả mục gặp đầu tiên khi hòa, vì vậy không dùng tên lịch được in ra để kết luận một lịch có chất lượng cao hơn lịch kia. Hãy xem cả bảng điểm.

Thử mở rộng miền Q đến 14. Có thể dựng phản ví dụ với A có cặp (0,14) và B có cặp (1,0). Dùng trọng số 10 thì B thắng theo tổng, trong khi A thắng theo thứ tự từ điển. Mỗi khi thêm loại phạt hoặc tăng quy mô, cần xem lại cận của tổng các thành phần ưu tiên thấp hơn.

4. Thiết kế một lần thử thay đổi trọng số

1. Chọn một kịch bản trong phòng thí nghiệm xếp lịch và ghi lịch mẫu, trọng số, từng số lần vi phạm mềm.
2. Tăng trọng số cho đổi cơ sở hoặc ca muộn rồi tìm lại phương án. Ghi cả điểm tổng lẫn các thành phần. Hai điểm tổng tính theo hai bộ trọng số khác nhau không đo cùng một chính sách.
3. Giữ trọng số cố định và đổi một điều kiện cứng trong một bản sao dữ liệu. Tách ảnh hưởng do tập lịch khả thi thay đổi khỏi ảnh hưởng do thang điểm thay đổi.

Nếu yêu cầu nghiệp vụ thật sự có cấp ưu tiên, ASP hỗ trợ khai báo các mức ưu tiên trong mục tiêu. Bài này dùng tổng có trọng số để giúp kiểm tra ngưỡng bằng tay. Đọc thêm tại Potassco Guide.