CODEWITHSUNDEEP
algorithm
Clive Tooth
Clive Tooth

Reputation: 163

Minimum distance between two sets of points

I have a set of n points in a metric space. These points are all colored blue. I have another set of n points in the space. Those points are all colored red. I want to connect the points in such a way that each blue point is connected to exactly one red point and each red point is connected to exactly one blue point. (Obviously there are n! ways of doing this.) I wish to find the set of connections which minimizes the total length of the connections. What is this problem called?

Upvotes: 3

Views: 1188

Answers (2)

Jean Valj
Jean Valj

Reputation: 94

Thr following code (Edmonds-Karp algorithm) solves a similar problem : optimal marriage between two sets (boys and girls). O(n^3) too.

# each boy would accept marriage with some
# of the girl. What wedding would maximize
# happiness ?
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,1,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]+[1]*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))+[1] 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] ))

Upvotes: 1

Y.T.
Y.T.

Reputation: 2729

The problem is called Min weight perfect matching on complete bipartite graph, or Assignment problem,

which is usually phrased as follows:

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized.

The problem can be solved by the Hungarian algorithm, which is O(n^3) in complexity.

Upvotes: 7

Related Questions