根据票数对人进行排序

我在查找排序人员数据集的算法时遇到了问题。我尽量详细解释：根据票数对人进行排序

故事从一项调查开始。一群人，可以说600可以选择20-25个项目。他们做了＃1愿望，＃2愿望和＃3愿望，其中＃1是他们想要参与的最想要的项目，并希望3“不完美但最可接受的选择”。

这些项目的参与人数有限。每个项目可以加入约30人（根据人数和项目数量）。

该算法将人们放在不同的项目中，并应找到最佳组合。

问题是，你不能只把所有的人与他们的号码1希望X在某个项目和东西所有其他与1号希望X在那里2号的愿望，因为这不会是最每个人都“最快乐”的情况。

你可能会想到我想表达的意思，当你想象得到他的第一个人的每个人都希望你得到100分，对于每个得到他的第二个愿望的人，他都希望得到60分，第三个希望得到30分，他的一个愿望0分。而且你希望获得尽可能多的点数。

我希望你得到我的问题。这是一个学校项目日。有没有可以帮助我的东西？你有什么主意吗？我会感谢每一次！

亲切的问候

来源

2014-01-23 Jannik

您可以通过将其作为最小成本网络流量问题进行优化来解决此问题。

为每个人添加一个节点，并为每个项目添加一个节点。

根据自己的喜好设置人与项目之间的流量成本。

（作为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。

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

来源

2014-01-23 19:45:16

哇！太棒了！我不知道Python或networkx，但我希望我能处理这个，应该不那么难。还有一个问题。我是否也可以为项目设置最少人数？ – Jannik

当然，您只需设置项目的需求，例如对于Project1至少有10个添加G.add_node（'Project1'，需求= 10），并减少dest的需求10匹配。 –

我的算法是这样的：

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

这应该通过数据集进行多次传递，直到一切都扯平了。如果您限制重新分配已经重新分配的人员，而这个算法可能会导致无限循环，因为一个项目会随着算法进展而填满此类人员，所以您可以尝试一下，而不受此限制。

来源

2014-01-23 19:25:08 Anachronist

根据票数对人进行排序

回答

相关问题