问题标签 [np-hard]

我想澄清一个概念。为了证明一个问题是 NP 完全的，我们使用约简。

现在假设我有 L<=L'。减少是从 L 到 L' 还是我也可以反过来做？即我可以证明如果 L 可以使用 L' 来解决，那么 L' 是 NP 完全的吗？

我对此感到很困惑。

例如。为了从火腿循环减少到火腿路径，我们采用了倒退的方式。

此外，我无法通过减少火腿循环来解决我必须证明“在至少有 k 个边的图中是否存在从 s 到 t 的路径”的问题。

请给我一个澄清并指导我解决上述问题。谢谢

我正在开发一个项目来实施和测试一个 NP-Hard/Complete 问题。我有一个大致的想法来做一些关于调度的事情，并且已经阅读了很多关于 Job Shop 问题的内容。我知道 OR 库中有著名的测试用例/基准可供使用。我有适当的代码（Java）来读取测试实例并存储其数据。现在我感觉陷入了一个循环，试图找到一种算法/方法来创建一个时间表，然后提出一个最佳时间表。我读了很多学术论文，但我通常会迷失在其中，尤其是复杂的集合符号。我希望我能找到更多伪代码的例子。我知道这是一个经典问题，我想知道是否有人对作业车间的直接经典解决方案提出建议——尤其是任何有伪代码示例的解决方案。我不需要为这个项目做原创研究。我只需要学习如何应用已知技术来解决 NP-Hard 问题、编写代码、运行测试、展示实验结果并对其进行评论。任何建议或帮助将不胜感激。

“必须完成许多工作，每项工作都包括在一定时间内使用多台机器。问题是要找到在最短的时间内在所有不同机器上完成所有工作的最佳计划。”

示例问题实例：

datalines 部分中的每一行通过 10 对连续数字指定一个作业。每对数字定义了作业的一个任务，代表了作业在机器上的处理。对于每一对，第一个数字标识它执行的机器，第二个数字是持续时间。10 对的顺序定义了作业的任务顺序。

“劳伦斯 10x10 实例”（表 6，实例 4）；也称为 (seta4) 或 (A4)(Applegate 和 Cook; 1991) -10 机器编号 0-9 -10 行 = 10 个工作 -- 最佳：842

2 44 3 5 5 58 4 97 0 9 7 84 8 77 9 96 1 58 6 89

4 15 7 31 1 87 8 57 0 77 3 85 2 81 5 39 9 73 6 21

9 82 6 22 4 10 3 70 1 49 0 40 8 34 2 48 7 80 5 71

1 91 2 17 7 62 5 75 8 47 4 11 3 7 6 72 9 35 0 55

6 71 1 90 3 75 0 64 2 94 8 15 4 12 7 67 9 20 5 50

7 70 5 93 8 77 2 29 4 58 6 93 3 68 1 57 9 7 0 52

6 87 1 63 4 26 5 6 2 82 3 27 7 56 8 48 9 36 0 95

0 36 5 15 8 41 9 78 3 76 6 84 4 30 7 76 2 36 1 8

5 88 2 81 3 13 6 82 4 54 7 13 8 29 9 40 1 78 0 75

9 88 4 54 6 64 7 32 0 52 2 6 8 54 5 82 3 6 1 26

一般来说，假设我们有一个NPC问题。给它增加更多的约束（让它更困难），这个问题有可能变成 NPH 吗？我知道 NPC 和 NPH 之间的区别，但我不知道如何证明向现有 NPC 问题添加新约束会使其成为 NPH 还是仍然是 NPC？

我见过几个调度问题，说这个问题是 NP 困难的。我的问题是 1）当我们说一个问题是 NP 困难时，这是否意味着它不在 NP 中？因为如果它是 NP，我们说这个问题是 NP 完全的。我知道问题出在 NPC 中，如果 a）在 NP 中 b）在 NP 中很难。

我有一组顶点，每对顶点之间定义了一些利润，因此利润（i，j）可能不等于利润（j，i）。此外，存在正权重周期，利润可能为负。

这是一个寻找最大利润的NP-hard问题，所以问题是每个城市最多访问一个（不需要访问所有城市）的利润最大化。我尝试了以下算法来找到这个：

• 对完整顶点集的贪心算法。
• Greedy with brute force：首先找到顶点的贪心序列。这给出了几乎形成簇的近似顶点集。现在连续设置 8 个城市并重新排列它们以使用蛮力找到最大利润。

但是当在 100 个顶点上尝试时，这些并没有给出很好的结果。

是否有任何其他概率或近似方法来最大化成本？

经典的旅行商问题 (TSP) 定义之一是：

给定一个三角不等式成立的加权完全无向图，返回一条总权重最小的哈密顿路径。

在我的情况下，我不想要哈密顿路径，我需要两个众所周知的顶点之间的路径。所以公式是：

给定一个加权完全无向图，其中三角不等式成立，并且两个称为源和目标的特殊顶点返回一个最小加权路径，该路径恰好访问所有节点一次，并从源开始并结束到目的地。

我记得哈密顿路径是无向图中的路径，它只访问每个顶点一次。

对于原始问题，Christodes 算法是一个很好的近似值（最好解决方案的 3/2），是否可以针对我的情况进行修改？或者你知道另一种方式？

我正在尝试使用整数线性规划 (ILP) 来解决问题。由于问题是 NP-hard ，我想知道 Simplex Method 提供的解决方案是否是最优的？任何人都可以评论使用单纯形法的 ILP 的最优性或指向某些来源。是否有任何其他算法可以为 ILP 问题提供最佳解决方案？

编辑：我正在寻找通过 ILP 的任何算法（单纯形法、分支定界和切割平面）获得的解决方案的最优性的是/否答案。

我想尝试寻找解决旅行商问题的启发式/近似方法，为了做到这一点，我正在寻找一些“硬” TSP 实例（以及它们最知名的解决方案），以便我可以尝试解决他们，看看我能做多好。

理想情况下，它们只是基于文本的邻接矩阵列表或邻接列表（我不想处理解析，只是算法）。
通过“硬”，我的意思是它们实际上应该是不可能使用蛮力解决或近似的。
（这样我就可以有理由相信，如果我找到一个接近最知名答案的答案，那么我实际上是在做正确的事情，而不仅仅是走运。）

是否有任何列表可以用于此目的？我搜索了一下，但没有找到任何东西。

我想知道编码一个布尔公式需要多少位

@ 是 SAT 的一个实例。我认为它是 4 位，因为可能组合的总数是 2（power4）。那是对的吗？我应该计算 OR、NOT 和 AND 来计算编码所需的位数吗？我搜索了很多，但在这方面找不到任何东西。

由于通过映射将任何 NP Hard 问题简化为任何其他 NP Hard 问题，我的问题向前迈出了一步；例如，该算法的每一步：也可以映射到另一个 NP 硬吗？

提前致谢