问题标签 [np-complete]

我自愿编写一个程序来安排家​​长会。校长希望家长选择 3 个可能的日期时间来拜访他们的英语和数学老师（同时）。

一旦所有的家长都选择了 3 个约会时间，我应该找出安排家长会的最佳方式，以便尽可能多的家长与两位老师见面。

（如果有时间冲突，数学老师不能到会，家长只能和英语老师见面）

我对 NP 类型的问题了解不多，但是当我听到“最优”和“调度”这两个词时，我开始怀疑……

我已经告诉校长我不能这样做，但我想知道它是否是 NP 完全的。如果是，假设有：

• 500名家长
• 15名英语教师
• 5位数学老师
• 25 个日期时间可供选择

在你奶奶的电脑上，这可以在几秒钟、几分钟或几小时内正确解决吗？

（我已经更改了这个问题的细节以避免 NDA 问题。我知道，如果从字面上看，有更好的方法来经营这家理论上的公司。）

有一组仓库，每个仓库能够存储和分发 200 种不同的产品，而 A 公司生产的产品可能有 1000 种。每个仓库都备有 200 种产品，并分配了订单，然后他们将从手头的库存中填写这些订单。

挑战在于每个仓库都需要自给自足。将有一个任意数量的产品（通常为 5-10 个）的订单，该订单被分配到一个仓库。然后，仓库为订单打包所需的产品，并将它们一起运送。对于仓库中没有的任何物品，必须先将物品单独交付到仓库，然后才能发货。

因此，问题在于确定最佳的仓库/产品配置，以便可以打包尽可能多的订单，而无需订购和等待单个物品。

例如（使用每个由一个字母表示的产品，以及能够储存 5 个产品线的仓库）：

目标是使用历史数据来尽量减少未来单独订购的产品数量。一旦以某种方式建立了仓库，软件就会确定哪个仓库可以以最小的开销处理订单。

这立即让我觉得这是一个机器学习风格的问题。它也似乎是某些众所周知的 NP 完全问题的组合，尽管它们似乎都不合适。

是否有代表此类问题的模型？

我编写了这个程序来测试“解决”集合覆盖问题需要多长时间。

这只是一个贪婪的次优解决方案，但仍然需要 147 秒才能运行。然而，我认为这个解决方案应该非常接近最优，所以它应该足以满足我的目的。我怎样才能加快速度呢？

我注释掉了几行，因为它们弊大于利。编辑：计算宇宙实际上不应该是时间的一部分……这可以事先知道。

我正在研究一个我怀疑是 NP-hard 的组合优化问题，并且遗传算法在我们的数据集上运行良好。我们是一个研究小组，并计划在我们的领域（而不是数学或 CS）发表我们的结果，我想在将手稿送审之前探索 NP 难题。

有两个主要问题：

1）我想知道是否研究过这个特定的优化问题。我已经仔细搜索了点燃，但没有看到任何完全相同的东西。

2）如果这个问题还没有被研究过，我可能会尝试做一个可还原性证明，并且想要一些关于还原的良好 NP-完全候选者的指针。

这个问题可以用两种方式来描述，一个子序列变体，一个二分图问题。

在子序列风格中，我想找到一个允许排列的“宽松”子序列，并优化以最小化排列计数。例如： (. = 任何其他字符)

查询：abc，目标：..babc，结果：abc（正常子序列）

查询：abc，目标：..baca，结果：bac（一个排列的子序列）

二分公式是一个匹配问题或线性分配问题，将图划分为查询字符节点和目标字符节点。边将查询字符连接到目标字符，使得从每个查询字符到目标字符只有一条边。目标函数是最小化边缘交叉的数量（在 lit 中也称为“交叉数”）。这类似于重新排序节点放置以最小化边缘交叉的二分图布局算法，但我的问题要求两个节点顺序保持固定。

专家对问题 1 或 2 有何想法？

提前致谢！

如果已知问题 X（决策问题）是 NP-Complete，并且证明可以在多项式时间内简化为问题 Y，那么您能说问题 Y 是 NP-Complete 吗？

我的第一个想法是，不，问题 Y 需要证明它在 NP 中。但是经过进一步思考，如果将 X 简化为 Y，则 Y 已经被认为是 NP-Complete。现在我很困惑......任何帮助将不胜感激。

我知道我的问题可能没有“完美”的解决方案（这听起来像是背包或垃圾箱包装问题的变体），但这是我的场景：

我想将一个 SQL 数据库表列表划分为 n 个（比如说 7 个）大致相同大小的堆（这样我就可以将一些维护任务大致平均分布在整个一周内）。

假设我有 100 张桌子（可能更高或更低，但不可能高于 5000），大小从 1 到 10,000,000 不等（当然，更大的桌子不太常见）。

我最初的想法是按字母顺序（伪随机）对表格进行排序，然后从头开始，当总数超过 Sum(Size)/7 时移动到下一组。对于某些数据库，这可能会正常工作，但如果两个巨大的表彼此相邻，那么这会导致非常不平等的组。（这并不像听起来那么不可能，考虑两个巨大的表，Account_History 和 Account_History_Archive）。

是否有任何普遍接受的技术，可以为各种源数据提供“良好”的结果？我倾向于一种更简单的技术，而不是更精确的分组（如果某些日子的维护时间比其他日子稍长，那没什么大不了的）。

“证明确定给定输入 G 和 k 是 NP 完全的G 拥有这两个子集。”

我们在我的算法课程中遇到了这个问题，一大群学生无法弄清楚。这是我们到目前为止所拥有的...

我们知道集团和独立集问题本身都是 NP-Complete 的。我们也知道这个问题的验证，给定一些“证书”在 NP 中。

问题是以某种方式将上述问题（包含独立集和派系）简化为完全由派系或独立集组成的问题（至少这是我们认为需要做的）。我们不知道如何在不丢失将还原还原到其原始形式所需的信息的情况下执行此还原。

我有一个问题，我被困住了，找不到任何开始的地方，所以我绝望地转向stackoverflow。

问题要我们找出它是 np-hard 还是多项式，如果它的 np-hard 证明 np-completeness，否则给出算法。

问题如下：

存在 n 个模块的乘积。有两家公司可以构建每个模块，但需要一些成本（c_ij，i：模块编号，j：公司编号）。如果模块 a 和 b 是由不同的公司构建的，它们也会产生额外的成本 (p_ab)。模块 a 和 b 不必连续，同样的额外费用也适用于 a 和 c。正如预期的那样，问题要我们找到将模块分配给公司的方法，以使总成本最小。

有任何想法吗 ？

假设我有一个大的（几千个节点）有向图G和一个小得多的（3-5 个节点）有向图g。我想计算在G中有多少g的同构。换句话说，我想知道 G 中有多少独特的节点集与g匹配。我意识到这是子图同构问题的一个实例，因此是 NP 完全的。但是，鉴于您可能假设g很小，是否有任何合理有效的算法可以做到这一点？

首先，我要说我对理论之类的东西知之甚少。但我想知道这是一个 NP 还是 NP 完全问题。这听起来像是子集和问题的一个特例。

无论如何，我最近一直在玩这款名为 Alchemy 的游戏，它引发了这个想法。基本上，您从 4 个基本元素开始，然后将它们组合成其他元素。

因此，例如，如果您愿意制作元素，这是一个简短的“食谱”

因此，假设一台计算机只能创建 4 个基本元素，但它可以创建多组元素。因此，您编写一个程序来通过组合其他元素来制作任何元素。该程序将如何处理创建灯泡的列表？

很明显，火+空气=能量，土+土=沙，沙+火=玻璃，能量+玻璃=灯泡。

但是我想不出任何方法来编写程序来处理列表并在不使用蛮力类型方法并检查每个元素并检查其配方的情况下弄清楚这一点。

这是一个NP问题吗？或者我只是无法弄清楚这一点？