可能是 NP 完全问题吗？
我只是希望有人验证以下问题是否是 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 的原因 :)
I'd just like someone to verify whether the following problem is NP-complete or if there is actually a better/easier solution to it than simple brute-force combination checking.
We have a sort-of resource allocation problem in our software, and I'll explain it with an example.
Let's say we need 4 people to be at work during the day-shift. This number, and the fact that it is a "day-shift" is recorded in our database.
However, we don't require just anyone to fill those spots, there's some requirements that needs to be filled in order to fit the bill.
Of those 4, let's say 2 of them has to be a nurse, and 1 of them has to be doctors.
One of the doctors also has to work as part of a particular team.
So we have this set of information:
Day-shift: 4
1 doctor
1 doctor, need to work in team A
1 nurse
The above is not the problem. The problem comes when we start picking people to work the day-shift and trying to figure out if the people we've picked so far can actually fill the criteria.
For instance, let's say we pick James, John, Ursula and Mary to work, where James and Ursula are doctors, John and Mary are nurses.
Ursula also works in team A.
Now, depending on the order we try to fit the bill, we might end up deducing that we have the right people, or not, unless we start trying different combinations.
For instance, if go down the list and pick Ursula first, we could match her with the "1 doctor" criteria. Then we get to James, and we notice that since he doesn't work in team A, the other criteria about "1 doctor, need to work in team A", can't be filled with him. Since the other two people are nurses, they won't fit that criteria either.
So we backtrack and try James first, and he too can fit the first criteria, and then Ursula can fit the criteria that needs that team.
So the problem looks to us as we need to try different combinations until we've either tried them all, in which case we have some criteria that aren't filled yet, even if the total number of heads working is the same as the total number of heads needed, or we've found a combination that works.
Is this the only solution, can anyone think of a better one?
Edit: Some clarification.
Comments to this question mentions that with this few people, we should go with brute-force, and I agree, that's probably what we could do, and we might even do that, in the same lane that some sort optimizations look at the size of the data and picks different sort algorithms with less initial overhead if the data size is small.
The problem though is that this is part of a roster planning system, in which you might have quite a few number of people involved, both as "We need X people on the day shift" as well as "We have this pool of Y people that will be doing it", as well as potential for a large "We have this list of Z criteria for those X people that will have to somehow match up with these Y people", and then you add to the fact that we will have a number of days to do the same calculation for, in real-time, as the leader adjusts the roster, and then the need for a speedy solution has come up.
Basically, the leader will see a live sum information on-screen that says how many people are still missing, both on the day-shift as a whole, as well as how many people is fitting the various criteria, and how many people we actually ned in addition to the ones we have. This display will have to update semi-live while the leader adjusts the roster with "What if James takes the day-shift instead of Ursula, and Ursula takes the night-shift".
But huge thanks to the people that has answered this so far, the constraint satisfaction problem sounds like the way we need to go, but we'll definitely look hard at all the links and algorithm names here.
This is why I love StackOverflow :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
你所遇到的是约束满足问题； 它们与 NP 的关系很有趣，因为它们通常是 NP 但通常不是 NP 完全的，即它们易于处理多项式时间解决方案。
正如 ebo 在评论中指出的那样，您的情况听起来可以表述为 精确覆盖问题，您可以应用Knuth 算法 X。 如果您采取这种策略，请告诉我们它对您的效果如何。
What you have there is a constraint satisfaction problem; their relationship to NP is interesting, because they're typically NP but often not NP-complete, i.e. they're tractable to polynomial-time solutions.
As ebo noted in comments, your situation sounds like it can be formulated as an exact cover problem, which you can apply Knuth's Algorithm X to. If you take this tack, please let us know how it works out for you.
看起来您确实遇到了约束满足问题。
在你的情况下，我会首先特别关注约束传播技术——你也许能够通过这种方式将问题减少到可管理的规模。
如果没有人符合标准怎么办？
It does look like you have a constraint satisfaction problem.
In your case I would particularly look at constraint propagation techniques first -- you may be able to reduce the problem to a manageable size that way.
What happens if no one fits the criteria?
您所描述的是“室友问题”，它在本论文中进行了简单描述。
请耐心等待，我正在寻找更好的链接。
编辑
这是另一篇相当密集的论文 。
What you are describing is the 'Roommate Problem' it is lightly described in this thesis.
Bear with me, I'm searching for better links.
EDIT
Here's another fairly dense thesis.
对我来说，我很可能会尝试减少二分图匹配问题。 另外，要证明问题是 NP 通常比留下来无法找到多项式解要复杂得多。
As for me I would most likely trying to find reduction to bipartite graph matching problem. Also to prove that problem is NP usually is much more complicated than staying you cannot find polynomial solution.
我不确定你的问题是 NP，它闻起来不是那样的，但如果我是你，我会做的是订购职位的要求，这样你就会尝试先填补最具体的职位，因为可用的人会更少填补这些位置，这样你就不太可能需要大量回溯。 没有理由不将其与算法 X（一种纯 Knuth 性算法）结合起来。
I am not sure your problem is NP, it does not smell that way, but what I would do if I was you would be to order the requirements for the positions such that you try to fill the most specific first since fewer people will be available fill these positions, so you are less likely to have to backtrack a lot. There is no reason why you should not combine this with algorithm X, an algorithm of pure Knuth-ness.
我将把这个理论留给其他人，因为我的数学悟性不是很好，但您可能会发现像 Cassowary/Cassowary.net 或 NSolver 这样的工具可以将您的问题声明性地表示为约束满足问题，然后解决约束。
在此类工具中，经常采用单纯形法与约束传播相结合来确定性地减少解空间，然后在给定成本函数的情况下找到最优解。 对于较大的解决方案空间（这似乎不适用于您指定的问题的大小），有时会采用遗传算法。
如果我没记错的话，NSolver 还在示例代码中包含了 Chun 博士在香港研究的实际护士排班问题的简化。 还有一篇关于他所做工作的论文。
I'll leave the theory to others, since my mathematical savvy is not so great, but you may find a tool like Cassowary/Cassowary.net or NSolver useful to represent your problem declaratively as a constraint satisfaction problem and then solve the constraints.
In such tools, the simplex method combined with constraint propagation is frequently employed to deterministically reduce the solution space and then find an optimal solution given a cost function. For larger solution spaces (which don't seem to apply in the size of problem you specify), occasionally genetic algorithms are employed.
If I remember correctly, NSolver also includes in sample code a simplification of an actual Nurse-rostering problem that Dr. Chun worked on in Hong Kong. And there's a paper on the work he did.
在我看来，您有几个单独的问题，这些问题更容易解决：
--从 A 团队中选择一名医生
-- 从任意团队中选择另一名医生
-- 选择两名护士
所以你有三个独立的问题。
但需要澄清的是，是否必须有两名医生（一名来自指定团队）和两名护士，或者一名来自指定团队的医生、两名护士，以及另一名可以是医生或护士的人？
It sounds to me like you have a couple of separable problems that would be a lot easier to solve:
-- select one doctor from team A
-- select another doctor from any team
-- select two nurses
So you have three independent problems.
A clarification though, do you have to have two doctors (one from the specified team) and two nurses, or one doctor from the specified team, two nurses, and one other that can be either doctor or nurse?
一些问题：
如果您想完全满足约束，那么我会按严格程度递减排序约束，即最难实现的（例如上面示例中的医生和 A 团队）应该首先进行检查！
如果您想大约满足约束，那么这是一个不同的故事......您必须指定某种加权/重要性函数来确定我们宁愿拥有什么，当我们不能时完全匹配，并且有多种可能性可供选择。
Some Questions:
If you want to satisfy the constraints exactly, then I would order the constraints decreasingly by strictness, that is, the ones which are most hardest to achieve (e.g. doctor AND team A in your example above) should be checked first!
If you want to satisfy the constraints approximately, then its a different story... you would have to specify some kind of weighting/importance-function which determines what we rather would have, when we can't match exactly, and have several possibilities to choose from.
如果您有多个或多个限制，请查看 Drools Planner（开源、java）。
蛮力、分支定界和类似技术需要很长时间。 确定性算法（例如首先填充最大的偏移）是非常次优的。 元启发式方法是解决这个问题的一个很好的方法。
具体看一下 Drools Planner 的真实护士排班示例。 添加许多限制很容易，例如“年轻护士不想在周六晚上工作”或“一些护士不想连续工作很多天”。
If you have several or many constraints, take a look at Drools Planner (open source, java).
Brute force, branch and bound and similar techniques take to long. Deterministic algorithms such as fill the largest shifts first are very suboptimal. Meta-heuristics are a very good way to deal with this.
Take a specific look at the real-world nurse rostering example of Drools Planner. It's easy to add many constraints, such as "young nurses don't want to work the Saturday night" or "some nurses don't want to work to many days in a row".