讓學生與實驗室配對

我們在一所大學的理學碩士課程中遇到了一個實際問題，在該大學中，學生必須被分配到實驗室。所涉及的數字並不是很大，所以我不是在尋找一個快速的解決方案，而是一個易於理解的解決方案，以便爲學生和小組負責人提供所提議配對的理由。讓學生與實驗室配對

鑑於2列表

S1 Li,Lj,Lk 
S2 Lu,Lv,Lw 
. 
Sn

這裏每個學生s已上市的前3個實驗室中的優先順序。所以學生S1理想情況下會喜歡在實驗室我。如果該實驗室不需要他，那麼他會想要進入Lab j等等。

和

L1 Si,Sj,Sk 
L2 Su,Sv,Sw,Sx,Sy 
. 
Lm

其中每個實驗室列出的學生，他們希望在實驗室。因此，如果實驗室1選擇了本實驗室（他的前三個選擇之一），那麼實驗室1會首先要求學生i。請注意，實驗室可以挑選儘可能多的學生。

約束條件是每個學生只能在一個實驗室中，但每個實驗室可能有0,1或更多的學生。

的目標是生產中，所有學生被分配到實驗室匹配（SI，LJ）和配對導致最大滿意。

的滿意分數被定義爲

Z=sum_{i=1..n}(sum_{j=1...m} (abs(i-j))

直觀這個嘗試配對的許多學生和實驗室用他們最好的選擇。

所以我尋求其目的的解決方案是最小化Z.

一種可能的部分解決方案該優化算法的算法如下：

定義的陣列稱爲分配的長度L的和初始化它全是假的

首先，匹配的第一選擇和放棄這些學生

for each s in {S1,..,Sn}: 
     Assigned[s]=False 
Assigned[s]=j 
repeat until all(Assigned)==True: 
for each s in S: 
    if RANK(Lj,s)==1: 
      Assigned[s]=j # i.e. pair student s with lab Lj 
      del(S,s) # delete s from the list S

函數RANK（ Lj，s）返回實驗室j中首選學生列表中的位置。如果學生不在實驗室j中想要的學生名單中，則返回無窮大。

我不知道應該怎麼還是這種方法可以減少分數Z.

任何幫助將非常感激進行。

來源

2017-02-19 Lee Sande

在我看來，你正試圖解決https://en.wikipedia.org/wiki/Assignment_problem的一個實例，因此可以通過例如。 https://en.wikipedia.org/wiki/Hungarian_algorithm。分配問題就代理和任務而言。這裏的代理人可能是學生，而且任務是實驗室的空閒插槽。如果您的空閒空檔比學生多，那麼您可以創建虛擬學生，將任何虛擬學生分配給任何空閒位置的成本始終相同。

你可能想看看https://en.wikipedia.org/wiki/Stable_marriage_problem和它指向的醫院/居民問題。這看起來像是試圖解決你正在看的那類問題，但它可能不會使用你特定的滿意度分數。這些解決方案已經足夠長，可以針對您未提及的潛在政治問題進行測試。是否有誘因讓人們對自己的偏好說謊？解決方案是否會導致兩個學生同意在作業後想要交換分配的位置的情況？

來源

2017-02-19 05:43:33 mcdowella

讓學生與實驗室配對

回答

相關問題