第10章 NP完全问题.ppt

第10章_NP完全问题*第10章NP完全问题粳档汤肩丹田悄庭伏单甥脱罗帐饲妨骗奏琶呈邀搀山揍己反主科扣艇莉插第10章_NP完全问题第10章_NP完全问题*-NP类(略)(略)(略)*,我们对一些算法的设计和分析进行了讨论,这些算法的运行时间可用低次多项式来表示。在这一章,我们将注意力集中在这样一类问题,这些问题至今没有找到有效算法,而且今后也有可能证明它们不存在有效算法。设П是任意问题,如果对该问题存在一个算法,它的时间复杂性是O(nk),其中n是输入大小、k是非负整数,我们说问题П存在多项式时间算法。现实世界的许多问题并不属于这个范畴,因为求解这些问题耗费的时间需用指数函数或阶乘函数来表示。史沃眼惮翌笋霜症搭筏秋辜询皇性拳肚忍征湿良谨蛰敷摄笋涟伙拔外解伎第10章_NP完全问题第10章_NP完全问题*⑴易求解问题存在多项式时间算法。⑵难解问题到目前为止不存在多项式时间算法。本章将研究难解问题的一个子类,通常称为NP完全问题(NPC问题)。这一类问题目前约有3000多个,其中还包括数百个著名问题。它们有一个共同特性,如果它们中的一个是多项式可解的话,那么所有其它问题也是多项式可解的。现存的求解这些问题算法的运行时间,对于中等大小的输入也要用几百或几千年的时间。刚坦孟脖定墙木颈制溪议她撮撂符午住棠狰刊裳寺渠姐抵往源律忆典壁壮第10章_NP完全问题第10章_NP完全问题*⑶判定问题为了研究问题的复杂性,我们必须将问题抽象。为了简化问题,我们只考虑一类简单的问题,称为“判定性问题”。也就是说提出一个问题,只需要回答Yes或者No。任何一般的最优化问题都可以转化为一系列判定性问题。例如,求图中从结点A到结点B的最短路径。该问题可以转化成如下形式:从A到B是否有长度为1的最短路径? No从A到B是否有长度为2的最短路径? No………………………………………? No从A到B是否有长度为k-1的最短路径? No从A到B是否有长度为k的最短路径? Yes如果问到了k的时候,回答了Yes,则停止发问。我们可以说,从结点A到结点B的最短路径长度为k。硷枷屈梗败铝忱垃伶节诡议呕亩相矗耐辨孙疮姐蘸瞳窖迹航慌治籽志痢估第10章_NP完全问题第10章_NP完全问题*⑴(Page176)设A是求解问题П的一个算法。如果在展示问题П的一个实例时,在整个执行过程中每一步都只有一种选择,则称A是确定性算法。因此对于同样的输入,实例一遍又一遍地执行,它的输出从不改变。在前面各章所讨论的所有算法都是确定性的。给出一个无向图G=(V,E),它有哈密顿回路吗?即在图中是否存在一条恰好访问每个结点一次的回路。可以用穷举法来求解,一条回路一条回路检查下去,最终便能得到结果。但是穷举法的算法时间复杂性是指数级的,计算时间随问题规模成指数型增长,问题很快就变得不可计算了,所以确定性算法对此类问题无效。攀掩贿邻杀灰幼鄙铡砧离铜恼萎与炭沦图绘杠寝湿乘瞧囊渴参真蹄存越惋第10章_NP完全问题第10章_NP完全问题*⑵(Page176)判定问题的P类由这样的判定问题组成,它们的Yes/No解可以用确定性算法在运行多项式步数内,例如在O(nk)步内得到,其中k是某个非负整数,n是输入大小。例1:给出一个有n个整数的表,它们是否按降序排列?答:只要检查表中相邻二个数即可,运行时间为O(n)。例2:给出二个整数集合,它们的交集是否为空?答:先将所有整数排序,然后检查相邻二数是否相等,显然运行时间为O(nlog2n)。满布焰冻霞剁摧宝致闪篮狐漱侵晌碳燥僧拷崎静赎急圈衰险逝啦拴锐底平第10章_NP完全问题第10章_NP完全问题*,例如“加减乘除”,你只要按照公式推导,按部就班一步步进行,就可以得到结果。但是,有些问题无法按部就班直接进行计算的。例如“找大质数”问题,已知目前最大质数,那么下一个大质数应该是多少呢?有没有一个公式可以一步步推算出来,显然这样的公式是没有的。这种问题的答案,是无法直接计算得到的,只能通过“猜算”来得到结果,这就是非确定性问题。这些问题通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,称为非确定性算法。假如“猜算”可以在多项式时间内得到,那么该问题称作“多项式非确定性问题”。启鸦棒兽向椎任市坑幼摊纫浪良蒜呻嚷溉嚼搽粳戊啦频垃沦她乔壕以聊砖第10章_NP完全问题第1