我正在努力理解什么是不确定多项式时间问题和NP完全问题.我理解多项式时间可解决的问题,并在维基百科中看到NP问题.在阅读了这篇文章后,我试着想一些示例问题.据我了解,深度优先搜索的是无向的NP完全,因为每个决策都可以做出非决定性的(即如果我做出了错误的决定,我可以尝试其他选择)如果图表很大(cit是一个如果图形尺寸很小,则为多项式.)
任何人都可以用简单的例子简单地解释所有这些NP术语,而不需要使
tem*_*def 38
有很多方法可以考虑NP和NP-完整性.我会的定义开始NP,那么就说说NP -hardness,终于NP -completeness.
从高层次来看,P和NP是一类问题.问题出在P中,如果是一个是或否的问题(决策问题),并且有一些算法可以在多项式时间内解决问题.例如,问题是"你能从这个图中的节点u到节点v吗？" 属于P,因为你可以通过深度优先搜索来解决它.(注意DFS本身不在P中,因为DFS是算法而不是问题).P中问题的另一个例子是检查序列是否按排序顺序排列.
问题在于NP,如果它是一个是或否的问题(决策问题),其中可以在多项式时间内验证正确的答案.例如,一个经典的NP问题是,在给定一组已知权重的权重的情况下,您可以选择一组权重恰好为某个量k的权重(这称为子集和问题).弄清楚是否存在一组具有该属性的权重可能是棘手的,但如果我给你一组我称之为正确的权重,你可以很容易地检查我是否给了你正确的权重通过添加它们并查看它们是否总计为k来设置权重集.
其原因NP被称为"非确定性多项式"是想以不同的方式NP是考虑一个神奇的算法,可以以某种方式猜测正确答案在多项式时间的问题.也就是说,如果您可以编写一个允许对问题的答案进行猜测并在多项式时间内运行的算法,那么您要解决的问题是NP.回到我们的权重示例,我们可以为这个问题编写如下的猜测算法.从线性时间开始,猜测哪组权重是正确的权重集,然后将它们全部加起来,看看它们是否总共为k.如果是,请报告答案为"是".否则,说"不".如果总是保证这个程序能够做出正确的猜测,那么给出解决问题的任何输入它总会找到一个并报告"是",如果没有解决方案,它总是会猜错并报告"否".
现在计算机科学中最基本和最重要的问题之一是NP中已知的任何问题是否也在P中.也就是说,如果我们能够有效地(在多项式时间内)轻松验证问题的答案,我们是否总能有效地解决该问题(在多项式时间内)？众所周知,P中的任何问题也是NP中的问题,因为你可以使用多项式时间算法来产生答案,然后检查它是否正确,但是没有人找到过在多项式中解决NP中的任意问题的方法时间.
这样做的原因是NP中的一些问题被称为NP -complete,这意味着(非正式地)它们至少与NP中的其他问题一样难.如果我们能够有效地解决这些问题(多项式时间),那么我们就可以在多项式时间内解决NP中的每个问题.这将是一个巨大的交易,因为NP中存在很多问题,这些问题非常重要,因为我们目前没有好的,快速的算法.这也是P = NP问题的诱惑,因为它只需要一种算法来证明假定难以解决的大量问题实际上可以有效地解决.
更正式地说,NP中的问题称为NP -complete,如果在多项式时间内,您可以将任何其他NP问题的任何实例转换为该问题的实例.上述权重问题是一个问题,确定布尔公式是否具有令人满意的赋值,解决整数上的某些优化问题(整数规划),确定访问一组位置的最快路径(旅行推销员)的问题),或确定如何使用最小数量的频率(图形着色)在城市中分配蜂窝塔.即使确定它是否能够解决像游戏数独和扫雷艇被称为是NP -完全任意电路板尺寸.
(有些问题具有后一种性质 - NP中的任何问题都可以有效地转化为该问题 - 但本身并不是NP.这些问题被称为NP -hard.)
从实际角度来看,如果您被要求解决已知为NP -complete或NP -hard的问题,请不要期望在任何合理的时间内找到确切的解决方案.在某些情况下,甚至不可能有效地在任何精度范围内逼近解决方案.你最好寻找一个替代问题来尝试解决或让自己适应一个在大多数但不是所有情况下表现都很好的启发式解决方案.
至于你对DFS是NP -complete的原始想法,只有问题可以在NP或NP完全 ; 算法不能.DFS是一种解决图形可达性问题的算法 - 给定图中的两个节点,是否存在从第一个到第二个的路径？这个问题出现在NP中,因为如果有一个路径很容易检查,但它(可能)不是NP -complete,因为我们知道我们可以使用DFS在多项式时间内解决它.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
3866 次 |
| 最近记录： |