问题标签 [np-hard]

我试图将二叉树拆分为 k 个类似大小的部分（通过删除 k-1 个边）。有没有解决这个问题的有效算法？或者它是NP难的？任何指向论文、问题定义等的指针？

-- 评估分区质量的一个合理指标可能是最大和最小分区之间的大小差距；另一个指标可能是使最小的分区具有尽可能多的顶点。

我正在处理一个看起来像分配问题的变体的问题。有些任务需要分配给服务器。服务器的成本总和需要最小化。以下条件成立：

1. 每个任务都有一个单位大小。

2. 一个任务不能在多个服务器之间分配。一项任务必须由一个服务器处理。

3. 服务器对可以分配给它的最大任务数有限制。

4. 任务分配的成本函数是一个阶梯函数。服务器产生最低成本“a”。对于服务器处理的每个任务，成本增加 1。如果分配给特定服务器的任务数量超过其容量的一半，则该服务器的成本会增加一个正数“d”。

   4. 任务具有偏好，即，可以将给定任务分配给几个服务器之一。

我有一种感觉，这是一个 NP-Hard 问题，但我似乎无法找到一个 NP-Complete 问题来映射到它。我试过装箱、分配问题、多个背包、二分图匹配，但这些问题都没有我的问题的所有关键特征。你能提出一些映射到它的问题吗？

谢谢和最好的问候

萨奇布

有 1 个候选人要接受 n 个面试官的面试，因此总共需要 n 个连续的位置，例如下表说明了四个面试官（I1、I2、I3、I4）在四次时间的可用性插槽（S1、S2、S3、S4）。表中的 1 表示对应的面试官在对应的时间段有空。

例如，第一个采访者 I1 在时间段 S1 和 S2 可用。

每位面试官只能接受一次面试，所有四个时段都应依次进行，如 S1->S2->S3->S4

在每个位置找到面试官的所有可能组合。图中就是这样一个例子，

算法

让我们拿三组（挖掘和算法是不同的）

我知道如果我将一个 NP 完全问题简化为一个未知问题P，那么我确定P本身就是 NP 完全问题。而且我知道如果我将问题P简化为 NP 完全问题，则没有结论。所以我想举一个例子来说明我们可以将一个多项式可解问题P简化为一个 NP 完全问题。

最小集覆盖是一个问题，您必须找到覆盖每个元素所需的最小集数。例如，假设我们有一个集合X=array(1,2,3,4,5,6)5 和另一个集合 S，其中

问题是要找到覆盖 X 的每个元素的 S 的最小集合数。显然，在我们的例子中，最小集合覆盖将是S[4]并且S[5]因为它们覆盖了所有元素。有谁知道如何在 C++ 中实现此代码。请注意，这是 NP 完全的，因此没有快速算法来解决它。任何 C++ 解决方案都将受到欢迎。顺便说一句，这不是家庭作业，我需要在Quine-McCluskey项目中使用这个算法来生成解决方案的最后一部分。
提前致谢。

this is my first question on this site.

I‌ recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me.

I) each NP problem can be solved in Exponential Time.

II) if P=NP then NP=NP-Complete.

III) Problem of factorization into 2-prime factor, is NP.

IV) if problem X can reduce to a known NP-Hard problem, then X must be NP-HARD.

anyone can verify my inference and learn me?‌

我试图找到一种算法来找到一个实数数组的K大小不相交的连续子集，以最大化元素的总和。Lx

详细说明，X 是一组 N 个正实数：
X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N.

称为长度 L 的连续子集S[i]定义为 X 的 L 个连续成员，从位置开始到位置n[i]结束n[i]+L-1：
S[i] = {x[j] | j=n[i],n[i]+1,...,n[i]+L-1} = {x[n[i]],x[n[i]+1],...,x[n[i]+L-1]}.

如果有两个这样的子集S[i]，S[j]则称为成对不相交（非重叠）|n[i]-n[j]|>=L。换句话说，它们不包含 X 的任何相同成员。

定义每个子集成员的总和：

S[1],S[2],...,S[K]目标是找到长度为 L 的K 个连续且不相交（不重叠）的子集，SUM[1]+SUM[2]+...+SUM[K]以使其最大化。

从一整天开始，我就被这个问题困住了。

当我们在图中找到最长的路径时，我们首先进行拓扑排序，然后检查相邻顶点的路径，并不断升级，选择边权重的最大值或另一个顶点的备用路径。

因此，我们能够解决这个问题，因为拓扑排序只能对无环图进行。因此这类问题只能针对无环图来解决。

因此，我们能够解决这个问题，因为拓扑排序只能对无环图进行。因此这类问题只能针对无环图来解决。

现在，如果我提出另一个案例。如果所有边都具有相同的权重并且我们不查看图形的循环会怎样。这是否可以解决。每次我想到这一点时，如果我们可以选择任何源，考虑到我们必须选择最大数量的节点（最长路径），我看不到拓扑排序的任何用途。

这也是NP Hard还是我们可以解决这个问题？

PS：我在有向未加权图中经历了这个最长的非循环路径，但只有解决最长路径问题的算法。

我在复杂性证明方面遇到了一些困难：我处理了 3 个问题：A、B 和 C 我知道：

• A-> B
• A-> C
• C -> B

A-> B 含义：如果我对 A 有一个“是的答案”，那么我对 B 有一个“是的答案”。我知道 A 属于 NP，B 和 C 是 NP 完全的。此外，我可以为 A 编写一个对 C 进行二次调用的算法。
我可以推断出 A 的复杂性吗？

更准确地说：我有一个由 k 个对象组成的集合 P。如果所有这些对象都被移除，问题 A 的回答是，否则为否。如果这些对象之一可以被移除，则问题 C 的回答是，否则为否。我们有一个约束，即每一步都必须删除至少一个对象。在最坏的情况下，我们会进行 P 步。所以算法 A ：

我正在尝试解决旅行推销员问题的修改版本。这是对基本 TSP 的修改，使所有节点都具有颜色属性，并且最优路径不能依次接触超过四个相同颜色的节点。这将在不超过 100 个节点的连接图中运行。我正在尝试使用协和飞机来运行它。

有谁知道如何将颜色约束添加到协和式飞机上？

谢谢