标签: np

存在许多已知为NP难的优化问题,例如旅行商问题,MAX-SAT或找到图的最小色数.鉴于这种问题,我很好奇以下问题的复杂性:

鉴于NP难度优化问题和候选解决方案S,S是问题的最佳解决方案吗？

直观地说,似乎这可能是共同的NP难,因为通过猜测更好的解决方案并将其用作见证人来反驳优化问题的答案很容易,但我不知道如何展示这一点.事实上,我真的不知道如何推断这个问题的复杂性.

有谁知道这个决策问题的复杂性有任何好的下限？知道这是否是共同NP难,PSPACE-hard等会非常有趣.

我正在尝试为这个问题提出一个合理的算法:

假设你有一堆球.每个球至少有一种颜色,但也可以是多色的.每个球都有一个重量和一个与之相关的值.还有一堆盒子,每个盒子只有一种颜色.每个盒子都有最多可以容纳的球.目标是在保持总重量W的同时最大化盒子中的值的总和,唯一的规则是:

为了将球放入盒子中,它必须至少具有盒子的颜色

(例如,您可以将蓝色和绿色球放入蓝色框或绿色框中,但不能放入红色框中.)

我已经进行了一些研究,这看起来类似于背包问题,也类似于匈牙利算法可以解决,但我似乎无法将其减少到任何一个问题.

我只是好奇是有这种类型的问题的某种动态编程算法使它在多项式时间内可解决,或者它只是伪装的旅行推销员问题.如果我知道最多有X种颜色会有用吗？任何帮助是极大的赞赏.如果它有帮助,我也可以用变量名称来形式化这个问题.谢谢!

这是一个简单的例子:

最大重量: 5

球:

1个红球 - (值= 5,重量= 1)

1个蓝色球 - (值= 3,重量= 1)

1个绿色/红色/蓝色球 - (值= 2,重量= 4)

1个绿色/蓝色球 - (值= 4,重量= 1)

1个红色/蓝色球 - (值= 1,重量= 1)

盒:

1红色(1个球)

1蓝色(可容纳2个球)

1绿色(持1个球)

最优方案:

在红色框中的红球

蓝色的球和蓝色框中的红色/蓝色球

绿色框中的绿色/蓝色球

总价值:13(5 + 3 + 1 + 4)

总重量:4(1 + 1 + 1 + 1)

注意:即使绿色/红色/蓝色球比红色/蓝色球更有价值,它的重量也会让我们超过极限.

编辑:

一个澄清点:具有相同颜色组合的球不一定具有相同的重量和值.例如,你可以有一个值为3且重量为1的红色球和另一个值为2且重量为5的红色球.

编辑2:

如果它有助于我们提出动态编程算法,我们可以假设整数权重和值.

因子:Gven是一个整数N,找到整数1 <a,b <N,如果它们存在则N = ab,否则说N是素数.

我知道素数测试是在P中,但为什么不考虑因素？

这是我的算法:

For each a = 1 ... sqrt(N)
    if(N % a == 0)
        b = N/a
        add (a,b) to the result
    Endif
EndFor

它以O(sqrt(N))运行.

我知道,P = NP一直没有解决到现在,但有谁能够告诉我一些关于以下内容:当前什么是最有前途的数学/计算机科学的方法是可以有助于解决这个问题？或者到目前为止还没有任何已知的方法可能有用吗？是否有关于此主题的任何(免费)纲要,我可以在这个领域找到所有/大部分研究成果？

这是我的第一个stackoverflow问题,所以要温柔.如果已经被打死了,我会事先道歉......我在NP上读了一些帖子,但我没有找到一个诱人的答案我的问题(如果有的话,我想出了一些新的).简述:

1. 是否存在可判定的决策问题,但在NP中却没有？
2. 如果是这样,那些要求解决方案比同等决策问题更困难的问题是什么？

我怀疑第一个问题的答案是响亮的"是",而第二个问题的答案是响亮的"不".

在第一种情况下,示例问题可能是"给定集合S,S的子集T和具有域2 ^ S的函数f,确定T是否最大化f".对于通用的S,T和f,如果不检查S的所有子集X的f(X),你甚至无法验证这一点,对吗？

在第二种情况下......好吧,我承认这更像是一种预感.出于某种原因,似乎答案是否应该包含一位(用于决策问题)或任何(有限)位数......或换句话说,为什么你不应该考虑作为"答案"的一部分,TM停止后留在磁带上的符号.

编辑:实际上,我有一个问题......你的结构如何表明功能问题"比决策问题更难"？如果有的话,你已经表明,回答功能问题并不比决策问题更容易......这是微不足道的.也许这是以粗心的方式提出问题的错.

给定NP中的TM T1解决了变量X的"X是问题P的解决方案"和(为了参数)固定P的问题,是否保证在NP中将存在TM T2,其中T1停止到处停止,它在停止的任何地方以"停止接受"状态结束,并在磁带上留下例如X的二进制表示？

我有几个数字数组(数组的每个元素只能取值0或1),就像这样

v1: 1; 0; 0; 1; 1; 
v2: 0; 1; 0; 0; 1; 
v3: 1; 1; 0; 1; 0; 
v4: 1; 0; 0; 1; 0; 
v5: 1; 1; 0; 1; 1; 
v6: 1; 1; 0; 1; 1; 

我希望找到这样的子集,当数组求和时,得到的数组具有2的倍数的单个元素.例如,v1 + v2 + v3得到的结果数组为2,2,0,2,2.结果数组可以具有2的倍数的任何值.

另一个例子:

v1: 1, 1, 1, 0, 1, 0
v2: 0, 0, 1, 0, 0, 0
v3: 1, 0, 0, 0, 0, 0
v4: 0, 0, 0, 1, 0, 0
v5: 1, 1, 0, 0, 1, 0
v6: 0, …

我不相信存在一种算法,用于在二分图中找到最大独立顶点集,而不是在所有可能的独立集中找到最大值的强力方法.

我想知道找到所有可能的顶点集的伪代码.

假设给出了一个带有4个蓝色顶点和4个红色的二分图.目前我会的

Start with an arbitrary blue,
  find all red that don't match this blue
  put all these red in Independent Set
  find all blue that dont match these red
  put these blue in Independent Set
  Repeat for next vertex in blue

Repeat all over again for all blue then all vertices in red.

我知道这种方式根本不能给我所有可能的独立集合组合,因为在第一步之后我选择了所有不匹配的颜色顶点而不是逐步完成所有可能性.

例如,给出具有匹配的图表

B  R
1  1
1  3 
2  1
2  3
3  1
3  3
4  2
4  4

Start with blue 1
  Choose …

我对搜索算法和回溯编程非常感兴趣.现在,我已经实现了算法X(请参阅我的其他帖子:确定无冲突集？)来解决确切的覆盖问题.这非常有效但我现在有兴趣用更基本的回溯变体来解决这个问题.我无法弄清楚如何做到这一点.问题描述与以前相同:

假设你有一堆集合,而每个集合都有几个子集.

Set1 = {(香蕉,菠萝,橙子),(苹果,羽衣甘蓝,黄瓜),(洋葱,大蒜)}

Set2 = {(香蕉,黄瓜,大蒜),(鳄梨,番茄)}

...

SetN = {...}

现在的目标是从每个集合中选择一个子集,而每个子集必须与任何其他所选子集无冲突(一个元素不包含在任何其他所选子集中).

作为一个例子,我写了两个Java类.集合由单个字符标识,元素是普通数字.

我特别有两个问题:

• 如何迭代所有集合/子集,以便可以使用启发式(选择具有最小元素的子集,最低成本,......)
• 如何维护选定的集+子集及其包含的元素.

我能找到的所有其他例子都是Sudoku或n-Queens,并且都使用固定的for循环.除此之外,我正在考虑一种相当普遍的方法,其中如果所选择的路径/集合可能与先前选择的子集/元素冲突,则可以使用函数"isPossiblePartialSolution"来检查.

以下是两个Java类:

import java.util.ArrayList;

public class Main {

public static void main(String[] args) {

    ArrayList<Set> allSets = buildRandomTest();

    for(Set r : allSets) {
        System.out.print("Set with id: " + r.id + " is subset in collection: " + r.name + " and contains: ");
        for(Integer n : r.listOfElements) {
            System.out.print(" " + n + " ");
        }
        System.out.println();
    }

}

public static …

我在期中考试时遇到了一个问题.任何人都可以澄清答案吗？

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

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

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

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

2)O(| E |)次

3)O(lg m)次

4)因为A是NP-Hard,这是不可能做到的.

给定一个布尔值的2D数组,我想找到包含至少2列和至少2行的所有模式.问题与图中的派系有些接近.

在下面的示例中,绿色单元格表示"真实"位,灰色表示"假".模式1包含cols 1,3,4和5以及行1和2.模式2仅包含第2列和第4列以及第2,3,4行.

这背后的商业理念是在各种社交网络用户群之间找到相似性模式.在现实世界中,行数最多可达3E7,列数最多可达300.

除了蛮力匹配之外,无法找到解决方案.

请告知问题的正确名称,以便我可以阅读更多内容,或建议优雅的解决方案.