基于遗传算法的排课项目：如何判定无冲突course-table是否存在？

问题本质：图着色问题 #

你的问题可以直接转化为图着色问题——这是解决排课冲突类问题的经典模型：

• 将每门课程视为图中的一个节点
• 如果有任意学生同时选了两门课程，就在这两个节点之间连一条边（表示这两门课不能安排在同一个时段）
• 每个时段对应一种颜色，只要能给所有节点分配颜色且相邻节点颜色不同，就说明存在无冲突的课程表。

具体实现步骤 #

1. 构建冲突图 #

遍历所有学生的选课数据，为每个学生选中的5门课程，两两之间添加一条冲突边（注意避免重复添加同一对课程的边）：

• 示例：如果student_1选了math100、phys100、chem100，则在math100与phys100、math100与chem100、phys100与chem100之间各加一条边。

用邻接表存储冲突图的示例代码：

conflict_graph = {}
# 先收集所有课程并初始化节点
all_courses = set()
for student in all_students:
    for course in student:
        all_courses.add(course)
for course in all_courses:
    conflict_graph[course] = set()

# 添加冲突边
for student in all_students:
    courses = student
    # 遍历当前学生选课的所有两两组合
    for i in range(len(courses)):
        for j in range(i+1, len(courses)):
            c1, c2 = courses[i], courses[j]
            conflict_graph[c1].add(c2)
            conflict_graph[c2].add(c1)

2. 检查着色可行性 #

对于50门课程的规模，用贪心着色算法就能快速验证是否存在可行解：

• 按任意顺序遍历所有课程节点
• 给当前节点分配第一个未被其相邻节点使用的时段（颜色）
• 若所有节点都能分配到不冲突的时段，说明存在无冲突课程表；否则说明不存在。

贪心着色的示例代码：

def is_schedule_possible(conflict_graph):
    time_assignment = {}
    # 遍历所有课程分配时段
    for course in conflict_graph:
        # 收集相邻课程已占用的时段
        used_times = set()
        for neighbor in conflict_graph[course]:
            if neighbor in time_assignment:
                used_times.add(time_assignment[neighbor])
        # 找到第一个可用时段
        current_time = 0
        while current_time in used_times:
            current_time += 1
        time_assignment[course] = current_time
    # 只要能完成分配就说明可行（最多用50个时段必然能完成）
    return True, time_assignment

注：贪心着色不一定能得到最少的时段数，但只要能完成分配，就证明存在可行解。如果需要更少时段，可以调整节点遍历顺序（比如按节点度数从高到低），但你的问题只需要验证可行性，无需最优解。

3. 特殊情况处理 #

• 若存在学生重复选同一门课，直接判定不可行
• 无课程或无学生时，显然存在可行解

总结 #

通过将问题转化为图着色问题，你可以快速验证是否存在无时间冲突的课程表。对于50门课程、500名学生的规模，上述算法在普通电脑上几秒内就能运行完成。

内容的提问来源于stack exchange，提问作者Jesse Jin