3

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?

Clive Tooth
  • 163
  • 9
  • Forgetting for a moment that this may be the wrong space for this question, it's possible that you could adapt The Travelling Salesman problem to this requirement. Here's one link: https://stackoverflow.com/questions/25585401/travelling-salesman-in-scipy – John Joseph Aug 24 '21 at 16:03
  • Here's a way to do it, O(n): https://www.geeksforgeeks.org/minimum-distance-to-visit-all-the-nodes-of-an-undirected-weighted-tree/ – lmonninger Aug 24 '21 at 16:09
  • @Imonninger it's not the same question. – TYeung Aug 24 '21 at 16:11
  • 1
    [Assignment problem](https://en.wikipedia.org/wiki/Assignment_problem) perhaps? – user58697 Aug 24 '21 at 16:14
  • Those type of graphs are called Bipartite graph. If I am not mistaken lecture of this https://www.degruyter.com/document/doi/10.2478/s13537-013-0110-4/html should help with solving your problem. – Bartosz Szymański Aug 24 '21 at 16:16

2 Answers2

7

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.

TYeung
  • 2,579
  • 2
  • 15
  • 30
1

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] ))
Jean Valj
  • 119
  • 4