与选择和排名优化匹配的算法 [英] Algorithm for optimal matching with choices and ranking

问题描述

我有以下问题:有 200 名学生需要从 7 个讲座中选择 4 个.它们之间没有不兼容.他们将它们从 1 到 7 进行排名.

I have the following problem: there are 200 students who need to pick 4 lectures out of 7. There is no incompatibility between them. They ranked them from 1 to 7.

是否有一种算法提供可选的分配学生讲座?是否在某处实施/可用?

Is there an algorithm providing an optional assignation student-lectures? Is it implemented/available somewhere?

提前致谢！

推荐答案

有几种方法.下面的一个使用最大流量算法:基本上，您构建一个图表，其中男孩通过他们偏好的容量管道连接到女孩，并在您的图表中最大化流量(n^3 算法).

There are several methods. The following one uses a maximal flow algorithm : basically you build a graph where boys connect to girl with a pipe of capacity their preference, and you maximize flow (n^3 algorithm) in your graph.

以下代码以独特的偏好级别执行此操作，但可以直接适应不同的偏好

Following code does this with unique level of preference but is straightforward adaptable to different preferences

# each boy would accept marriage with some
# of the girl. What wedding would maximize
# happyness ?
MensN=["Brad","John","Chrid","Tom","Zack","Moe","Yim","Tim","Eric","Don"]
WomN=["Olivia","Jenny","Michelle","Kate","Jude","Sonia","Yin","Zoe","Amy","Nat"]
       # O J M K J S Y Z A N
MensP=[[ 0,0,1,0,2,0,0,1,0,0],  # Brad
       [ 1,1,0,0,0,1,1,0,1,0],  # John
       [ 0,0,0,1,1,0,0,1,0,1],  # Chris
       [ 0,1,1,0,0,0,1,0,0,0],  # Tom
       [ 0,0,1,0,0,1,0,1,1,1],  # Zack
       [ 1,0,1,0,1,0,0,1,0,0],  # Moe
       [ 0,0,1,0,0,0,0,0,1,1],  # Yim
       [ 0,1,1,0,0,1,0,0,1,0],  # Tim
       [ 0,0,1,1,1,0,1,0,0,0],  # Eric
       [ 1,0,0,0,1,0,0,1,0,1]]  # Don 
       
#Edmonds-Karp Algorithm for optimal matching

def max_flow(C, s, t):
 F,path=[[0]*len(C) for c in C],s!=t
 while path:
  [path,flow]=bfs(C,F,s,t)
  for u,v in path:
   F[u][v],F[v][u]=F[u][v]+flow,F[v][u]-flow
 return F,sum(F[s])

#find path by using BFS
def bfs(C,F,s,t,f=999999):
 queue,paths=[s],{s:[]}
 while queue: 
  u=queue.pop(0)
  for v in range(len(C)):
    if C[u][v]>F[u][v] and v not in paths:
     paths[v]=paths[u]+[(u,v)]
     f=min(f,C[u][v]-F[u][v])
     if v==t:  return [paths[v],f]
     queue.append(v)
 return([[],999999])    

# make a capacity graph
C=[[0]+[2]*len(MensN)+[0]*len(WomN)+[0]]+[ # Source leads to men
[0]*(1+len(MensN))+p+[0] for p in MensP]+[ # Men lead to women with respective prefs
[0]*(1+len(MensN)+len(WomN))+[2] for w in WomN]+[ # Women lead to target
[0]*(1+len(MensN))+[0]*len(WomN)+[0]]  # Target leads nowhere
[F,n]=max_flow(C,0,len(C[0])-1)
print("It is possible to do",n,"marriage(s)")
for i in enumerate(MensN):
    print (i[1]," chooses ",",".join(WomN[j] for j in range(len(WomN)) if F[1+i[0]][1+len(MensN)+j] ))

这篇关于与选择和排名优化匹配的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！