ang*_*son 8 algorithm allocation np-complete constraint-satisfaction
我只是想让某人验证以下问题是NP完全还是实际上有一个比简单的强力组合检查更好/更容易的解决方案.
我们的软件中存在一种资源分配问题,我将用一个例子来解释它.
假设我们需要4个人在白班工作.这个数字以及它是"白班"的事实记录在我们的数据库中.
但是,我们并不需要任何人填写这些地点,需要填写一些要求才能满足要求.
在这4个中,让我们说其中2个必须是护士,其中1个必须是医生.
其中一名医生也必须作为特定团队的一员工作.
所以我们有这套信息:
白班:4名
1名医生
1名医生,需要在A组
1名护士工作
以上不是问题.当我们开始挑选人们白天工作并试图弄清楚到目前为止我们选择的人是否能够真正满足标准时,问题就出现了.
例如,假设我们选择James,John,Ursula和Mary来工作,其中James和Ursula是医生,John和Mary是护士.
厄秀拉也在A队工作.
现在,根据我们试图适应账单的顺序,我们最终可能会推断出我们是否拥有合适的人,除非我们开始尝试不同的组合.
例如,如果在列表中首先选择Ursula,我们可以将她与"1医生"标准相匹配.然后我们到了詹姆斯,我们注意到,由于他不在A队工作,所以关于"1位医生,需要在A队工作"的其他标准,不能用他来填补.由于其他两个人都是护士,他们也不符合这个标准.
因此,我们首先回溯并尝试詹姆斯,他也可以符合第一个标准,然后厄秀拉可以满足需要该团队的标准.
所以问题在我们看来,因为我们需要尝试不同的组合,直到我们要么全部尝试,在这种情况下我们有一些尚未填充的标准,即使工作头的总数与总数相同需要的头数,或者我们发现了一个有效的组合.
这是唯一的解决方案,任何人都可以想到更好的解决方案吗？
编辑:一些澄清.
对这个问题的评论提到,对于这几个人,我们应该蛮力,我同意,这可能是我们可以做的,我们甚至可以做到这一点,在某些优化看待大小的同一条道路上如果数据量很小,数据并选择不同的排序算法,初始开销较小.
但问题在于,这是一个名册规划系统的一部分,你可能会涉及很多人,"我们在白天需要X人"以及"我们有这个Y人群"这将是",以及一个大的潜力"我们有这个X人的Z标准列表,将不得不以某种方式与这些Y人匹配",然后你补充说我们将有在领导者调整名单的同时,实时进行相同计算的天数,然后需要快速解决方案.
基本上,领导者会在屏幕上看到一个实时信息,说明有多少人仍在失踪,无论是在整个日班,还是有多少人符合各种标准,以及我们实际有多少人除了我们拥有的那些之外.这个显示器必须更新半实时,而领导者调整名单时"如果詹姆斯采取白天而不是厄秀拉,而厄秀拉需要夜班".
但是非常感谢到目前为止已经回答过这个问题的人,约束满足问题听起来像我们需要的方式,但我们肯定会在这里仔细查看所有的链接和算法名称.
这就是为什么我喜欢StackOverflow :)
cha*_*aos 11
你有什么约束满足问题 ; 它们与NP的关系很有意思,因为它们通常是NP但通常不是NP完全的,即它们易于处理多项式时间解.
正如ebo在评论中指出的那样,你的情况听起来像是一个精确的封面问题,你可以将Knuth的算法X应用到.如果你采取这种方法,请告诉我们它是如何工作的.