如何找到连接不同联合体之间不同节点的最佳方式？

Question

描述：

有1000个并集，每个并集包含x个节点（x是1~100之间的随机值）。现在我们可以创建从联合 A 中的一个节点到联合 B 中的另一个节点的连接。

规则是：

1. one node only accepts just one connection. 
2. The connection must be across different unions.

同样，尽可能多地建立这样的联系。

最后可能还有几个节点无法连接，因为其他联合中没有其他可用节点

例如：

Union 1: a b c
Union 2: d e
Union 3: f g h i j

如果我们选择以下连接方式：

U1.a <-> U2.d
U1.b <-> U2.e
U1.c <-> U3.f

联合 3 中的 h i j 将被保留。

但是如果我们使用另一种连接方式：

U1.a <-> U3.f
U1.b <-> U3.g
U1.c <-> U3.h
U2.d <-> U3.i
U2.e <-> U3.j

那么就没有节点了。

所以问题是：

我们如何设计算法来尝试找到使无连接节点最少的最优解？

Answer 1

这看起来像一个 matching problem 你的图表是：

G=(V,E), 
V = {all nodes}, 
E={(u,v) | u and v not in same union}

可以解决，比如Blossom algorithm

Answer 2

这等同于partition problem，其中输入多重集中的每个元素都是并集的长度。此外，这个问题总是可以通过在 O(n) 时间内运行的简单贪婪实现来解决。例如，考虑以下输入：

Union 1: a a a
Union 2: b b b b b b b b b
Union 3: c c c c c c c c c c
Union 4: d d d d d d d d d d 
Union 5: e e

简单贪心算法创建两个输出列表。对于每个联合（从具有最多元素的联合开始），联合的元素被添加到较短的输出列表中。结果是两个这样的列表：

c c c c c c c c c c b b b b b b b b b
d d d d d d d d d d a a a e e

下一步是从较长列表的末尾取出一些项目并将它们添加到较短列表的开头。在此示例中，移动了两个 b：

c c c c c c c c c c b b b b b b b 
b b d d d d d d d d d d a a a e e

那么，它会一直有效吗？是的，唯一的例外是当一个联合包含超过一半的项目总数时。在这种情况下，不会从较长的列表中移动任何项目。

这是 python 中的示例实现：

inputList = [['a','a','a'],
            ['b','b','b','b','b','b','b','b','b'],
            ['c','c','c','c','c','c','c','c','c','c'],
            ['d','d','d','d','d','d','d','d','d','d'],
            ['e','e']]
topCount = 0
botCount = 0
topList = []
botList = []

# sort the input in descending order based on length
inputList = sorted(inputList, key=lambda x:len(x), reverse=True)

# greedy partitioning into two output lists
for itemList in inputList:
    if topCount <= botCount:
        topList += itemList
        topCount += len(itemList)
    else:
        botList += itemList
        botCount += len(itemList)

# move some elements from the end of the longer list to the beginning of the shorter list
if topList[0] != topList[-1]:
    if topCount > botCount+1:
        excess = (topCount - botCount) // 2
        botList = topList[-excess:] + botList
        topList = topList[:-excess]
    elif botCount > topCount+1:
        excess = (botCount - topCount) // 2
        topList = botList[-excess:] + topList
        botList = botList[:-excess]

print topList
print botList

输出为：

['c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'b', 'b', 'b', 'b', 'b', 'b', 'b']
['b', 'b', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'a', 'a', 'a', 'e', 'e']

如何找到连接不同联合体之间不同节点的最佳方式？

How to find a best way to connect different nodes between different unions?

algorithm

graph-algorithm