问题标签 [np-complete]

假设您有货物。它需要从 A 点到 B 点，从 B 点到 C 点，最后从 C 点到 D 点。您需要用最少的钱在五天内到达那里。每条支线有三个可能的托运人，每条支线都有自己不同的时间和成本：

您将如何以编程方式寻找最佳组合？

到目前为止，我最好的尝试（第三或第四种算法）是：

1. 为每条腿找到最长的托运人
2. 淘汰最“贵”的一个
3. 为每条腿找到最便宜的托运人
4. 计算总成本和天数
5. 如果天数可以接受，则完成，否则，转到 1

在 PHP 中快速模拟（请注意，下面的测试数组可以流畅地工作，但是如果您使用上面的测试数组尝试它，它不会找到正确的组合）：

我想我实际上可能需要做一些事情，我逐个制作每个组合（带有一系列循环）并将每个组合的总“分数”相加，然后找到最好的一个......

编辑：澄清一下，这不是“家庭作业”（我不在学校）。这是我当前工作项目的一部分。

要求（一如既往）一直在不断变化。如果在我开始解决这个问题时给了我当前的限制，我将使用 A* 算法的一些变体（或 Dijkstra 或最短路径或单纯形或其他东西）。但是一切都在变化和变化，这将我带到了现在的位置。

所以我想这意味着我需要忘记我到目前为止所做的所有废话，只使用我知道我应该使用的东西，这是一种寻路算法。

我有一个十进制数（我们称之为目标）和一个其他十进制数的数组（我们称之为数组元素），我需要从总和为目标的元素中找到所有数字组合。

我偏爱 C# (.Net 2.0) 中的解决方案，但无论如何最好的算法都可能获胜。

您的方法签名可能类似于：

是否有用于在图中找到哈密顿步行的多项式时间算法？

我的算法是 N 阶乘，而且非常慢。

P=NP 是否是计算机科学中最著名的问题。这是什么意思？为什么它如此有趣？

哦，为了获得额外的荣誉，请张贴一份声明的真假证明。:)

假设您有一个由一堆固定大小的块组成的大文件。这些块中的每一个都包含一些可变大小的记录。每条记录必须完全适合单个块，然后根据定义，这些记录永远不会大于完整块。随着时间的推移，记录在这些块中添加和删除，因为记录来自这个“数据库”。

在某些时候，尤其是在可能将许多记录添加到数据库并删除了一些记录之后 - 许多块可能最终只被部分填充。

什么是一个好的算法来打乱这个数据库中的记录，通过更好地填充部分填充的块来压缩文件末尾不必要的块？

算法要求：

• 必须在原始文件的位置进行压缩，而不是暂时将文件从其起始大小最多扩展几个块
• 该算法不应不必要地干扰已经基本满的块
• 必须一次从文件读取或写入整个块，并且应该假设写入操作相对昂贵
• 如果记录从一个块移动到另一个块，则必须在从其起始位置删除之前将它们添加到新位置，以便在操作中断时不会因“失败”压缩而丢失记录。（假设这种记录的临时重复可以在恢复时检测到）。
• 可用于此操作的内存可能只有几个块的数量级，这仅占整个文件大小的很小百分比
• 假设记录大约为 10 字节到 1K 字节，平均大小可能为 100 字节。固定大小的块大约为 4K 或 8K，文件大约为 1000 个块。

有问题的问题/漫画：http: //xkcd.com/287/

我不确定这是不是最好的方法，但这是我迄今为止提出的。我正在使用 CFML，但任何人都应该可以阅读它。

上面的代码告诉我，加起来 15.05 美元的唯一组合是 7 个混合水果订单，我的 testCombo 函数需要执行 232 次才能完成。

有没有更好的算法来得出正确的解决方案？我找到了正确的解决方案吗？

什么是NP完全问题？为什么它在计算机科学中如此重要？

从 NP-Complete 上的维基百科条目：

“证明一些新问题是NP完全的最简单方法是首先证明它在NP中，然后将一些已知的NP完全问题简化为它”

我很确定我理解这一点：如果我有问题，我可以证明它是 NP-Complete 如果我：

1. 证明它在 NP 中（可以在非确定性图灵机上以多项式时间验证问题的解决方案）

2. 证明一个已知为 NP-Complete 的问题可以“简化”为新问题

所以，我的问题是，第一个 NP 完全问题是如何“证明”为 NP 完全的？有一次，已知 NP 完全问题的集合必须为零，这使得无法诉诸上述过程中的步骤 2。

这让我觉得有一种我不知道的不同的证明方法。由于缺乏已知的多项式时间解，对于某些问题，要么是这样，要么可能是整个 NP 完全属性被“假设”。（实际上，在写完这篇文章后，如果是这种情况，我不会感到惊讶，但无论哪种方式，我都希望得到一些大师的反馈）。

我有一个与子集和问题有关的问题，我想知道这些差异是否使它更容易，即可以在合理的时间内解决。

给定一个值 V、一个集合大小 L 和一个数字序列 [1,N] S，S 中有多少个大小为 L 的子集总和小于 V？

这在三个方面不同于子集和问题：

1. 我关心有多少子集小于给定值，而不是有多少相等。
2. 子集大小是固定的。
3. 我关心有多少集合总和小于 V，而不仅仅是是否存在。

有没有合理有效的算法来解决这个问题？

编辑：显然，这可以使用组合生成算法在 O(N choose L) 中完成。我真正感兴趣的是可以显着加快速度的巧妙技巧。

给定一个 *n 大小的多头无环图，其中每个节点最多有三个子节点和三个父节点，是否存在一个非指数算法来识别是否存在一个 n 长度路径，其中没有两个节点共享相同的值，并且每个一个集合的值被占？

基本上，我有一个 n*n 迷宫，其中每个空间都有一个随机值 (1..n)。我需要找到包含每个值的 n 个节点的路径（从顶部到底部）。

现在我正在使用深度优先搜索，但那是T(n) = 3T(n-1) + O(1)一个O(3^n)非理想的解决方案。

确认我的恐惧，或指出我正确的方向将不胜感激。

编辑：为了让这个更具体一点，这里是一个带有解决方案的迷宫（使用深度优先解决方案解决）。