1

根据他们的喜好和能力，将两组不同的人配对。

一组人可以同时执行任务 A 和任务 B，但他们中的大多数人只会执行任务 B。在另一组中，他们大多数人只能执行任务 A。

找到一种算法，将能够并愿意执行相同任务的人配对。

4

2 回答 2

0

我知道你想要所有可能的情侣的名单。如果正确，您可以尝试：

  1. 创建所有具有语言能力的辩手的列表
  2. 创建一个包含所有可能的辩论者夫妇的列表，而不考虑语言能力。
  3. 通过删除不相容的夫妇来过滤先前的列表。

步骤 2 和 3 可以合并

在 python 中，它可以写成函数形式：

import itertools as it

# list of debaters as tupple
# [(name, speak english, speak french), ...]
debaters=[
    ('ef1', True, True), ('e2', True, False), ('f3', False, True),
    ('e4', True, False), ('f5', False, True) ]

result=map(
    lambda x: (x[0][0], x[1][0]),
    filter(lambda x: (x[0][1] and x[1][1]) or (x[0][2] and x[1][2]),
           it.combinations(debaters,2)))

print(result)

它将打印：

[('ef1', 'e2'), ('ef1', 'f3'), ('ef1', 'e4'), ('ef1', 'f5'), ('e2', 'e4'), ('f3', 'f5')]

您还可以使用以下方法编写此算法：

def compute(d):
    result = list()
    for i in range(len(d)):
        for j in range(i+1, len(d)):
            if (d[i][1] and d[j][1]) or (d[i][2] and d[j][2]):
                result.append((d[i][0], d[j][0]))
    return result
print(compute(debaters))
于 2015-12-12T21:58:51.707 回答
0

据我了解，该问题可以建模为未加权匹配问题；当且仅当两个参与者共享共同语言时，他们将处于优势地位。然而，这个问题比二部图中的相同问题更难，它可以通过Edmonds的算法在多项式运行时范围内解决。

于 2015-12-12T21:29:54.447 回答