2014-01-23 156 views
1

我在查找排序人員數據集的算法時遇到了問題。我儘量詳細解釋:根據票數對人進行排序

故事從一項調查開始。一羣人,可以說600可以選擇20-25個項目。他們做了#1願望,#2願望和#3願望,其中#1是他們想要參與的最想要的項目,並希望3「不完美但最可接受的選擇」。

這些項目的參與人數有限。每個項目可以加入約30人(根據人數和項目數量)。

該算法將人們放在不同的項目中,並應找到最佳組合。

問題是,你不能只把所有的人與他們的號碼1希望X在某個項目和東西所有其他與1號希望X在那裏2號的願望,因爲這不會是最每個人都「最快樂」的情況。

你可能會想到我想表達的意思,當你想象得到他的第一個人的每個人都希望你得到100分,對於每個得到他的第二個願望的人,他都希望得到60分,第三個希望得到30分,他的一個願望0分。而且你希望獲得儘可能多的點數。

我希望你得到我的問題。這是一個學校項目日。 有沒有可以幫助我的東西?你有什麼主意嗎?我會感謝每一次!

親切的問候

回答

3

您可以通過將其作爲最小成本網絡流量問題進行優化來解決此問題。

爲每個人添加一個節點,併爲每個項目添加一個節點。

根據自己的喜好設置人與項目之間的流量成本。

(作爲Networkx提供分鐘費用流,但不是最大費用流我已設置的成本是 負。)

例如,使用Networkx和Python:

import networkx as nx 

G=nx.DiGraph() 

prefs={'Tom':['Project1','Project2','Project3'], 
     'Dick':['Project2','Project1','Project3'], 
     'Harry':['Project1','Project3','Project1']} 

capacities={'Project1':2,'Project2':10,'Project3':4} 

num_persons=len(prefs) 
G.add_node('dest',demand=num_persons) 
A=[] 
for person,projectlist in prefs.items(): 
    G.add_node(person,demand=-1) 
    for i,project in enumerate(projectlist): 
     if i==0: 
      cost=-100 # happy to assign first choices 
     elif i==1: 
      cost=-60 # slightly unhappy to assign second choices 
     else: 
      cost=-30 # very unhappy to assign third choices 
     G.add_edge(person,project,capacity=1,weight=cost) # Edge taken if person does this project 

for project,c in capacities.items(): 
     G.add_edge(project,'dest',capacity=c,weight=0) 

flowdict = nx.min_cost_flow(G) 
for person in prefs: 
    for project,flow in flowdict[person].items(): 
     if flow: 
      print person,'joins',project 

在這種代碼Tom的第一個選擇是Project1,然後是Project2,然後是Project3。

容量字典指定有多少人可以加入每個項目的上限。

+0

哇!太棒了! 我不知道Python或networkx,但我希望我能處理這個,應該不那麼難。還有一個問題。我是否也可以爲項目設置最少人數? – Jannik

+0

當然,您只需設置項目的需求,例如對於Project1至少有10個添加G.add_node('Project1',需求= 10),並減少dest的需求10匹配。 –

0

我的算法是這樣的:

mainloop 
wishlevel = 1 
    loop 
    Distribute people into all projects according to wishlevel wish 
    loop through projects, counting population 
    If population exceeds maximum 
    Distribute excess non-redistributed people into their wishlevel+1 projects that are under-populated 
    tag distributed people as 'redistributed' to avoid moving again 
    endif 
    endloop 
    wishlevel = wishlevel + 1 
loop until wishlevel == 3  
mainloop until no project exceeds max population 

這應該通過數據集進行多次傳遞,直到一切都扯平了。如果您限制重新分配已經重新分配的人員,而這個算法可能會導致無限循環,因爲一個項目會隨着算法進展而填滿此類人員,所以您可以嘗試一下,而不受此限制。

相關問題