可能是 NP 完全问题吗？

Question

我只是希望有人验证以下问题是否是 NP 完全的，或者是否确实有比简单的强力组合检查更好/更简单的解决方案。

我们的软件中存在某种资源分配问题，我将用一个例子来解释它。

假设我们需要 4 个人在白班工作。这个数字以及它是“白班”的事实都记录在我们的数据库中。

然而，我们并不要求任何人都能填补这些空缺，还需要满足一些要求才能满足要求。

在这 4 人中，假设其中 2 人必须是护士，其中 1 人必须是医生。

其中一名医生还必须作为特定团队的一员工作。

所以我们有这组信息：

白班：4
1名医生
1名医生，需要在A组工作
1名护士

以上都不是问题。当我们开始挑选上白班的人，并试图弄清楚我们迄今为止挑选的人是否真正符合标准时，问题就出现了。

例如，假设我们选择詹姆斯、约翰、乌苏拉和玛丽来工作，其中詹姆斯和乌苏拉是医生，约翰和玛丽是护士。

乌苏拉也在 A 队工作。

现在，根据我们尝试满足要求的顺序，我们最终可能会推断出我们是否拥有合适的人员，除非我们开始尝试不同的组合。

例如，如果沿着列表向下选择 Ursula，我们可以将她与“1 名医生”标准进行匹配。然后我们谈到 James，我们注意到，由于他不在 A 团队工作，因此“1 名医生，需要在 A 团队工作”的其他标准无法由他满足。由于另外两个人是护士，他们也不符合这个标准。

所以我们回溯并首先尝试詹姆斯，他也可以满足第一个标准，然后乌苏拉可以满足该团队需要的标准。

因此，问题对我们来说是因为我们需要尝试不同的组合，直到我们尝试了所有组合，在这种情况下，我们有一些尚未满足的标准，即使工作的头总数与总数相同所需的头数，或者我们已经找到了有效的组合。

这是唯一的解决方案吗，有人能想到更好的解决方案吗？

---

编辑:一些澄清。

对这个问题的评论提到，对于这几个人，我们应该使用蛮力，我同意，这可能是我们可以做的，我们甚至可能这样做，在某些排序优化着眼于大小的同一条车道上如果数据量较小，则选择初始开销较小的不同排序算法。

但问题是，这是花名册规划系统的一部分，其中可能涉及相当多的人，既“我们需要 X 个人上白班”，也包括“我们有 Y 个人”将会做到这一点”，以及一个大的潜力“我们有这些 X 人的 Z 标准列表，这些 X 人必须以某种方式与这些 Y 人相匹配”，然后你添加一个事实，即我们将有当领导者调整名单时，需要几天时间实时进行相同的计算，然后就出现了对快速解决方案的需求。

基本上，领导者会在屏幕上看到实时汇总信息，显示整个白班仍有多少人失踪，以及有多少人符合各种标准，以及我们实际有多少人。除了我们拥有的之外，还有 ned 。当领导者用“如果詹姆斯上白班而不是乌苏拉，而乌苏拉上夜班怎么办”来调整名单时，该显示必须进行半实时更新。

但非常感谢到目前为止回答这个问题的人们，约束满足问题听起来像是我们需要走的路，但我们肯定会仔细查看这里的所有链接和算法名称。

这就是我喜欢 StackOverflow 的原因 :)

Answer 1

您有什么有一个约束满足问题;他们对NP的关系很有趣，因为他们是典型的NP但往往没有NP完全问题，即他们是听话的，以多项式时间的解决方案。

由于EBO在评论中指出，您的情况听起来可配制为精确覆盖问题，你可以申请 Knuth的算法X 来。如果采取这种粘性，请让我们知道它是如何工作适合你。

Answer 2

它看起来就像你有一个约束满足问题。

在你的情况我会特别看约束传播技术第一 - 你可以把问题缩小到可管理的大小的方式。

如果没有人符合标准，会发生什么？

Answer 3

您所描述的是“室友问题”，它在 这篇论文.

请耐心等待，我正在寻找更好的链接。

编辑

这是另一个相当密集的 论文.

Answer 4

至于我，我将最有可能试图找到还原二分图匹配问题。也证明，问题是NP通常比住你不能找到解决多项式复杂得多。

Answer 5

我不知道你的问题是NP，它不闻这种方式，但如果我是你将为了使这样的，你尝试填补，因为人少的最具体的第一位置的要求，我会做什么将可填补这些职位，所以你不太可能有走回头路了很多。没有理由为什么你不应该与算法X，纯克努特岬的算法结合这一点。

Answer 6

我要离开这个理论给别人，因为我的数学头脑不那么大，但你会发现像鹤鸵/ Cassowary.net或NSolver有用的工具以声明表示您的问题作为一个约束满足问题，然后解决约束

在这样的工具，单纯形法与约束传播组合经常采用确定性地降低溶液的空间，然后找到给出的成本函数的最优解。对于较大的溶液的空间（这似乎没有在指定的问题的大小适用），偶尔遗传算法被使用。

如果我没有记错，NSolver也在示例代码包括一个实际的护士排班问题春博士在香港制作的简化。还有的对他所做的工作的文件。

Answer 7

这听起来像你对我有一对夫妇的可分离的问题，这将是一个更容易解决：

- 选择从A队一个医生 - 从任何一支球队选择另一位医生 - 选择两个护士

所以，你有三个独立的问题。

虽然澄清，你必须有两名医生（一个从指定的团队）和两名护士，或一个医生从指定的球队，两名护士和一个其他可以是医生或护士？

Answer 8

一些问题：

1. 目标是满足约束 到底, 或者只 大约 (但尽可能地)?
2. 一个人可以成员的多个团队?
3. 什么都是可能的限制吗？(例如，我们需要一个医生这是一个部件的几个团队？)

如果你想要满足的限制 到底, 然后我会秩序的约束渐减通过严格，那就是，那些是最难以实现(例如医生团队在你上面的例子)应检查 第一!

如果你想要满足的限制 大约, 然后它的一个不同的故事...你就必须指定某种加权/重要功能，它确定什么我们不会，当我们不能完全匹配，并有几种可能性选择。

Answer 9

如果您有几个或很多限制，看看 Drools的规划师 （开源，JAVA）。

蛮力，分支定界和类似技术采取长。确定性算法如第一填充最大位移是非常不理想的。元启发式对付这是一个非常好的办法。

采取在Drools的规划师的真实世界的护士排班示例的特定的外观。这很容易增加了许多限制，如“年轻的护士不想上班星期六晚上”或“一些护士不愿工作多天连续”。