有可能让所有人都满意吗？
Is It Possible to Satisfy Everyone?
给你两组节点，每组节点数相同。集合 A 包含人员列表。集合 B 包含一个项目列表。每个人对集合 B 中任意数量的项目都有偏好。如果我们将这些偏好表示为人员节点和项目节点之间的连接，则每个节点必须至少有一个连接。
起初我以为每个人总能得到他们想要的东西，但事实并非总是如此，例如可能会发生这样的事情：
我的一个想法是，只要图中有（set A size + set B size-1）个或更多连接，就总是可以形成有效连接。但是，我无法证明这一点的正确性。
你知道这是否正确吗？或者是否有完全不同的解决方案？
恐怕你的理论不正确。假设 A 组有 10 个人，B 组有 10 件物品。你的理论说需要 19 个连接。但事实上，如果没有解决方案，您可以拥有更多。
例如，将集合分成 7 人组和 3 人组。然后将 7 人组中的每个人连接到 7 项组中的每个项目。那是 49 个连接。
并且如题所示，两组3仍然可以连接。因此，如果有 10 个人和 10 个项目，您可能有 53 个连接而没有解决方案。
感谢评论中的@PaulHankin for pointing out Hall's marriage theorem。
我将在这里解释一下定理。证明在链接的文章中。
Given two sets A and B of equal size, a saturating matching is a
matching that covers every element of both sets.
For a subset {b} of B, let {a} denote the subset of A that has
connections to {b}. The marriage theorem states that A and B have
a saturating matching if and only if for every subset b of B:
|b| <= |a|
In other words: every subset of B has sufficiently many connections
to A.
让我们将其应用于问题中的图表。
我们看到B中的子集b={b1, b3}连接到A中的子集a={a2}。我们注意到|b|==2和|a|==1，所以条件|b| <= |一个|不满足，图没有饱和匹配。
要使用霍尔婚姻定理作为算法的基础来验证饱和匹配的存在性，我们需要检查 B 的每个子集。有多少个子集？ B 的所有子集的集合称为 B 的 powerset。幂集包含 B 的 2^n 个子集（其中 n 是 B 中的元素数）。因此，直接使用该定理会导致 O(2^n) 算法。
解决 maximal matching problem or the balanced assignment problem 的算法可用于更有效地解决此问题。
我会通过以下方式解决这个问题：
A中的人按边数排序（从低到高）
如果A里的人在B里只有一个偏好的item，分配给它。
当A中的一个人在B中有一个以上的偏好项时，选择A中偏好人数最少的项。
我会用回溯来做到这一点。
给你两组节点，每组节点数相同。集合 A 包含人员列表。集合 B 包含一个项目列表。每个人对集合 B 中任意数量的项目都有偏好。如果我们将这些偏好表示为人员节点和项目节点之间的连接，则每个节点必须至少有一个连接。
起初我以为每个人总能得到他们想要的东西，但事实并非总是如此，例如可能会发生这样的事情：
我的一个想法是，只要图中有（set A size + set B size-1）个或更多连接，就总是可以形成有效连接。但是，我无法证明这一点的正确性。 你知道这是否正确吗？或者是否有完全不同的解决方案？
恐怕你的理论不正确。假设 A 组有 10 个人，B 组有 10 件物品。你的理论说需要 19 个连接。但事实上，如果没有解决方案，您可以拥有更多。
例如，将集合分成 7 人组和 3 人组。然后将 7 人组中的每个人连接到 7 项组中的每个项目。那是 49 个连接。
并且如题所示，两组3仍然可以连接。因此，如果有 10 个人和 10 个项目，您可能有 53 个连接而没有解决方案。
感谢评论中的@PaulHankin for pointing out Hall's marriage theorem。
我将在这里解释一下定理。证明在链接的文章中。
Given two sets A and B of equal size, a saturating matching is a matching that covers every element of both sets.
For a subset {b} of B, let {a} denote the subset of A that has connections to {b}. The marriage theorem states that A and B have a saturating matching if and only if for every subset b of B:
|b| <= |a|
In other words: every subset of B has sufficiently many connections to A.
让我们将其应用于问题中的图表。
我们看到B中的子集b={b1, b3}连接到A中的子集a={a2}。我们注意到|b|==2和|a|==1，所以条件|b| <= |一个|不满足，图没有饱和匹配。
要使用霍尔婚姻定理作为算法的基础来验证饱和匹配的存在性，我们需要检查 B 的每个子集。有多少个子集？ B 的所有子集的集合称为 B 的 powerset。幂集包含 B 的 2^n 个子集（其中 n 是 B 中的元素数）。因此，直接使用该定理会导致 O(2^n) 算法。
解决 maximal matching problem or the balanced assignment problem 的算法可用于更有效地解决此问题。
我会通过以下方式解决这个问题：
A中的人按边数排序（从低到高）
如果A里的人在B里只有一个偏好的item，分配给它。
当A中的一个人在B中有一个以上的偏好项时，选择A中偏好人数最少的项。
我会用回溯来做到这一点。