尋找一種巧妙的方式來排序一組數據

-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），它比機械地將最低位和最高位進行配對要靈活一些，但並不是所有分區都會使整體錯誤最小化（不過，）。這可能是一個很好的第一步，然後可以採用爬山方法，將元素對交換直至找到局部最優解。 –

尋找一種巧妙的方式來排序一組數據

回答

相關問題