寻找一种巧妙的方式来排序一组数据

-1

我有一组80名学生，我需要将它们分成20组4.我有他们以前的考试成绩来自先决条件模块，我想确保排序的组成员分数的平均值尽可能接近先前考试分数的总体平均值。寻找一种巧妙的方式来排序一组数据

对不起，如果不是特别清楚。

这里的问题的快照：

Student Score 
AA   50 
AB   45 
AC   80 
AD   70 
AE   45 
AF   55 
AG   65 
AH   90

所以分数的平均这里为62.5。我最好将这八名学生分成两组，每组四人，两组的平均考试分数尽可能接近62.5。

我的问题正是这个，但有80个数据点（20个组）而不是8个（2个组）。

我越想越觉得这个问题越困难。

有没有人有任何想法？

谢谢

来源

2017-09-27 Juggler

“我越看越这个问题就越难看” - 事实上，这是NP-Hard。这是*多路分区问题*。演化算法方法对于你的规模问题是一个合理的策略，并且不难实现。 –

恐怕以上所有内容对我而言都是陌生的。我担心我可能会在这里深入... – Juggler

首先按照分数排序goup。因此，它变成了：

AH 90 
AC 80 
..... 
AB 45 
AE 45

然后开始combinning第一与最后：

(AE, AH, 67.5) 
(AB, AC, 62.5) 
(AD, AA, 60) 
(AG, AF, 60)

等都在另一种情况下，你会用两个二者结合起来。前两个与最后两个。

另一种方式：

1. Find all the possible groups by 4 students. 
2. Then for every combination of groups find the abs deviation from the average score and SUM it up for the combination of groups. 
3. Choose the combination of groups with the lowest sum.

来源

2017-09-27 10:58:12 sshopov

这完全是一种启发式。你有什么理由认为这是一个特别好的启发式吗？首先，当分数偏离某一方向而不是落入钟形曲线时，似乎表现得相当差。 –

有1.78 x 10^91种方法可以将80名学生分成20个大小为4的小组。您的最后一段描述了一种不可行的蛮力方法。 –

起初，我没想到上下匹配选项。然而，约翰强调，结果肯定不是最优的：

Scores    Students       Avg. 
40 94 40 94  'AE' 'DA' 'AI' 'AR'  67 
40 90 40 88  'AK' 'CI' 'AM' 'BP'  64.5 
40 85 40 80  'AQ' 'AW' 'AT' 'BD'  61.25 
40 79 40 77  'AU' 'BC' 'AV' 'AB'  59 
40 76 40 75  'AX' 'CG' 'AZ' 'CQ'  57.75 
40 75 40 75  'BF' 'CB' 'BN' 'BQ'  57.5 
40 75 40 74  'BR' 'BI' 'CF' 'CZ'  57.25 
40 74 40 74  'CK' 'CO' 'CP' 'AL'  57 
40 72 41 71  'DB' 'CN' 'AG' 'BO'  56 
41 71 42 70  'CD' 'BM' 'AH' 'BS'  56 
42 70 42 69  'BG' 'BL' 'CU' 'CX'  55.75 
43 68 44 67  'BK' 'CY' 'AD' 'CE'  55.5 
44 64 44 64  'BJ' 'CR' 'BZ' 'BY'  54 
45 64 45 63  'BW' 'BV' 'CS' 'BE'  54.25 
45 62 47 60  'CV' 'CH' 'AC' 'CM'  53.5 
47 59 47 58  'BT' 'AY' 'CL' 'AP'  52.75 
47 57 48 57  'CT' 'BA' 'BX' 'AS'  52.25 
48 56 49 56  'CA' 'AJ' 'AN' 'AA'  52.25 
50 55 50 54  'BB' 'AF' 'CJ' 'AO'  52.25 
51 52 51 52  'CC' 'BU' 'CW' 'BH'  51.5

来源

2017-09-27 12:08:14 Juggler

一个可能的解决方案：

我会尝试用贪心算法，通过与其他学生配对每一个学生开始去让你最接近你的目标平均水平。在初始配对之后，您应该能够使用相同的方法使第一对中的后续配对成为可能。

经过第一轮配对后，此方法利用平均两个平均值并将其与目标平均值进行比较以创建后续群组。你可以阅读更多关于为什么将这个问题here.

不过工作，

这不一定给你最佳的解决方案，相反却是一种启发式的技术来解决这个问题。下面的一个着名例子是当一个低值必须被三个高值抵消以达到目标平均值时。这种类型的分组将不会被这种技术考虑。然而，如果你知道你有一个相对正常的分布以你的目标平均值为中心，那么我认为这种方法应该给出一个体面的近似值。

来源

2017-09-27 13:25:37

这种方法的问题在于没有理由认为在最佳解决方案中，4个组将以2个组将接近目标平均值的方式分成2个组。这种情况并不罕见，例如，一个单一的非常低的分数，需要通过3个高分来平衡，以至于任何一对都将远远低于平均水平。不过，对于某些发行版来说，这可能是一个合理的启发式。 –

正确，因为这是一种贪婪的技术，这意味着这可能无法实现全局最优解决方案。但是，有了这个问题，就不能保证你可以按照每个小组总是满足目标的方式划分学生。相反，您的总体目标是最小化错误，并通过在每个分区选择本地最佳分组，整体错误应该最小化。这种方法也很容易实现，并且在每个分区的合理执行时间为O（n^2）时运行。 –

我同意这是一个合理的启发式方法（所以+1），它比机械地将最低位和最高位进行配对要灵活一些，但并不是所有分区都会使整体错误最小化（不过，）。这可能是一个很好的第一步，然后可以采用爬山方法，将元素对交换直至找到局部最优解。 –

寻找一种巧妙的方式来排序一组数据

回答

相关问题