问题标签 [np-hard]

所以我有一个基本上是这样的问题：我有一堆字符串，我想构造一个 DAG，使得每条路径都对应一个字符串，反之亦然。但是，我可以自由地任意排列我的字符串。字符的顺序无关紧要。我生成的 DAG 具有与之相关的成本。基本上，DAG 中一个分支的成本与其子路径的长度成正比。

例如，假设我有字符串 BAAA、CAAA、DAAA，并且我构造了一个 DAG 来表示它们而不对它们进行置换。我得到：

() -> (B, C, D) -> A -> A -> A

其中元组表示分支。

就我的目的而言，更便宜的表示是：

() -> A -> A -> A -> (B, C, D)

问题是：给定 n 个字符串，对字符串进行置换，使得对应的 DAG 成本最低，其中成本函数为：如果我们从源头开始深度遍历图，从左到右顺序，我们的节点总数访问，具有多样性。

所以第一个例子的成本是12，因为我们必须在遍历中多次访问A。第二个示例的成本是 6，因为在处理分支之前我们只访问 A 一次。

我感觉这个问题是NP Hard。这似乎是一个关于形式语言的问题，我对这些算法还不够熟悉，无法弄清楚我应该如何进行缩减。我本身不需要完整的答案，但如果有人能指出一类似乎相关的众所周知的问题，我将不胜感激。

我遇到了许多可以表述为图形问题的问题。它通常是 NP 难的，但有时可以证明该图是平面的。因此，我对学习这些问题和算法很感兴趣。

据我所知：

1. 平面图中的最大切割
2. 平面图中的四色
3. 三次平面图中的最大独立集

希望有人能完成这份清单。

有一个包含 N 个整数的集合 S，每个整数的值 1<=X<=10^6。问题是将集合 S 划分为 k 个分区。分区的值是其中存在的元素的总和。分区是以这样的方式完成的，集合 S 的总值在 k 个分区中公平分布。还需要定义公平的数学含义（例如，目标可以是最小化分区值与集合 S 的平均值的标准偏差（即 sum(S)/k)）

例如 S = {10, 15, 12, 13, 30, 5}, k=3

一个好的分区是 {30}, {10, 15}, {12, 13, 5}

一个坏的分区是 {30, 5}, {10, 15}, {12, 13}

第一个问题是在数学上表达一个分区优于另一个分区的条件。第二个问题是如何解决问题。问题是NP-Hard。有什么启发式方法吗？

在我试图解决 N <= (k*logX)^2 的问题中，K 从 2 到 7 不等。

==================================================== =================================

基于其他相关的 SO 问题，评估分布有两个合理的函数：

a) 最小化具有最大值的分区的值。

再想一想，这不是一个好的指标。考虑，一组 {100, 40, 40} 被划分为三个子集。该指标不区分以下两种分布，即使其中一种明显优于另一种。

分布 1：{100}、{40}、{40} 和分布 2：{100}、{40、40}、{}

b) 最小化给定分区中任意两个值之差的最大值，即最小化 max|AB| 对于任何 A、B

我一直在努力解决一个问题......整个问题很复杂......但让我尽力解释真正重要的部分......

我有一个图表，其中每条边代表连接的两个节点之间的相关性。每个节点都是一个时间过程（TC）（即400个时间点），其中事件将在不同的时间点发生。两个节点之间的相关性定义为重叠事件的百分比。为简单起见，让我们假设每个节点上发生的事件总数与 $tn$ 相同。如果两个 TC（节点）有 $on$ 重叠事件（即，发生在完全相同的时间点的事件）。然后，相关性可以简单地定义为$on$/$tn$。

现在，我有一个由 11 个节点组成的网络；我知道每两个节点之间的相关性。如何为所有满足相关约束的 11 个节点生成 TC？

当您知道两者之间的相关性时，很容易对两个节点执行此操作。假设 TC_1 和 TC_2 的相关值为 0.6，这意味着两个 TC 中有 60% 的重叠事件。此外，假设 TC_1 和 TC_2 的事件总数与 $tn$ 相同。将事件放置在两个 TC 中的一个简单算法是首先随机选择 0.6*$tn$ 个时间点，并将这些时间点视为两个 TC 中发生重叠事件的时间段。接下来，在 TC_1 中随机选择 (1-0.6)*$tn$ 时间点，以放置 TC_1 的其余事件。最后，随机选择 TC_2 中的 (1-0.6)*$tn$ 时间点，其中 TC_1 中对应的时间点没有发生任何事件。

然而，当你考虑一个 3 节点网络时，它开始变得越来越难，其中生成的三个 TC 需要满足所有三个相关约束（即 3 条边）......对于 11 节点网络来说几乎不可能做到这一点...

这对你有意义吗？如果不是请告诉我...

我在想这只是一个诡计的计算机科学编程问题......但我越想它，它更像是一个线性编程问题，不是吗？

有人有合理的解决方案吗？我在 R 中这样做，但任何代码都可以......

我想知道 TSP 的问题名称是什么，不考虑返回起点的方式以及解决此问题的算法是什么。

我研究了最短路径问题，但这不是我要找的，这个问题只能从 2 个指定点找到最短路径。但我正在寻找的是我们给出 n 分并且只输入 1 个起点的问题。然后，找到通过所有点的最短路径恰好一次。（终点可以是任何点。）

我还研究了哈密顿路径问题，但它似乎没有解决我定义的问题，而是找出是否存在哈密顿路径。

在调度问题 P||Cmax 中给出：

n- 要调度的任务
m数 - 机器数
向量p- 保持 n 个任务中每个任务的工作时间。

p每次是如何定义的？

即，它是整数还是浮点数？

如果一个已知为 NP-Complete 的问题 A 可以在多项式时间内简化为另一个问题 B，则 B 是 (A) NP-Complete (B) NP-hard

无论问题 B 是否在 NP 中，都没有给出任何内容。我很困惑，因为在 Hopcraft 和 Ullman 书中给出了一个定理，如果一个 NP 完全问题 P1 可以在多项式时间内简化为问题 P2，那么 P2 是 NP 完全的。但它也要求一个问题是 NP 完全的，它应该属于 NP 类。伙计们帮助理解这个概念。

编写一个程序，找出最大可能的字母矩形，使每一行构成一个单词（从左到右），每列构成一个单词（从上到下）。

我发现了这个有趣的问题。这不是家庭作业，尽管听起来可能是这样。（我不在学校）。我这样做是为了好玩。

例子

从cat , car , ape , api , rep , tip我们得到以下矩形（正方形）：

我最初的想法是构建某种前缀树，这样我就可以检索所有以特定字符串开头的单词。当我们已经有 2 个或更多单词（从上到下或从左到右阅读）并且我们需要找到下一个要添加的单词时，这将很有用。

还有其他想法吗？

编辑

这可以用长方体（3D 矩形）来完成吗？

如果它需要在对角线上有有效的单词怎么办（创意来源：user645466）；如何优化它的算法？

如果我想证明一个问题是 np-hard 问题，可以多次使用现有的 np-hard 问题吗？例如在图中使用哈密顿循环 n 次，其中 n 是顶点数？或者我是否需要将图形转换为可以通过使用 1 次的现有 np-hard 问题轻松解决的东西？

Wiki 说，当您将 poly time 中的 np 完成问题转换为 A 时， A 是 np 困难的。见http://en.wikipedia.org/wiki/NP-hard

但是下面的 pdf 说，当您在多项式时间内将 np 难题转换为问题 A 时，A 是 np - hard http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard。 pdf

我应该相信哪一个？