algorithm - 最大化对数的有效方法

Question

这是最近遇到的一道面试题。 你有 G 位客人(编号从 1 到 G)在一个聚会中。每个客人都有一个长度为 G 的偏好列表，代表他与其他人交谈的偏好。 例如，如果客人 1 的偏好列表是 N Y N N Y(假设有 5 位客人)，那么客人 1 有兴趣与 2 或 5 交谈，而不是其他人。

假设

a) 每位客人只能与另一位客人交谈
b) 如果 a 有兴趣与 b 交谈，则 b 也有兴趣与 a 交谈

给定客人及其偏好矩阵，给出可以保持参与的最大配对数。

Let G = 5;

偏好矩阵是

N Y N N N
Y N Y Y Y
N Y N N N
N Y N N N
N Y N N N

因为我们可以观察到每个人都有兴趣与客人 2 交谈，但他只能与另一个人交谈，所以答案是一对。

我的方法:

我认为它是图论中的最大匹配问题但无法实现 在短时间内。(我不擅长图算法实现)

这是仅使用图表解决的还是有更好、更快的方法？
有贪心的方法吗？

Answer 1

我们可以使用递归和一些内存。请找到一种方法来识别具有 K 个节点和所有关系的图(我们将在下面看到为什么我们需要这个)。在递归过程中，我们应该记录已经解决的案例 (K, R)，其中 K 是客人的数量，R 是这 K 位客人的关系列表。

对于问题 (N, R)，我们将客人编号为 1, 2, ..., N，然后扫描关系列表以获得没有重复的列表(哈希表可能有助于检查重复项)

1 & 2、1 & 4、2 & 3 等

我们需要找到最大的非碰撞对(例如，1 & 2 与 2 & 3 碰撞)。我们可以使用下面的递归算法:

A) 如果 1 和 2 被采用，则删除所有与 1 或 2 的对，并对其余的进行递归。

R_A 将是没有 1 和 2 的剩余关系的列表。我们有 ((N-2), R_A) 的递归

B) 如果跳过 1 和 2，则对其余部分进行递归。

R_B 将是没有链接的剩余关系列表 (1 & 2)。我们有 (N, R_B) 的递归 - 仍然是 N，因为 1 或 2 可能仍保留在完整集中。

C) 检查哪条路线呈现更多的对。

我们需要内存来存储 (K, R) 的结果，因为可能有像 (1, 3, 5, ...) 和 (2, 4, 6, ...) 这样的客人集群，其中客人是 friend 彼此就在簇内。

如果我们使用朴素递归，我们将多次解决相同的问题。但是集群意味着它们的解决方案是对称的。因此，我们需要结合客人数量及其关系来识别图表(重新编号客人会产生相同的图表)。