logo标签列表

可能的NP完全问题？

algorithmallocationnp-completeconstraint-satisfaction
8
我只想请有人验证以下问题是否为NP完全问题，或者是否存在比简单的蛮力组合检查更好/更容易的解决方案。
我们在软件中遇到了一种类似资源分配问题，我将通过一个例子来解释它。
假设我们需要4个人在白天工作。这个数字以及它是“白班”记录在我们的数据库中。
然而，我们不仅需要任何人来填补这些职位，还有一些需求必须满足才能符合要求。
其中2个人必须是护士，1个人必须是医生。
其中一名医生还必须作为特定团队的一部分工作。
因此，我们有了这些信息：
白班: 4    1名医生    1名医生，需要在A团队工作    1名护士
上面的内容不是问题所在。问题出现在我们开始挑选人员来工作白天，并尝试确定我们已经选择的人员是否真正符合标准时。
例如，假设我们选择James、John、Ursula和Mary来工作，其中James和Ursula是医生，John和Mary是护士。
Ursula还在A团队工作。
现在，根据我们尝试适应法案的顺序，我们可能会得出我们有合适的人员的结论，或者不会，除非我们开始尝试不同的组合。
例如，如果我们按照列表顺序选择Ursula，我们可以与“1名医生”标准匹配。然后我们到达James，并注意到由于他不在A团队工作，关于“1名医生，需要在A团队工作”的其他标准不能用他来满足。由于另外两个人是护士，他们也不符合该标准。
因此，我们回溯并首先尝试James，他也可以符合第一个标准，然后Ursula可以符合需要该团队的标准。
因此，问题对我们来说看起来就像我们需要尝试不同的组合，直到我们已经尝试了所有组合，在这种情况下，即使工作人数与所需总人数相同，我们仍有一些标准未被满足，或者我们已经找到了一个有效的组合。
这是唯一的解决方案吗？有人能想到更好的方法吗？
问题在于这是排班系统的一部分，可能会涉及到很多人，既有“我们需要X个人在白天上班”，也有“我们有这个Y人的人员池”，还有一个大的“我们有这个Z标准列表，这些X人必须与这些Y人匹配”，然后你要为同样的计算做出贡献，因为领导正在调整排班，并且需要实时进行，在此基础上需要快速解决方案。
基本上，领导将在屏幕上看到实时的汇总信息，显示还缺少多少人，无论是整个白天班还是符合各种标准的人数，以及我们实际上需要增加多少人。这个显示屏将在领导调整排班时半实时更新，“如果詹姆斯代替乌苏拉上白班，乌苏拉代替夜班”等。
非常感谢到目前为止回答过这个问题的人们，约束满足问题听起来像我们需要走的路，但我们肯定会认真查看这里所有链接和算法名称。
这就是为什么我喜欢StackOverflow :)
有了像4和2这样的数字，我不明白为什么不使用最简单的暴力搜索。 - ShreevatsaR
我同意如果数据规模始终很小，你应该直接使用暴力算法。如果不是，你需要使用一种启发式算法。我猜这可能是背包问题的变体。我不知道为什么那个回答被从这个问题中删除了。 - Matt Spradley
我同意，我会编辑这个问题，但我认为已经给出的答案将为我们提供一些开始的方式。 - Lasse V. Karlsen
9个回答
11

你所面临的是一个约束满足问题；它们与NP的关系很有趣，因为它们通常是NP问题，但经常不是NP完全问题，也就是说，它们可以通过多项式时间算法求解。

正如ebo在评论中指出的那样，你的情况听起来可以被形式化为一个精确覆盖问题，你可以应用Knuth的X算法来解决。如果你采取这个方法，请告诉我们它对你的作用如何。

4
如果你将问题重写为精确覆盖问题，你可以使用Knuth的X算法（或跳跃链接）来解决它。这比单纯的回溯方法快得多，网上有很多例子。 - ebo
@ebo：听起来比我想到的任何东西都更有成效。我会把它融入我的答案中。谢谢。 - chaos
我不认为这是答案 - 我在他的问题定义中没有看到任何内容表明这些标准是确切的。 - Loren Pechtel
我们一定会查看所有这些解决方案。由于有多个人提到了“约束满足问题”，并且这是得票最高的答案，我会接受这个答案，但我们一定会仔细研究其他答案。 - Lasse V. Karlsen
@Loren Pechtel： "exact"与约束无关。重要的是，需要满足所有约束条件。请阅读维基百科页面。 - ebo
3

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

在你的情况下，我会首先特别关注约束传播技术--这样你可能能够通过这种方式将问题减少到可管理的大小。

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

谢谢，这绝对是我们需要的！ - Lasse V. Karlsen
1
如果您有多个或许多的约束条件，可以看看Drools Planner（开源，Java）。
暴力搜索、分支定界等技术需要太长时间。确定性算法如“先填最大班次”非常次优。元启发式算法是处理这种问题的一种很好的方法。
特别关注Drools Planner的实际护士排班示例。很容易添加许多约束条件，例如“年轻的护士不想在周六晚上工作”或“一些护士不想连续工作太多天”。
1

你所描述的是“室友问题”，它在这篇论文中有轻微的描述。

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

编辑

这里还有一篇相当深入的论文。

1

对我来说，我最有可能尝试寻找二分图匹配问题的解决方案。而且证明该问题是NP难通常比说你无法找到多项式解决方案更加复杂。

这种类型的图表超出了我的知识水平，但我会去查阅相关资料！谢谢！ - Lasse V. Karlsen
1

我不确定你的问题是否属于NP问题，它并没有那种味道，但如果我是你，我会按职位需求的顺序来尝试填补最具体的职位，因为能够填补这些职位的人较少，所以你不太可能需要大量回溯。你完全可以将这个方法与X算法相结合，这是一个纯Knuth算法。

我同意，这也是我们最初设想的，但问题在于“A团队协会”的要求只是其中三个要求之一，可能会同时发生或不发生，即“A团队，并且熟练使用灭火器，以及是一名护士”，而这3种类型可以单独出现，也可以同时出现，这意味着在某些情况下，没有办法将一个要求权重比另一个更具体。 - Lasse V. Karlsen
1

我会把理论留给其他人，因为我的数学知识不是很好，但你可能会发现像Cassowary/Cassowary.net或NSolver这样的工具有用，可以将你的问题声明性地表示为约束满足问题，然后解决这些约束。

在这样的工具中，单纯形法结合约束传播经常被用来确定性地减少解空间，然后在给定成本函数的情况下找到最优解。对于更大的解空间（似乎不适用于您指定的问题规模），偶尔会使用遗传算法。

如果我没记错的话，NSolver还包括一个简化版的护士排班问题的示例代码，这是Chun博士在香港研究的实际问题。还有一篇他所做的工作的论文。

哦，不错，还有工具和软件！谢谢！ - Lasse V. Karlsen
1

听起来你有几个可以分开解决的问题：

-- 从A团队中选择一名医生 -- 从任意团队中选择另一名医生 -- 选择两名护士

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

不过需要澄清的是，你需要一名来自指定团队的医生和两名护士，还是一名来自指定团队的医生、两名护士和另外一名可以是医生也可以是护士的人？

后者实际上可以是任何类型的员工，否则就会有要求。但这并不是非常开放，因为试图将人员映射到班次的人拥有一个固定的员工池，这意味着通常会有一种相当同质化的员工类型（即大多数医生、护士、医务人员等）。你通常不会在同一个池中找到园丁、清洁工、医务人员和道路工人。 - Lasse V. Karlsen
1

一些问题：

  1. 目标是完全满足约束条件，还是尽可能地满足（但不完全）？
  2. 一个人可以是几个团队的成员吗？
  3. 所有可能的约束条件是什么？（例如，我们需要一个同时是几个团队成员的医生吗？）

如果您想要完全满足约束条件，那么我建议按照严格程度递减的顺序对约束条件进行排序，即最难实现的条件（例如，在上面的例子中，医生和A团队）应该首先检查！

如果您想要近似满足约束条件，那么情况就不同了……您需要指定某种加权/重要性函数，以确定当无法完全匹配并有多种选择时，我们更希望得到什么。

1
一个人只能参加一个团队，并且在这个背景下在公司里只有一个职位，但是最后一个标准，它存储关于这个人获得认证的信息（即参加并通过了灭火班，或使用心肺复苏急救技能等），这个人可以有多个认证。该系统的目的是尝试填写一个值班表，上面写着“我们需要至少2名医生在白班，而其中至少一人需要具备使用X-ray机器的认证”等要求。 - Lasse V. Karlsen
抱歉重复一遍，但当没有办法满足约束条件时，我们必须找到一些妥协的情况是否有兴趣？这种情况经常发生吗？（我对医院不是很了解...） :-) - jacob
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接