对于我之前提出的问题,有一个循环解决方案。它适用于偶数人员,但是一旦实施算法并对其进行尝试,所有建议都将失效。我尝试了许多变体,((将最后一个和其他一群人分组,第二个小组最后一个小组,不同的组合,第二行和第四行到最后一行的最后一行,我认为这会给我最大的收获)最佳解决方案,但仍然有很多重复项)。有人可以提出一条可行的解决方案,还是一个证明,如果没有两个人在一起工作超过一次,就无法找到解决方案,那么我就可以停止尝试使之工作。如果您想要用Java实现的算法,我可以发布它,以便您可以使用它。
谢谢。
23名2人和1人3组的学生14周的时间不足,因此本地搜索能够找到解决方案。
18 1 11| 3 4| 5 7| 9 6| 0 17| 2 12| 10 19| 15 16| 21 8| 14 20| 13 22| 6 13 18| 17 4| 5 0| 20 1| 12 11| 10 9| 2 14| 15 7| 3 8| 19 16| 21 22| 21 17 7| 19 22| 3 1| 2 8| 0 10| 14 12| 13 11| 6 16| 5 15| 18 20| 9 4| 8 1 13| 18 2| 6 11| 20 0| 12 10| 14 15| 5 17| 9 21| 4 19| 3 22| 16 7| 0 4 16| 17 20| 21 3| 7 18| 13 19| 1 5| 9 11| 15 2| 14 8| 10 6| 12 22| 12 1 17| 15 4| 8 6| 16 18| 9 0| 11 22| 5 14| 3 2| 7 13| 19 20| 21 10| 4 1 22| 12 8| 15 6| 7 0| 9 17| 11 3| 13 2| 5 18| 10 14| 19 21| 20 16| 0 1 6| 13 21| 15 12| 17 8| 20 10| 11 4| 3 14| 5 16| 7 2| 19 9| 18 22| 13 16 3| 2 9| 11 20| 6 17| 22 10| 5 12| 0 14| 15 1| 8 18| 19 7| 21 4| 14 1 7| 2 4| 5 9| 3 6| 8 10| 13 12| 21 0| 17 16| 22 20| 19 18| 11 15| 14 18 21| 12 4| 5 6| 2 19| 8 20| 1 9| 13 0| 11 16| 17 15| 3 10| 7 22| 21 6 2| 3 20| 5 13| 16 8| 18 17| 0 12| 22 14| 10 1| 9 15| 7 4| 11 19| 0 11 2| 6 4| 16 14| 7 8| 17 10| 1 19| 13 9| 3 18| 21 12| 20 5| 15 22| 1 16 2| 14 13| 3 7| 8 4| 11 10| 9 12| 0 18| 15 19| 17 22| 6 20| 21 5|
这是实现它的Java代码。
public class Schedule { private final int weekCount; private final int groupCount; private final int personCount; private final int groupFirstSlot[]; private final int weekSlotPerson[][]; public Schedule(int weekCount, int groupCount, int personCount) { this.weekCount = weekCount; this.groupCount = groupCount; this.personCount = personCount; int remainingPersonCount = personCount; this.groupFirstSlot = new int[groupCount + 1]; for (int remainingGroupCount = groupCount; remainingGroupCount > 0; remainingGroupCount--) { groupFirstSlot[remainingGroupCount] = remainingPersonCount; remainingPersonCount -= remainingPersonCount / remainingGroupCount; } this.weekSlotPerson = new int[weekCount][personCount]; for (int week = 0; week < weekCount; week++) { for (int person = 0; person < personCount; person++) { weekSlotPerson[week][person] = person; } } } public int getWeekCount() { return weekCount; } public int getGroupCount() { return groupCount; } public int getPersonCount() { return personCount; } public int getGroupFirstSlot(int group) { return groupFirstSlot[group]; } public int getWeekSlotPerson(int week, int slot) { return weekSlotPerson[week][slot]; } public void swapWeekSlotPerson(int week, int slotOne, int slotTwo) { int temp = weekSlotPerson[week][slotOne]; weekSlotPerson[week][slotOne] = weekSlotPerson[week][slotTwo]; weekSlotPerson[week][slotTwo] = temp; } public int getConflictCount() { int pairCount[][] = new int[personCount][personCount]; for (int week = 0; week < weekCount; week++) { for (int group = 0; group < groupCount; group++) { for (int slotOne = groupFirstSlot[group]; slotOne < groupFirstSlot[group + 1]; slotOne++) { int personOne = weekSlotPerson[week][slotOne]; for (int slotTwo = groupFirstSlot[group]; slotTwo < groupFirstSlot[group + 1]; slotTwo++) { int personTwo = weekSlotPerson[week][slotTwo]; pairCount[personOne][personTwo]++; } } } } int conflictCount = 0; for (int personOne = 0; personOne < personCount; personOne++) { for (int personTwo = personOne + 1; personTwo < personCount; personTwo++) { int pc = pairCount[personOne][personTwo]; conflictCount += pc * (pc - 1) / 2; } } return conflictCount; } public static void main(String[] args) { Schedule sched = new Schedule(14, 11, 23); java.util.Random rand = new java.util.Random(); int oldCc = sched.getConflictCount(); while (oldCc > 0) { int week = rand.nextInt(sched.getWeekCount()); int slotOne = rand.nextInt(sched.getPersonCount()); int slotTwo = rand.nextInt(sched.getPersonCount()); sched.swapWeekSlotPerson(week, slotOne, slotTwo); int newCc = sched.getConflictCount(); if (newCc < oldCc) { oldCc = newCc; } else { sched.swapWeekSlotPerson(week, slotOne, slotTwo); } } for (int week = 0; week < sched.getWeekCount(); week++) { for (int group = 0; group < sched.getGroupCount(); group++) { for (int slot = sched.getGroupFirstSlot(group); slot < sched.getGroupFirstSlot(group + 1); slot++) { System.out.printf("%3d", sched.getWeekSlotPerson(week, slot)); } System.out.print('|'); } System.out.println(); } } }