注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Search的博客

不断学习中!

 
 
 

日志

 
 

【引用】NP-hard问题  

2012-06-05 12:15:20|  分类: 算法分析 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自bjutqkleng《NP-hard问题》

    NP是指非确定性多项式(non-deterministic polynomial,缩写NP)。所谓的非确定性是指,可用一定数量的运算去解决多项式时间内可解决的问题。NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题,这里“很容易检查”指的是存在一个多项式检查算法。相应的,若NP中所有问题到某一个问题是图灵可归约的,则该问题为NP困难问题。
    例如,著名的推销员旅行问题(Travel Saleman Problem or TSP):假设一个推销员需要从香港出发,经过广州,北京,上海,…,等 n 个城市, 最后返回香港。 任意两个城市之间都有飞机直达,但票价不等。现在假设公司只给报销 C 元钱,问是否存在一个行程安排,使得他能遍历所有城市,而且总的路费小于 C?   
    推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排,可以很容易算出旅行总开销。但是,要想知道一条总路费小于 C 的行程是否存在,在最坏情况下,必须检查所有可能的旅行安排! 这将是个天文数字。   
    旅行推销员问题是数图论中最著名的问题之一,即“已给一个n个点的完全图,每条边都有一个长度,求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds,Cook和Karp等人发现,这批难题有一个值得注意的性质,对其中一个问题存在有效算法时,每个问题都会有有效算法。   
    迄今为止,这类问题中没有一个找到有效算法。目前倾向于接受NP完全问题(NP-Complet或NPC)和NP难题(NP-Hard或NPH)不存在有效算法这一猜想,认为这类问题的大型实例不能用精确算法求解,必须寻求这类问题的有效的近似算法。
    以上内容摘自百度百科:http://baike.baidu.com/view/3408158.htm
=====================================================================
    NP问题的全称是:Non deterministic Ploynomial问题,即非确定性多项式问题。
    多项式时间(Polynomial time)在计算复杂度理论中,指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。
    什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题。
    NP问题就是非确定性的多项式问题,也就是说,可以在多项式时间内验证一个解是否正确的问题是NP问题。P问题是能在多项式时间内求出其解的问题,所有的P问题都是NP问题,但是是否P=NP,目前还没有被证明。
    不是所有的NP问题都是难解的问题,比如数组排序的问题就是P类问题,但是P属于NP问题,所它也是NP问题,但是他并不难解。NP困难问题:对于一个判定问题A,如果所有的NP问题都可以多项式时间规约到A,那么这个问题就是NP困难问题。NPC问题:对于一个NP问题A,如果所有的NP问题都可以多项式时间规约到A,那么这个问题就是NP困难问题。NPC,也成NP完全问题,它是NP问题的一个子类,比如哈密尔顿回路问题就是NPC问题。它是这样描述的,给定N个顶点,以及任意两个顶点之间的距离,求出一条回路,使其经过每个顶点,且回路的总距离最短。这个问题可以通过枚举求出解,但是他的时间复杂度是(N-1)!,随着N的增大,要计算解是不可能的。
    NPC有一种性质,那就是如果能证明NPC问题可以再多项式时间内求出其解,则所有的NP都可以在多项式时间内求解了,即P=NP成立。所以,我们一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算法(如果存在则所有的NP问题都存在多项式时间算法,这太不可思议了,但是也不是不可能)。
   NP完全问题的证明:要证明一个判定问题是NP完全的,只要在NP完全类中找到一个问题A,将这个问题归约到待证明问题即可.要证明问题是NP完全是很困难的,因为很多问题之间的转化过程是很难想到的.第一个被证明的NP完全问题是可满足性问题,它是判定一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中,我们都可以用这个问题来归约,这里不再详述.
    以上内容摘自:http://blog.csdn.net/zxj1988/article/details/6275458
=====================================================================
    另外,关于NP-hard问题,提供一个链接,可能也会有所帮助。
    http://zhiqiang.org/blog/science/computer-science/np-hard.html

  评论这张
 
阅读(102)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017