Сортировка людей в группы на основе голосов

Question

У меня проблема с поиском алгоритма для сортировки набора данных людей. Я стараюсь объяснить как можно подробнее:

История начинается с опроса. Куча людей, скажем, 600 может выбирать между 20-25 проектами. Они делают # 1-пожелание, # 2-пожелание и # 3-пожелание, где # 1 - самый разыскиваемый проект, который они хотят принять, и желать 3 «не идеального, но наиболее приемлемого-выбрать».

Эти проекты ограничены по количеству участников. В каждом проекте может участвовать около 30 человек (в зависимости от количества людей и количества проектов).

Алгоритм ставит людей в разные проекты и должен найти наилучшую комбинацию.

Проблема заключается в том, что вы не можете просто поместить всех людей с их желанием № 1 в конкретный проект и передать все остальное с номером 1 желаемого X, там есть номер 2, потому что это не будет самым «самая счастливая» ситуация для всех.

Возможно, вы можете думать о том, что я имею в виду, когда вы представляете, что для всех, кто получает свой номер 1, вы получаете 100 очков, поскольку каждый, кто получает свой номер 2, желает 60 очков, номер 3 желает 30 очков и кто не попадает в одно из его пожеланий - 0 очков. И вы хотите получить как можно больше очков.

Надеюсь, вы получите мою проблему. Это для школьного проекта. Есть ли что-то, что могло мне помочь? Есть ли у вас какие-либо идеи? Я был бы благодарен за каждый троп!

Сердечные приветы

Answer 1

Вы можете решить эту проблему оптимально, сформулировав ее как проблему расхода сети с минимальными затратами.

Добавить узел для каждого человека и по одному для каждого проекта.

Установите стоимость потока между человеком и проектом в соответствии с их предпочтениями.

(Как 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's number 1 - Project1, затем Project2, затем Project3.

В словаре возможностей указан верхний предел количества людей, которые могут присоединиться к каждому проекту.

Answer 2

Мой алгоритм будет что-то вроде этого:

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 

Это должно сделать несколько проходов через набор данных, пока все не будет выровнен. Этот алгоритм может привести к бесконечному циклу, если вы ограничиваете перераспределение уже перераспределенных людей в том случае, если один проект заполняется такими людьми, как алгоритм прогрессирует, поэтому вы можете попробовать его без этого ограничения.