8

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

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

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

但是，我们不要求任何人来填补这些空缺，为了满足要求，需要满足一些要求。

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

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

所以我们有这组信息：

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

以上不是问题。当我们开始挑选人员进行白班工作并试图弄清楚我们迄今为止挑选的人员是否真的能够满足标准时，问题就出现了。

例如，假设我们选择 James、John、Ursula 和 Mary 工作，其中 James 和 Ursula 是医生，John 和 Mary 是护士。

Ursula 也在 A 队工作。

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

例如，如果从列表中首先选择 Ursula，我们可以将她与“1 位医生”标准进行匹配。然后我们到了 James，我们注意到，由于他不在 A 队工作，所以关于“1 位医生，需要在 A 队工作”的其他条件，不能由他填写。由于另外两个人是护士，他们也不符合这个标准。

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

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

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

编辑：一些澄清。

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

但问题是，这是一个名册规划系统的一部分，其中可能有很多人参与其中，既是“我们需要 X 人上白班”，又是“我们有这个 Y 人池那将是这样做的”，以及一个大型“我们为那些必须以某种方式与这些 Y 人匹配的那些 X 人的 Z 标准列表”，然后你补充说我们将拥有当领导者调整花名册时，需要在几天内实时进行相同的计算，然后就需要快速解决方案。

基本上，领导者会在屏幕上看到一个实时总和信息，说明还有多少人仍然失踪，无论是在整个白班，还有多少人符合各种标准，以及我们实际上有多少人除了我们拥有的那些。当领导者用“如果詹姆斯上白班而不是乌苏拉，乌苏拉上夜班怎么办”来调整名单时，这个显示将不得不更新半直播。

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

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

4

9 回答 9

11

你有一个约束满足问题；它们与 NP 的关系很有趣，因为它们通常是 NP 但通常不是 NP 完全的，即它们易于处理多项式时间解决方案。

正如 ebo 在评论中指出的那样，您的情况听起来像是一个精确的覆盖问题，您可以应用Knuth 的算法X。如果您采用此策略，请告诉我们它对您的效果。

于 2009-06-05T16:10:47.720 回答
3

看起来您确实存在约束满足问题。

在您的情况下，我将首先特别关注约束传播技术——您可以通过这种方式将问题减少到可管理的规模。

如果没有人符合标准会怎样？

于 2009-06-05T16:16:04.913 回答
1

您所描述的是本文中简单描述的“室友问题”。

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

编辑

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

于 2009-06-05T16:10:09.203 回答
1

至于我，我很可能会尝试减少二分图匹配问题。还要证明问题是 NP 通常比留下你找不到多项式解决方案要复杂得多。

于 2009-06-05T16:18:27.443 回答
1

我不确定你的问题是 NP，它闻起来不是那样，但如果我是你，我会做的是订购职位的要求，以便你首先尝试填补最具体的职位，因为可用的人会更少填补这些职位，所以你不太可能不得不回溯很多。没有理由不将它与算法 X 结合起来，算法 X 是纯 Knuth-ness 的算法。

于 2009-06-05T18:33:53.140 回答
1

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

在这些工具中，单纯形法与约束传播相结合经常被用来确定性地减少解空间，然后在给定成本函数的情况下找到最优解。对于较大的解决方案空间（似乎不适用于您指定的问题大小），有时会使用遗传算法。

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

于 2009-06-05T18:44:54.897 回答
1

在我看来，您有几个可以更容易解决的可分离问题：

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

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

不过需要澄清一下，您是否必须有两名医生（一名来自指定团队）和两名护士，或者一名来自指定团队的医生、两名护士和一名可以是医生或护士的人？

于 2009-06-05T18:47:28.917 回答
1

一些问题：

  1. 目标是完全满足约束，还是仅近似满足（但尽可能）？
  2. 一个人可以成为多个团队的成员吗？
  3. 所有可能的约束是什么？（例如，我们是否需要一名来自多个团队的医生？）

如果你想完全满足约束，那么我会按严格程度递减约束，即最难实现的约束（例如上面示例中的医生和团队 A）应首先检查！

如果你想近似地满足约束，那么它就是一个不同的故事......你必须指定某种加权/重要性函数来确定我们宁愿拥有什么，当我们不能完全匹配时，并且有几种可能性从中选择。

于 2009-06-08T07:09:46.073 回答
1

如果您有几个或多个约束，请查看Drools Planner（开源，java）。

蛮力，分支和绑定和类似的技术需要很长时间。确定性算法（例如首先填充最大的移位）非常不理想。元启发式是处理这个问题的一个很好的方法。

具体看一下 Drools Planner 的真实护士排班示例。很容易添加许多约束条件，例如“年轻护士不想在周六晚上工作”或“一些护士不想连续工作很多天”。

于 2010-12-26T14:03:57.887 回答