标签: np

我真的很困惑为什么2-CNF SAT在P中,而3-CNF SAT在NPC中.我读了CLRS,我理解他们如何证明3-CNF SAT在NPC中.我不能使用从SAT到2-CNF-SAT相同的可还原性来证明2-CNF-SAT在NPC中.我不明白为什么2-CNF SAT在P.

考虑一下这里描述的问题(在下面重现.)可以将一些更好的已知NP完全问题减少到它吗？

问题:

有一排房子.每个房子都可以涂上三种颜色:红色,蓝色和绿色.用一定颜色绘制每个房子的成本是不同的.你必须为所有的房屋涂漆,使两个相邻的房屋没有相同的颜色.你必须以最低的成本为房屋涂漆.你会怎么做？

注意:绘画房屋1红色的成本与绘画房屋2红色的成本不同.房屋和颜色的每种组合都有自己的成本.

我有一个基于网格的图,其中节点和边占据单元格.边缘可以交叉,但不能在同一方向上相互移动.

让我们说我想优化图形,以便边缘覆盖的距离最小化.我目前正在使用A*搜索每个连接,但算法是贪婪的,不提前计划.请考虑下面的图表,其中更改连接的顺序(请注意,对于任何给定边,可以有多个最短路径,请参阅绿色和紫色连接).

我的直觉说这是NP-Complete,并且需要进行详尽的搜索,随着图形的大小增加,这将是非常昂贵的.但是,我没有办法表明这一点,并且它与通常涉及最小化交叉的其他图形嵌入问题并不完全相同.

我在这个网站上阅读了很多关于完整加权图和汉密尔顿旅游主题的内容,其中一位用户询问,询问我大学的很多工作人员,但无法得到一个好的答案,我将这个问题的一个重要部分更改为如下:

问题A:给出一个完整的加权图G,找到weights最小权重的哈密顿游.

问题B:给定一个完整的加权图G和实数R,G是否具有最多R的哈密顿巡回训练？

假设有一台机器可以解决B.我们可以多少次调用B(每次给出G和实数R),用该机器解决问题A？假设G中边缘的总和达到M.

1. 我们不能这样做,因为有无数的状态.

2. O(| E |)次

3. O(lg m)次

4. 因为A是NP-Hard,这是无法做到的.

我读了这个文件,在第2页他写道:

a)优化问题(严格意义上):找到最优解

b)评估问题:确定最优解的价值

c)绑定问题:给定绑定B,确定最优解的值是高于还是低于B.

在接下来的两段

为了在解决b)中利用c),我们使用这样的事实:组合问题的可能值通常是离散的并且可以被认为是整数.假设我们可以在时间T内解决约束问题c)对于相应的评估问题b)人们通常知道该值在整数的某个范围[L,U]内.使用二进制搜索,我们用log |来解决评估问题 U - L | 调用绑定问题c),因此在时间T log | U - L |.

在接下来他写道:

例如:加权图上的TSP Kn =(V,E,w:E - > Reals),| V | = n,| E | = n-choose-2.用c)解决b).n个顶点图中的巡回或哈密顿循环恰好有n个边.因此,n个最长边的和S是最佳巡回长度的上限.另一方面,n个边缘的所有m个选择n子集的和是一组有限数,并且这些数中的两个中的最小非零差d定义了巡回长度的粒度.两个不同的游览具有相同的值,或者它们的长度相差至少d.因此,计算log(S/d)约束问题的二进制搜索确定最佳游览的长度(值).

我的问题是我们可以通过这种方式调整这个解决方案来选择(3)吗？

旅行推销员优化(TSP-OPT)是NP难问题,旅行推销员搜索(TSP)是NP完全的.但是,TSP-OPT可以简化为TSP,因为如果TSP可以在多项式时间内求解,那么TSP-OPT(1)也可以.我认为A要降低到B,B必须要比A更难.如我在下面的参考文献中所见,TSP-OPT可以降低到TSP.TSP-OPT应该比TSP更难.我很迷惑...

参考文献:(1)算法,Dasgupta,Papadimitriou,Vazirani练习8.1 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf https://cseweb.ucsd.edu/classes/sp08/cse101 /hw/hw6soln.pdf

http://cs170.org/assets/disc/dis10-sol.pdf

我有详细的、高度不规则的形状，如下所示：

我正在寻找一种方法，使它们覆盖一个没有孔的矩形区域，并且形状之间的混合/覆盖最小化。还允许有限的放大和自由旋转。

我搜索了包装和覆盖算法，但没有太多关于不规则形状的信息，而且我看到的每一个都假设形状不能混合。就我而言，这是可以接受的。

鉴于上述形状，一种解决方案将如下所示：

为了实现上述结果，形状被平移、旋转和缩放。

鉴于：

• 所有形状都可以放大和缩小（最大 2 倍）和旋转
• 形状可以重叠
• 形状的一部分可以在矩形之外
• 形状中没有孔

你知道可以解决这个问题的算法吗？

有时评估积分非常困难，但很容易验证解是否正确。在我看来它至少应该是 np，但我对这个概念的理解是有限的，我可能会遗漏一些东西

编辑：为了清楚起见，我很好奇算法的复杂性，该算法找到函数的反导数以解决不定积分，而不是计算定积分的数值近似值。

我读到经典的旅行商问题（TSP）是 NP 难问题。并且有一些近似算法以及在 O(N^2 * 2^N) 时间内运行的特定算法。但据我所知，这些是针对一般图表中的 TSP 的。

所以我的问题是，是否有更好的（优选多项式时间）算法来求解 M x N 网格中的 TSP？

例如，假设有一个 3x4 的网格，从一个单元格到 2 个相邻（底部和右侧）单元格中的每一个单元格的移动成本不同。所以我想找到访问所有单元格的最小成本，从单元格 (0, 0) 开始并返回到单元格 (0, 0)。

编辑：为了澄清事情，我很确定这不是欧几里得 TSP。为简单起见，请考虑以下示例。一个矩形被分成M行和N列。推销员位于单元格 0, 0（左上角单元格）。他必须访问所有单元格并仍然返回到起始单元格 (0, 0)。但他只能从一个单元格移动到其 4 个相邻单元格（上、左、下、右）中的每一个。并且从一个小区到其任何一个相邻小区的成本可能并不相同。

谢谢。

因此,这是一个引人深思的问题,可以让我的教授了解NP-Completeness的概念.我知道为什么应该有一个解决方案,由于NP-Completeness的规则,但我不知道如何找到它.所以这是问题所在:

问题是两个处理器的简单任务调度问题.每个处理器可以处理其中一个n任务,任何两个任务都可以同时完成.每个任务都有一个结束时间e,必须在此时完成.每个任务也有一个持续时间d.所有时间值,例如结束时间,持续时间和系统中的当前时间(时间将从0开始)都是整数.因此我们给出了一个n任务列表,我们需要使用这两个处理器来安排它们.如果无法安排任何一个,则算法必须不返回任何解决方案.请记住,顺序无关紧要,只要没有重叠并且每个任务在截止日期之前完成,哪个处理器获取哪个任务都无关紧要.

所以这里是问题得到概念/抽象的地方,比如我们可以访问一个特殊的小函数,我们不知道它是如何工作的,我们所知道的就是:给定一个n任务列表和当前的时间表,它将返回true或false基于从这一点来看,算法是否可以解决.此函数假定已安排的任务是一成不变的,它只会更改未安排的任务的时间.但是,所有这个函数都返回true或false,如果找到解决方案,它将不会给你正确的时间表.关键是你可以在执行调度问题时使用特殊功能.目标是解决调度问题,并使用对特殊函数的多项式调用次数,返回正确调度的每个作业的工作时间表.

编辑:澄清一下,问题是:创建一个解决方案来安排所有n任务,没有任何超过截止日期,使用多项式调用"特殊功能".

我认为这个问题是为了证明验证解是多项式,但发现它是非多项式的.但是我的教授坚持认为有一种方法可以使用对特殊函数的多项式调用来解决这个问题.由于整个问题是NP-Complete,这将证明运算符的非多项式方面在算法的"决策部分"中出现.

如果你希望我清理任何东西只是发表评论,我知道这不是对这个问题的完美解释.

我认为我对 NP-Complete、NP-Hard 等总体上有相当不错的理解，但突然间，偶然发现了一些文献，我发现有人在说一个“自然”的 NP 完全问题——明确地与那些引号。我不明白他们的意思，所以我试着用谷歌搜索——它又出现了几次，但没有人费心解释他们所说的“自然”是什么意思。

有人可以向我解释在“自然”周围加上引号的上下文是什么 - 当他们说“自然”NP完全问题时是什么意思？