我正在嘗試使用匈牙利演算法根據學生的喜好將學生分類。
在我的資料集中，大約有 550 名學生，每個學生都有一個排名前 5 的偏好串列。每個首選項都是一個對應于一個類的 ID。每個班級都有最小和最大容量（在我的情況下，最小上限為 15 人，最大上限為 27 人），資料集中有 21 個班級。
這是每個學生的示例資料集：
| 電子郵件 | 第一選擇 | 第二選擇 | 第三選擇 | 第四選擇 | 合適的選擇 |
|---|---|---|---|---|---|
| 電子郵件@gmail.com | 4 | 7 | 1 | 8 | 21 |
| [email protected] | 6 | 9 | 14 | 17 | 2 |
這是每個類的示例資料集：
| 班級名稱 | 班級號 | 最小帽 | 最大上限 |
|---|---|---|---|
| 班級標題1 | 1 | 15 | 27 |
| 類標題2 | 2 | 15 | 27 |
| 班級標題3 | 3 | 15 | 27 |
我需要將學生分類到他們喜歡的班級，同時還要遵循最小容量和最大容量。為此，我打算使用匈牙利演算法。
因為有大約 550 名學生和 21 個班級，并且為了讓匈牙利演算法起作用，我打算制作這些班級的“副本”。我會首先為每個班級（如班級 1.1、1.2、1.3、1.4、2.1、2.2、2.3 等）制作 15 個副本以滿足班級的最低要求，然后將更多副本添加到最流行的班級中直到有相同數量的學生和班級副本。
然后，根據學生的副本和偏好，我正在考慮制作一本字典并使用該演算法的實作。
我有幾個問題：
- 這個計劃是一個好的計劃還是有更好的解決方案來解決我遇到的問題？
- 如何制作所有鏈接回原始 ID 的類的副本？
- 在將其實作到演算法中時，我應該將學生的偏好放入字典中（如 GitHub 鏈接所示），但如果現在有 1.1 等 ID，人們的選擇是 1，并且沒有像這樣的實際類演算法，我應該如何解決？
提前謝謝您，如果您需要任何澄清，請告訴我
uj5u.com熱心網友回復：
因為學生只陳述了 5 個選項，所以可能無法完美匹配。如果您不希望產生完美的匹配，那么您可以使用serial dictatorship。它會比匈牙利演算法快得多。
一個偽代碼：
students = list of students
for stud in students:
if the number of students yet to be matched is greater than total of minimum quotas:
if [classes in stud's preference list that have not reached max capacity]:
stud is assigned to their most preferred among them
update the class's remaining seats
else:
stud is unmatched
else:
if [classes in stud's preference list that have not reached min capacity]:
stud is assigned to their most preferred among them
update the class's remaining seats
else:
stud is unmatched
uj5u.com熱心網友回復：
我認為這應該可行，盡管我會做一個改變。不要從每個類的最小副本開始，而是從最大值開始。有 550 名學生和 21 個班級，所有班級都將幾乎滿員。您不必擔心最低限度。
就像你說的那樣會起作用。1 類變為 1.1、1.2 和 1.3，您可以輕松地將其反轉。
由于您要“復制”類，因此您也必須“復制”ID。如果班級 1 變為 1.1、1.2 和 1.3，則更喜歡班級 1 的學生應該以相同的優先級鏈接到班級 1.1、1.2 和 1.3。
我看到的主要問題是 Python 很慢，看起來你有 550 個學生 * 5 個選擇 * 21 個班級 * 27 個容量 = 1,559,250 個連接。這將占用大量記憶體和大量時間，并且該存盤庫上的未解決問題并沒有讓我對它能夠計算這一點充滿信心。我自己測驗了一些具體案例，但其中一個案例陷入了無限回圈。如果您想為此使用 Python，我建議您改用Brian M. Clapper 的實作，因為我也測驗過它并且沒有遇到任何問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/420166.html
標籤：