算法 - 最大二分匹配的一个变种

Question

4

我正在处理一个最大二分匹配问题的变种。

原始问题如下：

有M个求职者和N个职位。每个求职者都有一组他/她感兴趣的职位子集。每个职位仅能接受一个求职者，而一个求职者只能被任命到一份工作上。找出一种分配方案，使得尽可能多的求职者得到工作。

新增的约束条件是：

每个求职者都属于某个组。现在，我们不再最大化求职者数量，而是要最大化快乐组的数量。快乐组是指所有成员都能获得工作的组。

欢迎任何想法/讨论！

- Mr Cold

这听起来类似于稳定婚姻问题。请查看该问题的描述：https://en.wikipedia.org/wiki/Stable_marriage_problem - Felipe Sulser

@FelipeSulser 不，不是那么简单。我猜需要一些修改过的福特-福尔克森算法。 - Kaidul

@FelipeSulser 我正在处理另一个更大的问题，最初想到使用稳定婚姻问题的思路，但由于很难将我的问题转化为该稳定婚姻问题，所以这种方法并没有奏效。然后我决定稍微改变一下我的问题，看起来更合理，结果它变成了一个约束匹配问题。 - Mr Cold

1

@KaidulIslam 我目前发现的是这个问题似乎是一个NP-Hard问题，但我既无法证明它，也没有找到一个好的估计解决方案。 - Mr Cold

@MrCold 我也认为这个问题是NP难的，但我还没有找到证明草稿；我对此不太确定。 - Codor

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

连接到永恒

如果您能够解决这个问题，您可以在永恒拼图上赢得一百万英镑。

在这个拼图中，您需要将209个多边形放置在一个板子上。

简化问题，每种拼图和位置的组合都有一个组。

每个组都有一个领导者，他只对与放置自己的拼图相对应的任务感兴趣。

每个组还有一个人负责瓷砖上的每个方格：该人只对填充游戏板上相应方格的任务感兴趣。

如果您可以找到209个快乐的组的解决方案，那么您已经找到了这个拼图的解决方案！

这是NP难问题，因为它可以用来解决最大独立集，这是一个已知的NP难问题。

假设我们有一个图，想要找到最大独立集。

为每个边创建一个任务。

为每个顶点创建一个组。

假设顶点x连接到三条边a、b、c。我们将向x组添加3个人。每个人只对一项任务感兴趣。第一个人对任务a感兴趣，第二个人对任务b感兴趣，第三个人对任务c感兴趣。

找到最大快乐群体就相当于找到最大的独立集。