简介资源是关于“教学计划编制问题”的课程论文与源程序面向数据结构、图论课程设计及算法初学者。内容聚焦将课程依赖关系建模为有向无环图AOV网通过广度优先拓扑排序生成合理教学顺序并讨论了DFS与BFS在该场景下的取舍。包内为单个doc文档约190KB包含问题描述、AOV网与邻接表表示、功能函数设计如初始化图、队列操作、拓扑排序以及完整C语言源代码便于读者对照算法与实现。已有295人学习下载适合需要完成类似课程设计任务或深入理解拓扑排序原理的读者参考。1. 教学计划编制问题一个把教务逼疯的组合优化难题每个学期末教务处的排课压力都会达到顶点。教学计划编制问题听起来只是排个课表实际上是把专业培养方案里的几百门课程在教师、教室、时间片、班级四个维度上找出一个不冲突的排列。冲突一旦出现就是连锁反应一个教师被占用实验课连排被打断两个班抢同一间机房。论文里把这类问题归为带约束的组合优化通常用遗传算法、模拟退火或约束编程求解而源程序要做的不只是算出一个可行解还要让教务老师看得懂、改得动。这篇笔记我会按照从建模到代码到调参的路径把教学计划编制问题讲透适合正在复现论文实验、准备课程设计或做教务信息化系统的人。2. 从培养方案到约束网络教学计划编制问题的建模方法2.1 变量定义课程段、教师、教室、时间片怎么拆教学计划编制的最小单元不是一门课而是课程段。一门每周4学时的课程如果每节课2学时它就是两个课程段如果每周要连排一次实验实验又是一个课程段。常见做法是把课程段编号为 seg_id记录它属于哪门课程、需要几课时、期望周几、倾向的时段类型上午/下午/晚上。接下来要定义四个基础集合教师集合 T每位教师有可授课时间段教室集合 R每个教室有容量和类型普通/多媒体/实验室班级集合 C每个班级有固定的课程段列表时间片集合 S通常按周几第几节拆分一周20个时间片周一至周五每天4个时段是常见粒度。这四个集合就是问题的坐标系所有约束都建立在这四者的交叉关系上。这里的关键是时间片粒度。论文里常用周几时段两级分解工程上如果涉及单双周还得加一个周次奇偶维度。我一般建议把时间片直接做成整数编号比如周一1-2节是3周一3-4节是4这样后续做冲突检测只需比较整数而不需要解析星期几第几节。解析式的写法在数据量小的时候看不出问题一旦遇到跨校区排课字符串比较带来的性能损耗和出错概率会成倍上升。2.2 约束分类硬约束与软约束的取舍标准约束条件分成硬约束和软约束两层。硬约束是任何可行解必须满足的违反一条就判为不可行解软约束是尽量满足不满足扣分。这个分类不是论文里随便写的它直接决定后续适应度函数里惩罚项的设计方式也是整个教学计划编制问题建模时最需要拿捏的部分。硬约束常见四条同一时间片同一个教师只能出现在一个课程段同一时间片同一个班级只能在一个教室上课同一时间片同一间教室只能被一个课程段占用教室类型和容量必须匹配课程段需求实验室课程不能排进普通教室教室容量不能小于实际上课人数。软约束常见三条课程尽量安排在教师偏好的时间段同一门课程的多个课程段尽量分散在不同天上午时段利用率尽量高晚间尽量少排。建模时的取舍标准是软约束不要超过五条否则适应度函数会互相打架调参变成玄学。论文里喜欢把软约束写成加权和工程上我建议每个软约束单独算一个评分项最终用权重合并方便教务在界面上直接调权重。我曾经见过一个需求文档里写了九条软约束实际调参时每改一个权重另一条评分就崩最后只能砍到三条才跑出可用结果。2.3 建模示例一个可落地的数据结构设计用 Python 里的字典和列表来承载这份模型结构简单在遗传算法迭代里也容易做切片和重组。下面是一份最小可跑的建模代码# 教学计划编制最小数据结构示例 from dataclasses import dataclass, field from typing import List, Dict dataclass class CourseSegment: seg_id: str # 课程段编号如 CS101-A1 course_name: str # 课程名 teacher_id: str # 任课教师 hours: int # 每周学时数 room_type: str # 教室类型normal/lab/multimedia student_count: int # 选课人数 prefer_morning: bool # 是否偏好上午时段 dataclass class TimetableSolution: # 关键决策变量seg_id - (time_slot, room_id, teacher_id) assignment: Dict[str, tuple] field(default_factorydict) def is_teacher_conflict(self, teacher_id: str, time_slot: int) - bool: # 检查教师在某时间片是否已被占用 for (seg, (slot, room, teacher)) in self.assignment.items(): if teacher teacher_id and slot time_slot: return True return False这段代码里TimetableSolution 的 assignment 字典是整个问题的核心键是课程段编号值是三元组时间片、教室、教师。is_teacher_conflict 只是一个冲突检测示例实际完整检查要同时覆盖班级、教室两个维度。把数据结构定成这样是因为遗传算法后续的交叉、变异只需要交换和修改 assignment 里的值不会影响课程段本身的属性。参数说明hours 在模型里用来计算该课程段每周需要占用几个时间片工程上如果一门课3学时通常排成21即一个2学时正课加一个1学时实验而不是一个3学时连续块room_type 和 student_count 决定教室过滤条件prefer_morning 参与软约束评分。seg_id 的命名规则建议统一成课程编号-班级编号这样在输出课表时可以直接映射回培养方案里的课程名。3. 用遗传算法求解教学计划从初始种群到适应度函数3.1 为什么选遗传算法而不是贪心或回溯教学计划编制问题的变量规模一个中等规模的学院大约在5002000个课程段决策变量是每个课程段的时间片和教室组合空间非常大。贪心算法能快速给出解但教室类型多样、教师偏好复杂时贪心很容易在局部选择中把后面的课程段逼进死胡同回溯能保证找到可行解但状态空间爆炸跑一个学院规模的实例要等很久。遗传算法是论文里最常见的选择原因在于三点第一适应度函数天然支持硬约束和软约束的加权合并工程实现直观第二种群并行搜索不容易一次跌进局部最优第三实现难度适中几十个课程段的验证规模一个下午就能跑起来。当然它不保证找到全局最优甚至是每次跑结果都不同的这需要后面讲到的随机种子和收敛判断来控制。算法求解质量实现复杂度典型耗时500课程段适用边界贪心一般容易局部冲突低秒级约束简单、规模小回溯最优但可能无解中可能数小时课程段小于100遗传算法接近最优中分钟级1003000课程段3.2 编码方案一维数组如何承载排课方案遗传算法的编码方案直接决定交叉变异怎么实现。常见做法有两种一是按课程段顺序排成一维数组每个位置上是一个时间片编号教室信息另外用哈希表记录二是每个位置放一个时间片, 教室的元组编码。我建议用第一种一维整数数组编码。原因在于教学计划编制里真正难的约束是时间冲突教室约束相对独立可以放到解码阶段再校验和修正。一维数组长度等于课程段总数第 i 位的整数表示第 i 个课程段被分配到的时间片。比如# 编码示例20个课程段的一维染色体 # 索引 课程段在列表中的顺序值 时间片编号0~39 chromosome [3, 15, 3, 22, 7, 30, 11, 18, 25, 29, 4, 16, 4, 23, 7, 31, 12, 19, 26, 30]这个数组的问题很快就显现出来两个不同的课程段被分配到同一个时间片如果它们共享教师或班级就构成硬约束冲突。所以适应度函数必须把冲突数量折算成惩罚值。编码长度固定为课程段数量不会因为教室数量变化而改变这让交叉算子写起来非常干净。3.3 适应度函数设计与遗传算子代码实现适应度函数是遗传算法的核心。我习惯把适应度设成越大越好用总权重减去惩罚分。硬约束每条违反记很大的惩罚软约束每个违反记小惩罚。下面是一段可以直接改参数跑起来的核心代码# 教学计划编制遗传算法核心模块示意 import random def decode(chromosome, segments): 把一维染色体解码成课程段-(时间片, 教室)映射。 教室分配采用贪心按时间片扫描选容量够且空闲的最小教室。 assignment {} room_busy {} # (time_slot, room_id) - bool for i, seg in enumerate(segments): time_slot chromosome[i] room assign_room(seg, time_slot, room_busy) # 贪心选教室 assignment[seg.seg_id] (time_slot, room) return assignment def fitness(chromosome, segments, weights): 适应度 1000 - 硬约束惩罚 - 软约束惩罚 assign decode(chromosome, segments) hard_penalty 0 teacher_used set() class_used set() room_used set() for seg_id, (slot, room) in assign.items(): seg segments_by_id[seg_id] tk (seg.teacher_id, slot) ck (seg.class_id, slot) rk (room, slot) if tk in teacher_used: hard_penalty weights[hard_teacher] else: teacher_used.add(tk) if ck in class_used: hard_penalty weights[hard_class] else: class_used.add(ck) if rk in room_used: hard_penalty weights[hard_room] else: room_used.add(rk) soft_penalty 0 for seg_id, (slot, room) in assign.items(): seg segments_by_id[seg_id] if seg.prefer_morning and slot % 4 not in (0, 1): soft_penalty weights[soft_morning] return 1000 - hard_penalty - soft_penalty def crossover(p1, p2): 单点交叉随机切一刀交换后半段 size len(p1) cut random.randint(1, size - 1) c1 p1[:cut] p2[cut:] c2 p2[:cut] p1[cut:] return c1, c2 def mutate(chromosome, slot_count, prob0.05): 按概率随机改变某个课程段的时间片 for i in range(len(chromosome)): if random.random() prob: chromosome[i] random.randint(0, slot_count - 1) return chromosome参数说明weights 里的 hard_teacher 通常设成 50100soft_morning 设成 15比值至少10倍以上否则硬约束罚不够算法会收敛到一堆冲突的解。mutate 概率 0.05 适合几百个课程段的问题课程段多时可以降到 0.02。crossover 用单点交叉是因为染色体长度不大单点交叉计算代价低而且对课表类问题没有明显的性能劣势。这段代码里的 decode 函数每次迭代都会被调用是性能瓶颈。工程上我建议把教室分配从适应度计算里拆出去预计算好每间教室的空闲矩阵能减少一半以上的计算量。另外注意 segments_by_id 在实际工程里应该作为参数传入而不是依赖全局变量否则多线程跑参数扫描时会出现数据串扰。fitness 里的教室冲突检测与 decode 的贪心分配是双保险decode 尽量避免冲突fitness 负责兜底惩罚。4. 教学计划编制源程序的工程化输入、输出与可调参数4.1 输入文件设计JSON 配置与课程清单要从论文实验变成教务能用的源程序第一步是把输入从硬编码的列表改成文件。常见做法用 JSON原因是没有额外的数据库依赖教务老师也能用 Excel 导出后简单转换。输入文件分三个courses.json课程段清单、teachers.json教师及其偏好、rooms.json教室资源。下面是一段 courses.json 示例{ semester: 2024-2025-1, time_slots_per_day: 4, working_days: 5, segments: [ {seg_id: CS101-A1, course: 程序设计基础, teacher: t001, class_id: c001, hours: 2, room_type: normal, student_count: 45, prefer_morning: true}, {seg_id: CS101-A2, course: 程序设计基础实验, teacher: t002, class_id: c001, hours: 2, room_type: lab, student_count: 45, prefer_morning: false} ] }参数说明time_slots_per_day 和 working_days 决定总时间片数这里是 4*520。hours 字段目前不参与编码但用于课程段拆分比如 hours4 的程序设计基础要拆成两个 seg_id 才能正常编码。教室类型在 rooms.json 里对应normal/lab/multimedia 三种类型要写在 room_type 字段里与教室资源严格一致大小写不一致是初学者最常见的导入报错。4.2 命令行运行流程与参数设置源程序的运行入口我一般设计成命令行工具最少参数就是输入目录、输出目录、随机种子、迭代代数。这样的设计方便批量跑实验也方便写脚本做参数扫描。运行时命令如下# 教学计划编制程序运行示例 python timetable.py \ --input ./data \ --output ./result \ --seed 42 \ --generations 500 \ --population 200 \ --crossover-rate 0.8 \ --mutation-rate 0.05 \ --hard-weight 100 \ --soft-weight 2这段命令里generations 和 population 是遗传算法的两个主要开销参数。500 代、200 个体对于500个课程段的问题大约要跑几分钟到十几分钟取决于解码函数优化程度。seed 必须保留教务排课需要可复现同一份输入、同一个 seed 必然得到同一个结果否则老师改一个权重后结果全变没法做对比。crossover-rate 0.8 是常规经验值mutation-rate 根据染色体长度微调。hard-weight 与 soft-weight 的比例决定算法是优先保证不冲突还是优先照顾教师偏好。4.3 输出结果课表视图与冲突报告输出不只是课表本身更要有冲突报告。教务老师看到结果时第一句话通常不是排得真好而是为什么这门课在周五晚上。所以源程序要输出三个文件timetable.csv、conflict_report.txt、schedule_stats.json。timetable.csv 的格式设计成课程段、教师、班级、时间片、教室seg_id,course,teacher,class_id,time_slot,room CS101-A1,程序设计基础,t001,c001,3,R203 CS101-A2,程序设计基础实验,t002,c001,7,L104conflict_report.txt 里列出所有未被满足的软约束和硬约束残留每行一条格式固定为类型 | 课程段 | 原因。这样做的好处是当遗传算法在有限代数内没找到完全无硬冲突的解时教务可以拿这个报告人工判断哪些冲突可以容忍。schedule_stats.json 记录本次运行的适应度曲线采样、收敛代数、硬冲突数量方便你和论文里的实验做对比。第4章的内容到这里你会发现整个源程序的骨架已经很完整输入是结构化文件运行是命令行输出是三份不同用途的文件。这个结构对后续增加新约束、新输出格式都非常友好。5. 教学计划编制避坑指南5个让算法失效的常见原因5.1 遗传算法永远收敛不到硬约束全为0的解现象跑了2000代适应度曲线已经平了但 conflict_report 里总是剩一两条教师冲突。原因初始种群全都是由随机时间片拼出来的当中某个课程段的可行时间片集合本身很小比如某位老师只在周一周三上午有空随机初始化时大概率给了一个不可行的时间片交叉变异又很难把它改回来。解决初始化种群时不要完全随机先扫描一遍每个课程段的可选时间片集合从集合里采样。做法是初始化函数里把时间片过滤逻辑复用课程段只从合法时间片里取随机值。这个改动能显著提高初始种群质量收敛代数可能减少一半以上。5.2 教室冲突检测和分配逻辑脱节出现排完才知道教室不够的情况现象遗传算法跑完输出课表里同一个教室在同一个时间片出现了两次或者实验室排进了普通教室。原因decode 阶段没有做教室状态管理教室分配只是随手赋值把教室冲突全部推给适应度函数罚分。解决把教室分配改成贪心匹配在 decode 时维护一个 room_busy[(slot, room)] 的布尔状态表当前课程段需要教室时从容量够且空闲的教室里选最小的一间。经过这一步教室里只剩一种情况会冲突可用教室总数在某时间片少于需要的教室数这时才由适应度函数罚分。我建议把这种结构性冲突单独记到输出报告里方便证明是教室资源不够而不是算法不行。5.3 教师偏好被当成硬约束写死排完课老师仍然不满意现象把教师不上周五下午直接设成不可选时间片结果课程段挤爆周一上午适应度很高但教务没法用。原因教师偏好具有弹性某些周不排课是特殊情况不是硬性禁令。写成硬约束后优化空间被砍掉一大块还会导致不可行解。解决一律把教师偏好放软约束评分项不参与可选时间片过滤。代码里在函数里对非偏好时间片加 soft_penalty而不是把该时间片从合法集合剔除。这个教训来自我做过的一个真实排课需求变更教师临时调课后硬约束方案完全需要重排软约束方案只需改权重。血泪经验偏好一旦写死后期每一处调整都是灾难。5.4 种群早熟课表多样性快速丢失现象前100代适应度涨得很快之后200代纹丝不动换一个随机种子结果基本一样所有个体的染色体高度相似。原因锦标赛选择压力太大、变异率太低或者精英保留数量过多。种群在早期被几个高适应度的个体主导基因多样性丢失。解决先检查选择压力锦标赛 k 值从2降到1等价于随机选变异率从0.05提高到0.1如果还不行从第50代起动态把变异率乘1.5。工程上我通常每隔20代做一次多样性检查计算所有个体同一个基因位上取值种类的数量低于某个阈值就触发变异率提升。这是最有效的反早熟手段。5.5 课程段拆分错误导致同一门课排进同一时间片现象一门4学时的课程被拆成两个课程段后两段课程的班级相同如果时间片编号恰好相同冲突报告会报班级冲突而且每次跑解不一样看起来像随机bug。原因课程段拆分时没有记录同一门课不能同时上的约束或者 hours 字段和拆分逻辑不一致。解决拆分时给同一门课的多个课程段打上 group_id 字段检测同 group_id 且同班级的课程段时间片必须不同。同时建议拆分规则固定为2学时一个段3学时拆成214学时拆成22。这个规则要和输入文件里的学时数强校验程序启动时发现不一致直接报错不要静默修复。6. 把教学计划从能跑调到能用结果校验与人工微调接口6.1 独立校验器和求解器解耦的结果验证遗传算法的实现里,decode 和 fitness 是耦合在一起的很容易出现fitness 说没冲突教务拿课表一核对全是冲突的情况。原因是 fitness 为了性能可能只检测了部分约束。做法是写一个完全不依赖遗传算法内部数据结构的独立校验器直接读 timetable.csv重新检查所有硬约束# 独立校验不复用遗传算法的解码逻辑 def validate(timetable_rows): errors [] teacher_slots {} class_slots {} room_slots {} for row in timetable_rows: seg_id, teacher, class_id, slot, room row if (teacher, slot) in teacher_slots: errors.append(f教师冲突: {seg_id} 与 {teacher_slots[(teacher, slot)]}) if (class_id, slot) in class_slots: errors.append(f班级冲突: {seg_id} 与 {class_slots[(class_id, slot)]}) if (room, slot) in room_slots: errors.append(f教室冲突: {seg_id} 与 {room_slots[(room, slot)]}) teacher_slots[(teacher, slot)] seg_id class_slots[(class_id, slot)] seg_id room_slots[(room, slot)] seg_id return errors这段校验器的输入是最终的 CSV 文件输出是明确的冲突列表。它和求解器完全解耦跑一次只需要几十毫秒每次改完参数、跑完算法先运行它过了再交付给教务。6.2 锁定重排给教务一个人工干预的入口无论算法多先进教务老师手里总会有几个必须这样排的硬性要求某个老师周三下午要去实验室某门课必须连排两节某间教室留给毕业答辩。所以源程序要支持锁定操作把部分课程段的时间片固定住再对剩余课程段重新优化。实现上给染色体加一个 locked_mask 数组长度和染色体相同值为 True 的位置在交叉、变异时跳过。初始化时先读取锁定配置把固定值写入染色体对应位置后续所有遗传操作都绕过这些位置。我在实际项目中用这个接口解决过最头疼的需求毕业设计指导课要避开所有答辩周锁定后其他课程照常优化教务把锁定配置维护在一个单独的 override.json 文件里不需要改代码。这个接口也是验证算法鲁棒性的好工具。如果想测软约束权重是否合理可以只锁定两三门课对比锁定前后其他课程段的变化幅度。变化太大说明适应度函数里软约束之间的权重失衡需要回炉调参。我吃过亏的是没有独立校验器直接拿解码函数当验证工具结果解码函数的 bug 复制到了整个流程排出来的课表连续两周没人发现教室冲突。后来独立校验器成了标配每次跑完先验证再交付。这个习惯帮你省掉的不只是排错时间还有教务老师的信任。希望帮到你。本文还有配套的精品资源点击获取