选修课两时段调度优化：寻求非暴力破解的优雅方案

核心问题转化 #

你的需求本质等价于无向图的最大割问题，可以将课程分配问题映射为图优化问题，彻底规避n!复杂度的暴力枚举：

• 目标：把8门课分成两个时段集合，最大化"前两个志愿分属不同时段"的学生总数
• 等价性：跨时段的课程对对应的学生都能修读前两志愿，我们要最大化这类学生的总和

图论建模步骤 #

1. 节点定义：每门选修课对应图中一个节点（共8个节点）
2. 边权重定义：构建对称权重矩阵W，其中W[u][v]表示所有"前两个志愿是u和v（顺序不限）"的学生总数
3. 模型对应：课程的两个时段分配对应图的节点二分划分，最大化的目标就是跨两个划分的边权重总和——这些边对应的课程对分属不同时段，对应的学生都能满足修读需求

高效求解方式 #

小规模场景（n=8） #

直接枚举所有有效二分划分即可，总共有2^(8-1)-1=127种不同分配（固定一门课的时段，避免重复计算），对比n!的40320次枚举，效率提升几个数量级。

代码实现（基于NetworkX的最大割求解） #

import networkx as nx

# 示例对称权重矩阵：W[i][j]为同时选i、j作为前两志愿的学生数
weight_matrix = [
    [0, 5, 3, 2, 1, 0, 4, 2],
    [5, 0, 4, 1, 0, 3, 2, 1],
    [3, 4, 0, 6, 2, 1, 0, 3],
    [2, 1, 6, 0, 5, 2, 1, 0],
    [1, 0, 2, 5, 0, 4, 3, 2],
    [0, 3, 1, 2, 4, 0, 5, 1],
    [4, 2, 0, 1, 3, 5, 0, 6],
    [2, 1, 3, 0, 2, 1, 6, 0]
]

# 构建加权无向图
G = nx.Graph()
for i in range(8):
    for j in range(i+1, 8):
        if weight_matrix[i][j] > 0:
            G.add_edge(i, j, weight=weight_matrix[i][j])

# 求解最大割（小规模场景可直接用精确解法）
max_students, partition = nx.maximum_cut(G)

print(f"最多可满足修读前两志愿的学生数: {max_students}")
print(f"时段1课程编号: {list(partition[0])}")
print(f"时段2课程编号: {list(partition[1])}")

大规模场景扩展 #

如果后续课程数增加，可使用Goemans-Williamson近似算法（近似比约0.878），NetworkX也提供了对应的近似实现nx.approximation.max_cut。

矩阵视角的公式表达 #

用0-1变量x_i表示课程i的时段：x_i=0代表时段1，x_i=1代表时段2。目标函数可写为：

最大化 sum_{u<v} W[u][v] * |x_u - x_v|

其中|x_u - x_v|=1当且仅当u、v分属不同时段，此时累加对应的学生数，正好是我们需要的最大化目标。

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