如何解决kirkkman女学生的这种变异
如何解决kirkkman女学生的这种变异
提问于 2012-02-14 10:41:57
我正在尝试实现一个应用程序，它将学生分配给实验室中的l个实验室。制约因素是：
1:每个实验室的学生都要与新生一起工作。他说:所有的学生一次都应该是实验室的领导。
如果学生不能在实验小组中被平均分配，那么2是不可解决的。因此，如果“古怪”的学生永远不能成为实验室的领导，这是可以接受的。
我试过两种方法，但我还不高兴。
- 禁忌搜索，它解决1，但有问题解决2(我实际上先解决1，然后尝试解决2，这可能是错误的方法，任何建议)
- 一个简单的解决方案，我在一个数组0..615.21中将#实验室中的学生分开，然后旋转(用0,1,2 inc)并转置矩阵，用递增的旋转(1,2,4)和(2,4,6)重复#labs。对于3个实验室的21名学生来说，7组实验的结果如下所示：
- lab 1: [0, 7, 14], [1, 8, 15], [2, 9, 16], [3, 10, 17], [4, 11, 18], [5, 12, 19], [6, 13, 20]
- lab 2: [6,12, 18], [0, 13, 19], [1, 7, 20], [2, 8, 14], [3, 9, 15], [4, 10, 16], [5, 11, 17]
- lab 3: [5, 10, 15], [6, 11, 16], [0, 12, 17], [1, 13, 18], [2, 7, 19], [3, 8, 20], [4, 9, 14]
实验室领导是第一实验室的第一列，第二组是第二实验室.
该解决方案运行良好，但例如，3个实验室的12名学生或6个实验室的150名学生都失败了。有什么建议吗？
2似乎处理同样数量的案件或组合，而且与1相比闪电速度快。也许我应该得到一个高尚的价格:-)
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-02-14 14:19:55
限制#1本身通常被称为社会高尔夫球手问题。(设参数g为组数，s为每个组的大小，w为周数。分组是将g* s高尔夫球手划分为g个大小的组。确定是否可以找到w组，以便使每一对高尔夫球手最多一次分组。)在组合优化文献中研究了社会高尔夫球手问题，研究方法有三种(你可以用你最喜欢的搜索引擎找到研究文章)：
- 本地搜索。当w远低于其最大可行值时，这是有效的。多杜和范亨特赖克有一篇论文，将禁忌搜索应用于社会高尔夫球手问题。
- 彻底搜查。这是必要的，当w是高于或略低于它的最大可行值，但它不是很好的规模。
- 代数构造这就是如何解决臭名昭著的g=8 s=4 w=10实例。不幸的是，对于许多参数集，没有已知的构造。
要指定实验室领导，计算学生和实验室组之间的最大匹配，如果学生属于该实验室组，则在学生和实验室组之间有一个边缘。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9275462
复制相关文章
相似问题
腾讯云开发者
