将学生与课程限制的课程相匹配(匈牙利语,最大流量,最小成本流程......)

Question

我目前正在编写一个将学生映射到课程的程序.目前,我正在使用SAT-Solver,但我正在尝试实现一个多项式时间/非贪心算法,它解决了以下子问题:

• 有学生(50-150)
• 有科目(10-20),例如'数学','生物','艺术'
• 每个科目(至少一门)都有课程,例如'math-1','math-2','biology-1','art-1','art-2','art-3'
• 学生选择一些(固定的)科目(10-12),并且对于每个科目,学生必须被分配到现有的一门课程(如果可能的话).选择哪个课程'math-1'或'math-2'并不重要.
• 这些课程允许的学生人数最多(20-34)
• 每门课程都在一个固定的区块内(=时间段1到13)
• 学生可能不会被分配到同一区块的课程

我现在描述到目前为止我所做的事情.

(1)忽略课程 - 学生限制

我能够用匈牙利算法/二分匹配来解决这个问题.每个学生可以通过如下建模来单独计算:

• 左节点代表主题'数学','生物','艺术'(学生)
• 右节点表示块'1','2',....'13'
• 从"主题"到"阻止"的每个过程插入一条边

通过这种方式,学生被分配到课程的每个科目,而不参加同一区块的课程.但课程限制被忽略了.

(2)忽略学生的选定科目

我能够用max-flow-algorithm解决这个问题.对于每个学生,建模如下:

• 第1层:从源到每个学生,流量为13
• 第2层:从每个学生到他/她的个人区块,流量为1
• 第3层:从每个学生块到该块中的每个课程,流程为1
• 第4层:通过'max-student-limit'从每个球场到水槽

通过这种方式,学生选择任意课程,并且课程限制已满.但是他/她可能不幸并被分配到'数学-1','数学-2'和'数学-3'而无视主题'生物'和'艺术'.

(3)贪婪的匈牙利人

我的另一个想法是一次匹配一个学生与匈牙利算法并调整权重,以便"更多空课程"是首选.例如,可以建模:

• 左节点是学生的主题
• 右边节点是块
• 对于每个球场,插入一个边缘从主体到球场的块重量=自由座位数

然后计算最大权重匹配.

我真的很感激任何建议/帮助.

谢谢!