-
2 votesanswersviews
叶片约束MST问题的简化为哈密顿路径问题
众所周知,计算具有最小可能叶数的生成树是NP完全的 . 但我无法弄清楚这个问题的多项式时间减少到哈密顿路径问题 . 我的指数减少: if(hamiltonian path exists for whole graph) min leaves = 1; return; else for each vertex of the graph if(hamilton... -
966 votesanswersviews
NP,NP-Complete和NP-Hard有什么区别?
NP , NP-Complete 和 NP-Hard 之间有什么区别? 我知道网上有很多资源 . 我想阅读你的解释,原因是它们可能与那里有什么不同,或者它在那里,我不知道 . -
363 votesanswersviews
什么是计算机科学的NP-complete?
什么是NP完全问题?为什么它是计算机科学中如此重要的话题? -
1 votesanswersviews
一些NP-Complete问题怎么也是NP-Hard?
我正在尝试以一种直观的方式将我听到的P,NP,NP-Complete和NP-Hard包裹起来,以便我不必记住他们的定义 . 在下图中(左手方案,P!= NP),NP-Complete和NP-Hard之间存在重叠区域 . 这是否意味着一些问题既是NP-Complete又是NP-Hard?根据这个特殊答案,我发现这是矛盾的:What are the differences between NP, NP... -
1 votesanswersviews
NP-complete与NP-hard(为什么它们不相等?)
为什么NP-hard不等于NP-complete? My informal understanding of definitions being used: NP - 可以在多项式时间内验证的所有问题 NP完全 - 所有NP和NP难的问题 NP-hard - 至少和NP中最难的问题一样难 决策问题 - 询问有关输入的问题并输出bool值的问题 Confusion: P与NP未知解的问题源于这样... -
1 votesanswersviews
在图中找到最少彩色的路径
我试图解决的问题是: 给定图G =(V,E)使得每个 edge 以10种颜色中的一种颜色和两个顶点着色:s,t . 我需要找到一种算法,它可以产生从s到t的(最短)路径,该路径可以通过最少量的颜色 . 我的想法是将图表复制10次: 第一个副本将仅包含一种颜色的边 第二个将仅包括两种颜色的边缘......依此类推 . 此外,我将外部节点:s'连接到每个副本中的每个“s”节点 . 但是,我已经想到,对...