问题标签 [np-hard]

最近我读了一篇研讨会的作品，上面写着：

匹配算法[用于一般图]可以扩展到加权情况，这似乎是可以在多项式时间内解决的“最难”的组合优化问题之一。

我立刻想到了以下问题：

你知道其他“P-hard”问题吗？

现在我想将 P-hard 定义为：“在该问题的文献中很晚才（1950 年之后）发现了多项式算法”。（或者如果已经有一种确定性算法可以在多项式时间内解决问题，那么如何更好地定义“困难”？）

我想找到一个确定性退火代码的开源示例。它几乎可以是任何语言：C、C++、MatLab/Octave、Fortran。我已经找到了用于模拟退火的 MatLab 代码，因此最好使用 MatLab。这是描述该算法的论文。

确定性退火是一种尝试找到成本函数的全局最小值的优化技术。该技术旨在能够使用随机性探索大部分成本表面，同时仍使用本地信息执行优化。该过程首先更改成本函数以引入随机性概念，从而允许探索大面积区域。每次迭代的随机量（由香农熵 [2] 测量）都受到约束，并执行局部优化。逐渐地，施加的随机性降低了，因此在终止时，算法优化了原始成本函数，产生了原始问题的解决方案

是否有某种语言是 NP 完全的，但我们知道一些“快速”算法？我的意思不是像背包那样我们平均可以做得很好，我的意思是即使在最坏的情况下，运行时间也类似于 2^n^epsilon，结果对于任何 epsilon>0 都成立，所以我们可以让它任意接近0。

我在尝试分类算法时遇到了以下算法问题。元素被分类为多层次结构，我理解为具有单个根的poset。我必须解决以下问题，这看起来很像set cover problem。

我在这里上传了我的乳胶问题描述。

设计一个满足 1 和 2 的近似算法非常容易，只需从 G 的顶点开始并“向上”或从根开始并“向下”。假设您从根开始，迭代地扩展顶点，然后删除不必要的顶点，直到您至少有 k 个子格。近似界取决于顶点的子节点数，这对我的应用程序来说是可以的。

有谁知道这个问题是否有正确的名称，或者问题的树版本？我很想知道这个问题是否是 NP 难的，也许有人对一个好的 NP 难问题有想法来减少或有一个多项式算法来解决这个问题。如果你有两个收集你的百万美元的价格。;)

一个工作的朋友向我介绍了子集和问题的一个有趣的变体：

给定一个大小为 n 的正整数集合 S，以及整数 a 和 K，是否存在一个（集合 S 的）子集 R，它恰好包含 a 个元素，其和等于 K？

他声称这可以用时间复杂度 O(nka) 来完成，我无法想出一个动态规划算法来实现这个运行时间。可以做到吗？

也许有人知道将石头（不同重量）放入不同大小的背包的算法，或者它有什么名字？我应该在 Prolog 中做到这一点。我给出了石头的重量和背包的容量。程序应该给我一个答案，我怎样才能把所有这些石头放进背包里。

我知道在 NP-HARD 中存在以下问题：给定一个简单的图 G=(V,E)，V 中有两个顶点 v，v'，一个整数 B，以及一个非负长度函数 len：E-> Z+ ，是否有一条从 v 到 v' 长度小于 B的简单路径？

我的问题是：在与以前相同的条件下，如果我们有兴趣在 G 中找到从顶点 v 到 v' 的最长但不一定简单的路径，那么问题仍然存在于 NP-HARD 中吗？

注意：我试图减少汉密尔顿路径，但我仍然无法证明 NP 是否存在问题，可简化为我提到的这个问题。我也查过Garey & Johnson，但我什么也没找到。

我想要一点提示来证明这个问题是否是 NP-HARD。提前致谢！

假设我有一条抛物线。现在我也有一堆相同宽度的棍子（是的，我的绘画技巧很棒！）。我怎样才能将这些棒堆叠在抛物线内，以便尽可能减少它使用的空间？我相信这属于背包问题的范畴，但是这个维基百科页面似乎并没有让我更接近现实世界的解决方案。这是一个NP-Hard问题吗？

在这个问题中，我们试图最小化消耗的面积（例如：积分），其中包括垂直面积。

我最近阅读了有关NP和P的文章。那么寻找给定单词组合的问题是NP问题吗？例如，给定单词anto，结果可以是 anot,toan 等。据我所知，只要我们可以在多项式时间内检查问题的解决方案，就意味着它属于 NP。那么组合问题属于NP吗？

这只是为了知道我是否已经很好地理解了NP和P。

将任何问题拆分为 NP 和 P 的主要意图或主要用途是什么？这是否有任何历史原因，还是他们创造了这些概念来帮助我们？如果是这样，这些对我们有什么帮助？