时间戳

首页 > 解决方案 > 与选择和排名进行最佳匹配的算法

algorithm - 与选择和排名进行最佳匹配的算法

问题描述

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

是否有提供可选分配学生讲座的算法？它在某处实施/可用吗？

提前致谢！

标签： algorithm

解决方案

有几种方法。以下使用了最大流量算法：基本上，您构建了一个图，其中男孩用他们喜欢的容量管道连接到女孩，然后在图中最大化流量（n^3 算法）。

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

# 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] ))

推荐阅读