离散数学与证明 I · 综合建模

校园研讨会安排:从同一现实问题切换模型

六场研讨会要排进三个时段、两间教室。学生选课造成冲突;当目标改变时,适合的离散结构也随之改变。

场景参数

6
研讨会
3
时段
2
教室

切换问题目标

同一批数据,分别读成网络、计数空间和算法状态。

冲突图:把“不能同段”画成边

点击任意顶点可循环更换时段,红边表示当前方案违反冲突约束。

校园研讨会冲突图 六个顶点代表研讨会,边代表有学生同时选择两场研讨会,顶点颜色代表分配时段。

当前时段映射 c

计数决策树:把“有多少种”拆成乘法

这里把时段和教室都视为有标签的选择:上午、下午、傍晚不同,R101 与 R202 也不同。

安排数决策树 先为三角冲突选择三个不同时段,再由冲突约束确定 D、E、F 的时段,最后分配教室。 6 场研讨会 3 时段 × 2 教室 A、B、C 两两冲突 必须占用三个不同时段 3! = 6 D、E、F 被约束 D 同 B,E 同 A,F 同 C 每个时段正好两场,分配两间教室 2! × 2! × 2! = 8 完整安排数 = 48

合法时段分配

-

每个时段方案的教室分配

-

完整可选安排

-

计数式: |Ω| = 3! × (2!)³ = 48。 三角冲突决定 A、B、C 的三个时段;其余三个顶点由冲突边唯一定位;每个时段内两场研讨会再交换两间教室。

不变式检查:逐步验证贪心输出

顺序为 A、B、C、D、E、F;每一步选择最早的可行时段,再取该时段第一间空教室。

当前排表

本步证据