一尘不染

如何解决柯克曼斯女学生的这种变化

algorithm

我正在尝试实现一个将s学生分配给g个实验室组中的l个实验室的应用。约束是:

1:每个实验室的学生应与新学生一起工作。2:所有学生必须成为实验室负责人一次。

如果不能在实验组中平均分配学生,则2是不可解决的。因此,如果“奇数”的学生从未成为实验室负责人,这是可以接受的。

我尝试了两种方法,但我还不满意。

  1. 禁忌搜索,它解决了1但有问题解决了2(我实际上首先解决了1,然后尝试解决了2,这可能是错误的方法,有任何建议)

  2. 一个简单的解决方案,我将#labs中的学生划分为数组[0..6] [7..14] [15..21],然后旋转(带有0,1,2 inc)并转置矩阵,重复#labs次,重复旋转(1,2,4)和(2,4,6)。在3个实验室中的21个学生中,实验组为7个,结果如下:

    • 实验1:[0、7、14],[1、8、15],[2、9、16],[3、10、17],[4、11、18],[5、12、19] ,[6,13,20]
    • 实验2:[6,12,18],[0、13、19],[1、7、20],[2、8、14],[3、9、15],[4、10、16] ,[5,11,17]
    • 实验3:[5、10、15],[6、11、16],[0、12、17],[1、13、18],[2、7、19],[3、8、20] ,[4,9,14]

实验室负责人是实验室1的第一列,实验室2的第二列…

此解决方案效果不错,但是例如对于3个实验室中的12名学生或6个实验室中的150名学生失败。有什么建议?

2似乎可以处理相同数量的情况或组合,并且与1相比,闪电般快。也许我应该得到一个高贵的价格:-)


阅读 263

收藏
2020-07-28

共1个答案

一尘不染

约束1本身通常被称为社交高尔夫球手问题。(让参数g为组数,s为每组的大小,w为周数。分组是将g * s高尔夫球手划分为g组,大小为s。确定是否可以找到w组,这样每个高尔夫球手最多可分组一次。)社会高尔夫球手问题已在组合优化文献中进行了研究,方法分为三种类型(您可以使用自己喜欢的搜索引擎查找研究文章):

  1. 本地搜索。当w远低于其最大可行值时,此方法有效。Dotú和Van Hentenryck的论文将禁忌搜索应用于社交高尔夫球手问题。

  2. 完成搜索。当w高于或略低于其最大可行值时,这是必要的,但扩展性不是很好。

  3. 代数构造。这就是解决臭名昭著的g = 8 s = 4 w = 10实例的方式。不幸的是,对于许多参数集,尚无构造信息。

要分配实验室负责人,请计算学生与实验室组之间的最大匹配度,如果该学生属于该实验室组,则该学生与实验室组之间将存在一条优势。

2020-07-28