问题标签 [np-complete]

我想嵌入 3 个 NP-Complete 问题（其中 2 个已知是 NP-Complete，其中 1 个是我自己的想法）。我看到了“这个问题”，并在理论上重新解释了嵌入问题：

• 服务员就是小偷。
• 桌子是商店。
• 食物是具有不同重量的有价值的物品。
• 小偷在抢劫之前知道所有物品的价格和重量。
• 他的目标是最有效的抢劫（使用的背包的最大容量，获得最有价值的物品）抢劫（至少获得 1 件物品）所有商店（完成抢劫之旅的最短路径，也访问每个商店 1 次）。

这部分是嵌入 2 个 NP-Complete 问题。

我的想法是，更多的物品意味着更多的袋子重量。更大的袋子重量会成倍地减慢小偷的速度。所以小偷的另一个目标应该是尽快完成抢劫。

此时，我不确定我的想法是否真的是 NP-Complete。也许，“重力”不仅仅是一个 NP 完全问题。但也许是在旅行推销员和背包问题的背景下。

所以我的问题是：

1. 小偷NP的减速也完全吗？

2. 是否有可能将这三个嵌入式问题简化为一个简单的 NP 完全问题？

我知道布尔可满足性是 NP-Complete 的，但它是布尔表达式的最小化/简化，我的意思是采用符号形式的给定表达式并以符号形式产生等效但简化的表达式，NP-Complete？我不确定从可满足性到最小化是否有减少，但我觉得可能有。有人有确切消息么？

在我看来，NP-completeness 似乎是那些大多只是理论上的东西，而不是你在正常工作环境中遇到的东西。

所以我有点好奇，是否有人在他们的工作中遇到了一个结果证明是 NP 完全的问题，并且需要更改设计以适应它？

有一个数字列表。
该列表将被分成 2 个大小相等的列表，总和的差异最小。必须打印总和。

在某些情况下，以下代码算法是否有错误？

我如何优化和/或 pythonize 这个？

问题来自http://www.codechef.com/problems/TEAMSEL/

我只是希望有人验证以下问题是否是 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 的原因 :)

这个问题纯粹是出于好奇。我暑假放学了，我打算实现一个算法来解决这个问题，只是为了好玩。这就引出了上面的问题，这个问题有多难？

问题：给你一个正整数列表、一组数学运算符和等号（=）。您可以使用整数（以相同顺序）和运算符（任意次数）创建有效的数学表达式吗？

一个例子应该可以澄清任何问题：

给定： {2, 3, 5, 25} , {+, -, *, /} , {=}
输出：YES

表达式（我认为只有一个）是（2 + 3）* 5 = 25。您只需要输出 YES/NO。

我相信问题出在NP上。我这样说是因为它是一个决策问题（是/否答案），我可以找到一个非确定性的多时间算法来决定它。

一种。不确定地选择一系列运算符放在整数之间。
湾。验证您的回答是一个有效的数学表达式（这可以在恒定时间内完成）。

在这种情况下，最大的问题是：问题在 P 中吗？（即是否有确定性的多时间算法来决定它？）或者问题 NP 是否完整？（即，一个已知的 NP Complete 问题可以简化为这个问题吗？或者等效地，每个 NP 语言的多时间都可以简化为这个问题吗？）或者两者都不是？（即 NP 中的问题但不是 NP Complete）

注意：这个问题陈述假设 P 不等于 NP。另外，虽然我是 Stack Overflow 的新手，但我对 homework 标签很熟悉。这确实只是好奇，而不是作业:)

或者更确切地说，组合算法和线性算法的定义分别是什么？

说清楚是因为显然第一响应者误解了这个问题：我不是在寻找线性时间与非线性时间运行的算法的定义。线性算法在某种程度上与线性规划有关，线性规划是一种用于寻找或逼近线性优化问题的解决方案的技术。

由于 NP-hard 问题非常困难，因此整个领域都在试图找到近似解。例如，旅行商问题有几个近似解，它们在多项式时间内运行，并产生一个在最佳解的给定范围内的解。

这些近似算法中的一些称为线性算法，另一些称为组合算法；后者似乎是首选（为什么？）。这是我想了解的两个概念。

我正在使用模拟退火来解决 NP 完全资源调度问题。对于任务的每个候选排序，我计算了几个不同的成本（或能量值）。一些例子是（尽管细节可能与问题无关）：

• global_finish_time：计划跨越的总天数。
• split_cost：每个任务由于其他任务的中断而延迟的天数（这是为了阻止任务一旦开始就被中断）。
• deadline_cost：每个错过的最后期限逾期的天数的平方和。

传统的接受概率函数如下所示（在 Python 中）：

到目前为止，我通过简单地将前两个成本合并为一个，这样我就可以将结果输入acceptance_probability. 但我真正想要的是deadline_cost永远优先global_finish_time，并且global_finish_time优先split_cost。

所以我对 Stack Overflow 的问题是：我如何设计一个接受概率函数，它考虑了多种能量，但始终认为第一种能量比第二种能量更重要，等等？换句话说，我想传入old_cost和new_cost作为几个成本的元组并返回一个合理的值。

编辑：在对提议的解决方案进行了几天的试验后，我得出结论，唯一对我来说足够好的方法是 Mike Dunlavey 的建议，尽管这会给具有不同单位的成本组件带来许多其他困难。我几乎被迫将苹果与橙子进行比较。

因此，我付出了一些努力来“规范化”这些值。首先，deadline_cost是平方和，因此它呈指数增长，而其他分量呈线性增长。为了解决这个问题，我使用平方根来获得类似的增长率。其次，我开发了一个计算成本线性组合的函数，但会根据目前看到的最高成本成分自动调整系数。

例如，如果最高成本的元组是 (A, B, C)，输入成本向量是 (x, y, z)，则线性组合是 BCx + Cy + z。这样，无论 z 值有多高，它都不会比 x 值 1 更重要。

当发现新的最大成本时，这会在成本函数中产生“锯齿”。例如，如果 C 上升，那么对于给定的 (x, y, z) 输入，BCx 和 Cy 都会更高，成本之间的差异也会如此。更高的成本差异意味着接受概率会下降，就好像温度突然降低了额外的步骤一样。但实际上这不是问题，因为最大成本在开始时仅更新几次，以后不会更改。我相信这甚至可以在理论上被证明会收敛到一个正确的结果，因为我们知道成本会收敛到一个较低的值。

仍然让我有些困惑的一件事是，当最大成本为 1.0 或更低（例如 0.5）时会发生什么。对于 (0.5, 0.5, 0.5) 的最大向量，这将给出线性组合 0.5*0.5*x + 0.5*y + z，即优先顺序突然颠倒。我想处理它的最佳方法是使用最大向量将所有值缩放到给定范围，以便系数始终相同（例如，100x + 10y + z）。但我还没有尝试过。

这是我似乎在使用会计系统时遇到的一个问题。

我有一组交易，但它们的总和不等于会计部门认为应该的金额。他们不是在质疑数学，只是在质疑交易：p

是否有一种算法可以帮助我确定不应该包含集合中的哪些交易以使总和与给定金额匹配。

编辑： 集合中的事务少于 100 个。有没有人有一个 C# 示例，因为在 XKCD 问题中解决 NP 完全问题没有一个？

伙计，我应该获得CS学位。

我正在尝试找出一种算法，该算法将帮助我将各种大小的文件分组为大小大致相等的“n”组。

关于如何实现这一目标的任何想法？