我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿主页 > 调度信息池 >

为什么节能调度算法一般都是np-hard问题

归档日期:05-02       文本归类:调度信息池      文章编辑:爱尚语录

  长期从事计算机组装,维护,网络组建及管理。对计算机硬件、操作系统安装、典型网络设备具有详细认知。

  在计算机学科中,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题、推销员旅行问题、(命题表达式)可满足问题这类,至今没有找到多项式时间算法解的一类问题,称之为NP类问题。

  多项式时间(Polynomial time)在计算复杂度理论中,指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类,此类包括可于此机器以多项式时间求解的问题。

  以数学描述的话,则可说m(n) = O(n),此n为一常数值(依问题而定)

  拿推销员旅行问题为例,假设推销员亨利有向6个城市推销公司产品的任务,并规定了一个旅行预算。他手中有一张航班票价表,他要从A城开始走遍图中的6个城市后返回A城,并且不超出预算,请你帮他找出应走的路线。如果给出的预算宽裕,则任务很简单;如果预算比较紧张,你就得认真设计路线了。你得考虑每一种可能的次序,以使旅费最少。

  而NP问题中最困难的问题称之为NP完全问题(NP-complete),已经证明的包括:电话网络的最优几何设计、格子棋的最佳走法。根据库克定理,任意一个NP完全问题如果能够在多项式时间内解决,则所有的NP问题都能在多项式时间内解决,而至今这一问题仍无答案。

  什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。

  这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间(多项式时间: 运行时间最多是输入量的多项式函数)内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。

  完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在一个确定性算法,可以在指数时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。

  解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。

  前段时间轰动世界的一个数学成果,是几个印度人提出了一个新算法,可以在多项式时间内,证明某个数是或者不是质数,而在这之前,人们认为质数的证明,是个非多项式问题。可见,有些看来好象是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已。

  首先说明一下问题的复杂性和算法的复杂性的区别,下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间,这是算法的性质;问题的复杂性是指这个问题本身的复杂程度,是问题的性质。比如对于排序问题,如果我们只能通过元素间的相互比较来确定元素间的相互位置,而没有其他的附加可用信息,则排序问题的复杂性是O(nlgn),但是排序算法有很多,冒泡法是O(n^2),快速排序平均情况下是O(nlgn)等等,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到,一般都是预先估计一个值,然后从理论上证明。

  为了研究问题的复杂性,我们必须将问题抽象,为了简化问题,我们只考虑一类简单的问题,判定性问题,即提出一个问题,只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题,比如求图中从A到B的最短路径,可以转化成:从A到B是否有长度为1的路径?从A到B是否有长度为2的路径?。。。从A到B是否有长度为k的路径?如果问到了k的时候回答了yes,则停止发问,我们可以说从A到B的最短路径就是k。

本文链接:http://i-zyczenia.net/diaoduxinxichi/163.html

上一篇:能打电话提前预约

下一篇:没有了