algorithm - 以最小总线长匹配两个不同大小的集合中的每个点

Question

我在坐标系中绘制了两组点。一组中的每个点都必须与另一组中的至少一个点匹配，通过连接这些点绘制的线的长度总和应尽可能短。说清楚，画线只是一种抽象，实际输出的只是必须匹配的点对。

我看过 this question关于类似的问题，除了在我的情况下没有单链接限制，因为集合可能有不同的大小。有没有什么问题可以描述这种情况？更具体地说，假设每组最多有 10 个点，我可以使用什么算法来解决这个问题？

Answer 1

算法

您可以将其建模为网络流量问题。

通过在第一组中的每个点都有一个 1 的源，在第二组中的每个点都有一个 1 的汇，再加上一个额外的节点 'dest' 用于任何剩余容量，任何有效流将始终连接每个点。

根据点与点之间的距离，用成本在点之间制作边。

到目前为止，我们有一个网络，其解决方案是第 1 组与第 2 组的最低成本匹配(即每个点都有一个链接)。

要允许多个链接，您只需添加以下内容即可:

1. 在 set2 中的每个点和“dest”之间添加 0 权重边(这允许 set 2 中的点多重连接)
2. 在“dest”和 set2 中的每个点之间添加 0 条权重边(这允许 set 1 中的点多重连接)

使用 Networkx 的示例 Python 代码

import networkx as nx
import random

G=nx.DiGraph()

set1=['A','B','C','D','E','F','G','H','I']
set2=['a','b','c']
# Assume set1 > set2 (or swap sets)
assert len(set1)>=len(set2)

G.add_node('dest',demand=len(set1)-len(set2))
A=[]
for person in set1:
        G.add_node(person,demand=-1)
        G.add_edge('dest',person,weight=0)
        for project in set2:
                cost = random.randint(1,10) # Assign appropriate costs here
                G.add_edge(person,project,weight=cost) # Edge taken if person does this project

for project in set2:
        G.add_node(project,demand=1)
        G.add_edge(project,'dest',weight=0)

flowdict = nx.min_cost_flow(G)
for person in set1:
        for project,flow in flowdict[person].items():
                if flow:
                        print person,'->',project