知识卡片
排课先满足硬约束
考试排课先满足硬约束,再尽量满足软约束。硬约束必须成立,否则时间表不可用,常见有:同一考生同一时段不能参加多门考试、各门考试只能安排一次、全部考试都要排进表。软约束尽量满足但非必须,例如同一考生各门考试间隔尽可能大、分布尽量均匀。时间表质量由软约束违反程度决定,违反值越小越好。
补充教学示例(非书中数据)。学生甲周一上午已有考试 A,若再把考试 B 排到同一时段,违反硬约束,整张表不可用;若 B 排到周三,硬约束满足,间隔仍可用软约束惩罚比较质量。编码、交叉和变异若会破坏硬约束,需要修复、拒绝或惩罚。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 . 3 . 1 基 于 遗 传 算 法 的 T T P 问 题 · 查看原书依据
大学考试时间表问题研究的就是如何在满足硬约束条件的情况下,尽可能满足多的软约束条件。时间表质量的好坏就是由满足软约束条件程度的高低决定的,软约束条件的违反值越小,时间表的质量越高,反之则时间表的质量越低。
参考来源
- 位置:《智能算法导论》第 1 章 1.3.1 节“约束条件”(`EPUB/xhtml/chapter1_0007.xhtml`)。
- 结论依据:原文分列三类硬约束与多项软约束,并定义时间表质量为软约束满足程度。甲同学两门考试的时段对比为依据硬/软约束定义补充的教学示例,非书中数据。
- 原始内容:大学考试时间表问题研究的就是如何在满足硬约束条件的情况下,尽可能满足多的软约束条件。