如何解决kirkkmans女生这种变化 [英] How to solve this variation of kirkkmans schoolgirls
问题描述
我想实现一个应用程序分配上的学生到L实验室以g实验组。约束条件是：
I am trying to implement an app which assigns s students to l labs in g lab groups. The constraints are:
1：学生应以新的学生每个实验室工作。 2：所有的学生都应该实验室领导人曾经
1:students shall work with new students for every lab. 2:all students shall be lab leader once.
2是不可解如果学生不能均匀地在实验室组划分。 Therfore这是可以接受的，如果奇的学生永远不会成为实验室的领导者。
2 is not solvable if the students can't be divided evenly in the lab groups. Therfore it is acceptable if the "odd" students never get to be lab leader.
我已经尝试了两种方法，但我不幸福了：
I have tried two approaches but I am not happy yet.:
-
禁忌搜索，解决了1，但有解决2个问题（其实我先解决1，然后设法解决2，这可能是错误的做法，有什么建议）
Tabu search, which solves 1 but has problems solving 2 ( I actually first solve 1 and then try to solve 2, which might be the wrong approach, any suggestions)
一个简单的解决方案，我把学生在#labs在数组[0..6] [7..14] [15..21]，然后转动（含0,1,2 INC ）和转置矩阵，为#labs次递增旋转（1,2,4）和（2,4,6）重复此。对于21名学生在3个实验室与7组实验的结果是这样的：
A simple solution where I divide the students in the #labs in an array [0..6][7..14][15..21] and then rotate(with 0,1,2 inc) and transpose the matrix, repeat this for #labs times with incremented rotation (1,2,4) and (2,4,6). For 21 students in 3 labs with lab groups of 7 the result looks like this:
- 实验室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 ...
the lab leaders are the first column for lab 1, the second for lab 2 ...
该解决方案的工作不错，但如失败的12名学生在3个实验室和150名学生在6个实验室。有什么建议？
This solution works decent but for instance fails for 12 students in 3 labs or 150 students in 6 labs. Any suggestions?
2，似乎处理案件或组合相同数量的，而且是快如闪电相比，1。也许我应该得到一个高贵的价格： - ）
2 seems to handle the same number of cases or combinations, and is lightning fast compared to 1. Maybe I should get a noble price :-)
推荐答案
约束＃1单是通常被称为社会的高尔夫球手的问题。 （让参数g为基团和s的数量是每个组和瓦特的大小是周的数目。的分组是一个分区的克* S球手进入大小为S的克团。确定瓦特分组是否可以找到这样每一对球手的组合在一起，最多一次）社会球手问题进行了研究，组合优化文学和途径有三种类型（你可以用你喜欢的搜索引擎查找该研究文章）：
Constraint #1 alone is usually referred to as the social golfer problem. (Let parameters g be the number of groups and s be the size of each group and w be the number of weeks. A grouping is a partition of g * s golfers into g groups of size s. Determine whether w groupings can be found such that each pair of golfers are grouped together at most once.) The social golfer problem has been studied in the combinatorial optimization literature, and the approaches are of three types (you can use your favorite search engine to find the research articles):
-
本地搜索。这是有效的，当w为远低于其最大可行的值。 Dotú和Van Hentenryck 有一纸申请禁忌搜索到社交高尔夫球手的问题。
Local search. This is effective when w is well below its maximum feasible value. Dotú and Van Hentenryck have a paper applying tabu search to the social golfer problem.
完整的搜索。这是必要的，当w是高于或略低于其最大可行值，但它不规模非常好
Complete search. This is necessary when w is above or just below its maximum feasible value but it does not scale very well.
代数结构。这就是臭名昭著的G = 8秒= 4 W = 10情况下得到解决。不幸的是，许多参数设置，没有施工知道。
Algebraic constructions. This is how the notorious g=8 s=4 w=10 instance was solved. Unfortunately, for many parameter sets there is no construction known.
要指定实验室的领导人，计算最大匹配学生和实验组之间，那里有一个学生和实验组之间的边缘，如果该学生属于该实验团队。
To assign lab leaders, compute a maximum matching between students and lab groups, where there is an edge between a student and a lab group if that student belongs to that lab group.
这篇关于如何解决kirkkmans女生这种变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
