最优选择选举算法

Question

给定一组人(类似于)：

[p1,p2,p3]
[p2,p3]
[p1]
[p1]

从每个集合中选择1，尝试最小化选择任何一个人的最大次数。

对于上述集合，必须选择给定人员的最大次数为2。

我正在努力寻找解决这个问题的算法。我不认为这可以用贪婪的算法来完成，更多地沿着动态编程解决方案的思路思考。

有什么关于如何做的提示吗？或者你们中有谁知道关于这些东西的好网站，我可以看看吗？

Answer 1

这既不是动态的也不是贪婪的。让我们先看一个不同的问题--可以通过选择每个人至多一次来实现吗？

你有P个人和S个集合。创建一个包含S+P顶点的图，表示集合和人物。当pi是si的一个元素时，人pi和集合si之间有一条边。这是一个bipartite graph，您的问题的决策版本相当于测试该图中的maximum cardinality matching是否具有大小S。

正如该页面上详细介绍的那样，这个问题可以通过使用maximum flow算法来解决(注意:如果你不知道我在说什么，那么现在花点时间去阅读它，否则你就不会理解其余的内容)：首先创建一个超级源，添加一个边将其链接到容量为1的所有人(表示每个人只能使用一次)，然后创建一个超级源，并添加将每个集合链接到容量为1的接收器的边(表示每个集只能使用一次)，然后在源和汇点之间运行合适的最大流量算法。

现在，让我们考虑一个稍微不同的问题:可以通过选择每个人至多k次来实现吗？

如果你注意到最后一段中的备注，你应该知道答案:只需改变离开超源的边的容量，以表明在这种情况下每个人可能会被使用不止一次。

因此，您现在有了一个算法来解决决策问题，在这个问题中，人们被选择至多k次。很容易看出，如果你可以用k来做，那么你也可以用任何大于k的值来做，也就是说，它是一个单调函数。因此，您可以对问题的决策版本运行二进制搜索，寻找仍然有效的最小k。

注意:您还可以通过按顺序测试k的每个值来摆脱二进制搜索，并增加在最后一次运行中获得的残差网络，而不是从头开始。然而，我决定解释二分搜索版本，因为它在概念上更简单。