C#自动排课系统源码实战：贪心算法与回溯搜索实现冲突检测

简介这是一套基于C#与.NET框架开发的自动排课系统完整源码面向智慧校园场景中的教务管理人员、学校IT部门及C#学习者。系统覆盖课程任务管理、排课条件设置、排课执行、课程计划等核心模块从aspx页面到cs业务逻辑均有完整实现可直接部署或二次开发。压缩包共370个文件约7.58MB核心代码以96个cs文件为主配合aspx页面、配置文件、样式与脚本资源同时包含30个xlsx/xls表格、sql及mdf/ldf数据库文件以及doc/docx文档和png/jpg图片素材。xlsx表格可查看课程、教师、班级等基础数据数据库文件便于快速初始化环境文档与图片辅助理解系统结构项目还附有sln与csproj文件可用Visual Studio直接打开通过断点和调试工具跟踪排课流程。目前已有302人学习下载适合需要快速搭建排课原型、研究排课约束算法或进行课程设计的学生与开发者。1. C# 自动排课系统源码先别急着写算法把排课当约束求解问题自动排课系统在智慧校园项目里属于看着简单、落地才发现水很深的模块。课程表只有五行十列但教师冲突、班级冲突、教室容量、连堂课、单双周、合班课、实训室专用时段这些条件叠加在一起就是一个典型的约束满足问题。排课的核心不是“生成一张表”而是“先定义清楚什么是一张合格的表”。网上流传的 C# 自动排课源码大多分为两类一类是只做了“时间不重叠”检查的玩具版跑通 Demo 没问题一上真实课表数据就死锁另一类是引入了遗传算法或模拟退火的“大词版”代码量很大实际收敛速度慢且参数难调。我一般会采用“贪心确定初排 回溯填补冲突”的混合策略先保证解存在再逐步逼近最优。接下来我会把数据模型、冲突判定、排课主流程和几个易踩的边界讲清楚适合已经能写基本 C# 语法、想搞懂排课系统完整链路的开发者。2. 排课系统的数据模型与表结构设计2.1 为什么数据模型比算法本身更重要很多人拿到排课源码第一件事就是找核心算法类这其实是本末倒置。排课系统的数据模型决定了冲突检查能写多快、算法回溯时能拿到多少有效信息。如果数据库里班级、教师、课程是分开的三张表且没有冗余的班级人数、教师可教科目关联那么每次判断“某教师某时段是否有空”都要跨表 JOIN回溯算法的单次尝试成本就非常高。这也是很多源码“跑得动 Demo、跑不动真实数据”的根本原因。智慧校园场景下的排课系统数据来源通常已经是教务系统里的结构化数据班级、教师、课程、教室都有稳定编码。源码里应该把这四类基础数据做成独立表再用排课结果表把“谁、在什么时间、去哪个教室、上什么课”关联起来。特别注意教室表和课程表之间要冗余一个“教室类型”字段比如普通教室、多媒体教室、机房、实训室否则合班课和政治课这类大班额场景无法做容量过滤。2.2 核心表结构六张表覆盖排课闭环一份能用于生产的排课系统数据模型我认为最少要包含六张表。下面给出的是我惯用的字段设计按智慧校园场景做了裁剪去掉了学籍、成绩等无关内容只保留排课必需的列。表名核心字段设计意图t_teacherteacher_id, teacher_name, max_hours_per_week记录教师可用总课时防止超量排课t_classclass_id, class_name, student_count, grade班级人数决定选教室时的最小容量t_coursecourse_id, course_name, hours_per_week, course_typecourse_type 区分普通课/合班课/实训课t_roomroom_id, room_name, capacity, room_typeroom_type 与课程类型匹配避免把体育课排进机房t_teacher_courseteacher_id, course_id, preferred_time_slots教师可教主科与偏好时段这是排课柔性约束的落点t_scheduleschedule_id, class_id, teacher_id, course_id, room_id, day_of_week, period最终排课结果一个班级同一时段只能有一条记录t_schedule表是判断冲突的核心依据。所有冲突检查都可以归纳为在同一day_of_week和period下是否有两条记录在class_id、teacher_id或room_id上重复。上课时间的基本单位是“星期几 第几节”比如周一第 3 节这一个组合在代码里用一个短整型枚举表示即可。2.3 写一个课程类让数据和逻辑在同一层数据库表是持久化层但在算法运行时频繁访问数据库显然是性能灾难。源码里应该在内存中维护一个课程分配列表做完一轮排课再批量写回。这里给出一个简单的 C# 课程实体类和分配记录类。// 课程定义包含每周课时、课程类型、可选教师列表 public class Course { public string CourseId { get; set; } public string CourseName { get; set; } public int HoursPerWeek { get; set; } public CourseType Type { get; set; } // 普通 / 合班 / 实训 public int MinRoomCapacity { get; set; } // 选教室时的最低容量要求 public Liststring TeacherIds { get; set; } // 能教这门课的老师 } // 一次分配记录对应数据库 t_schedule 的一行 public class ScheduleItem { public string ClassId { get; set; } public string CourseId { get; set; } public string TeacherId { get; set; } public string RoomId { get; set; } public int DayOfWeek { get; set; } // 1-7 public int Period { get; set; } // 第几节1-10 public bool IsSingleWeek { get; set; } // 单双周标记 }课程实体类的设计重点是TeacherIds和MinRoomCapacity这两个字段。前者让“某个老师只能教数学”这一类硬约束在分配前就能过滤后者让教室选择可以在内存中直接比较容量不必每门课都查一次数据库。IsSingleWeek字段标记单双周课程这类课程排课逻辑上会复杂一些因为同一时段可以存在单周 A 课、双周 B 课的组合。提示ScheduleItem里不要加主键自增 ID算法在回溯试探阶段会频繁创建和丢弃对象自增 ID 留在写库时再生成即可。内存模型越轻量回溯搜索越快。3. 贪心 回溯混合排课核心算法的 C# 实现3.1 先做贪心初排把难的课程往前放排课问题不能一上来就无脑回溯状态空间太大。正确做法是分两步第一步用贪心算法把所有课程依次分配到可选时段里分配不了的先挂起第二步对挂起课程做回溯搜索。贪心的关键是排序规则——课时多、可选教师少、有特殊类型要求的课程优先排。这类课程放后面基本排不进去因为它们对时段和教室的要求太高。选择时段的权重计算是贪心策略的核心。一个时段对某门课的价值取决于同时满足“班级空闲、教师空闲、教室可用”三个条件。我把这三个条件合并成了一个打分函数分数越低代表越空闲优先占用分数最低的时段。这样能最大程度避免把某一天的某几节排满、其他天全空着的情况。下面给出贪心分配的核心方法和打分逻辑。// 贪心排序课程数越多、可教老师越少排得越早 var orderedCourses courseList .OrderByDescending(c c.HoursPerWeek) .ThenBy(c c.TeacherIds.Count) .ToList(); foreach (var course in orderedCourses) { var candidateSlots GetCandidateSlots(course); if (candidateSlots.Count 0) { pendingCourses.Add(course); // 进待回溯队列 continue; } var bestSlot candidateSlots .OrderBy(s SlotScore(s, course)) // 分数最低的最空闲 .First(); var item CreateScheduleItem(course, bestSlot); scheduleItems.Add(item); }定义GetCandidateSlots时要一次性过滤掉“班级有课、教师有课、教室被占用”三种硬冲突。SlotScore则是柔性判断这个时段如果被占用后续剩余课程还能不能排得开。最简单有效的打分方式是统计“该时段下所有可选教室的空闲率”和“该类别课程已经占用的时段数”越不拥挤的时段分数越低。3.2 四种冲突判定不能只查班级课表写完贪心最需要谨慎的就是冲突判定函数。只检查班级是否有课是最常见的初级错误真实排课系统中至少有四种冲突必须硬性拦截——班级冲突、教师冲突、教室冲突、连堂课冲突。前三种是组合式冲突最后一种是时间跨度约束。我把所有判定收敛到一个静态类中便于回溯阶段反复调用。public static class ConflictChecker { // 判断某个时段能否安排某门课 public static bool IsAllowed(ScheduleItem target, ListScheduleItem existing) { // 班级冲突同一班级同一时段不能有第二门课 // 教师冲突同一教师同一时段不能分身到两个班 foreach (var item in existing) { if (item.DayOfWeek ! target.DayOfWeek || item.Period ! target.Period) continue; if (item.ClassId target.ClassId) return false; if (item.TeacherId target.TeacherId) return false; if (item.RoomId target.RoomId) return false; } // 连堂课冲突连续两节必须在同一教室 if (target.IsContinuous existing.Any(item item.ClassId target.ClassId item.DayOfWeek target.DayOfWeek item.Period target.Period - 1)) return false; return true; } }这里有一个容易被忽略的细节连堂课检查只检查了前一节没有检查后一节。因为排课是从第 1 节往第 10 节顺序分配的排到当前课程时后续节次还没有任何数据所以只需要向后检查存在性。但要注意如果采用了随机顺序回溯这个逻辑就必须改写为前后双向检查。这个方法的参数target是待分配项existing是已分配列表调用频率极高应始终在内存中操作不要引入 LINQ 的Count()做完整枚举直接foreach返回就能保持高效。3.3 回溯兜底处理贪心排不进去的课贪心策略在大多数数据组合下能解决 90% 的课程但总会遇到个别课程所有候选时段都被占满的情况。这时需要回溯搜索。回溯的思路是找到一门挂起的课程尝试把已经排好的某门课移动到其他时段给挂起课程腾出位置。每移动完一次检查是否重新引入冲突。bool BacktrackAssign(Course course, ListScheduleItem scheduleItems, int maxDepth) { if (maxDepth 0) return false; // 1. 找出该课程所有可选时段 var slots GetCandidateSlots(course); foreach (var slot in slots) { // 2. 找到这个时段内占用教室或教师的课程 var conflictedItems scheduleItems .Where(s s.DayOfWeek slot.DayOfWeek s.Period slot.Period) .ToList(); // 3. 尝试把冲突课程移到其他时段 foreach (var conflicted in conflictedItems) { var oldDay conflicted.DayOfWeek; var oldPeriod conflicted.Period; scheduleItems.Remove(conflicted); if (TryReassign(conflicted, scheduleItems) TryAddCourse(course, slot, scheduleItems)) { return true; } // 4. 还原现场尝试下一组 conflicted.DayOfWeek oldDay; conflicted.Period oldPeriod; scheduleItems.Add(conflicted); } } return false; }回溯的深度不能设太大否则指数爆炸。一般maxDepth控制在 35 层最合适。超过 5 层仍然排不出来的课程直接写入人工调整队列由教务人员手动安排。一个成熟的源码应该把“机器排不出来的课程”单独输出成报表而不是在界面上弹一个笼统的“排课失败”提示否则智慧校园项目的对接方根本不知道要改什么。3.4 界面刷新卡顿问题通常不在排课算法上热词里反复出现“C# 循环数据采集和 UI 刷新卡顿”这个问题在排课系统里同样存在。排课算法本身是计算密集型的如果直接把回溯过程的每一次分配都同步刷到 DataGridView 上界面重绘时间会远超计算时间。我一般会在后台线程跑算法用IProgressT按“每排完一门课”的频率回报进度而不是每个时段都回报一次。// 利用 IProgressT 实现低频率 UI 进度刷新 var progress new Progressstring(msg { lblStatus.Text msg; dataGridView1.DataSource scheduleItems .Where(s s.ClassId currentClassId) .ToList(); }); await Task.Run(() { foreach (var course in orderedCourses) { AssignCourse(course); progress.Report($已完成 {assignedCount}/{totalCount} 门课程分配); } });Progressstring的回调会捕获 UI 线程的 SynchronizationContext所以回调内直接操作控件是安全的。关键是Report的调用频率——每完成一门课报告一次既能看到整体进度又不会让 DataGridView 陷入频繁刷新。等到全部完成后再做一次完整数据绑定体验最流畅。4. 源码落地时最容易出错的三个边界问题4.1 文本解析从 Excel 导入课程数据时先清理不可见字符排课系统的数据源经常来自教务处导出的 Excel而 Excel 单元格里偶尔会混入换行符、不间断空格、全角空格。C# 里用String.Trim()无法去掉这些字符导致课程编号匹配不上而出现假冲突。我通常在读取单元格后执行一次正则清洗把非打印字符全部移除再做匹配。这种问题在源码交付后极难排查因为数据从界面看是完全正常的只有比对 ASCII 码才会暴露差异。4.2 单双周与连堂课不能做成两个独立布尔字段很多源码把单双周、连堂课分开处理但真实需求往往是“单周连续两节双周不排”或者“连堂课跨第 4、5 节且中午不休息”。如果代码里把两个字段独立判断就会出现组合爆炸式的逻辑漏洞。我的处理方式是在ScheduleItem中加入一个PatternType枚举把“单周连堂”“双周连堂”“每周连堂”“单周单节”等预定义好再统一交给一个状态机解析。这样写虽然前期代码多一点但后面排课算法里只用判断IsMatch(weekType, patternType)一个方法维护成本反而最低。4.3 验证排课结果用 SQL 查冲突比肉眼快最后给出一个验证 SQL把排课结果写回数据库后执行它能够快速找出教师冲突的记录-- 找出同一教师在同一时段出现在两个班的冲突记录 SELECT a.teacher_id, a.day_of_week, a.period, a.class_id AS class_a, b.class_id AS class_b FROM t_schedule a JOIN t_schedule b ON a.teacher_id b.teacher_id AND a.day_of_week b.day_of_week AND a.period b.period AND a.schedule_id b.schedule_id;这条 SQL 的核心是利用schedule_id b.schedule_id条件将两两配对的记录去重只保留每组冲突中的一对。如果查询结果为空教师维度的冲突就已清零。类似地把teacher_id换成class_id或room_id就能分别检查班级课表和教室占用冲突。源码交付前应该把这三条 SQL 存成一个.sql脚本文件连同排课系统一起提供给校方作为验收的依据。本文还有配套的精品资源点击获取