《算法分析与设计课件NP完全问题.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计课件NP完全问题.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习要点学习要点学习要点学习要点 理解理解理解理解P P类与类与类与类与NPNP类语言的概念类语言的概念类语言的概念类语言的概念 理解理解理解理解NPNP完全问题的概念完全问题的概念完全问题的概念完全问题的概念 理解近似算法的性能比及多项式时间近似格式理解近似算法的性能比及多项式时间近似格式理解近似算法的性能比及多项式时间近似格式理解近似算法的性能比及多项式时间近似格式的概念的概念的概念的概念NP完全性理论与近似算法1P P类与类与类与类与NPNP类问题类问题类问题类问题n n一一一一般般般般地地地地说说说说，将将将将可可可可由由由由多多多多项项项项式式式式时时时时间间间间算算算算法法法法求求
2、求求解解解解的的的的问问问问题题题题看看看看作作作作是是是是易易易易处处处处理理理理的的的的问问问问题题题题，而将需要超多项式时间才能求解的问题看作是难处理的问题。而将需要超多项式时间才能求解的问题看作是难处理的问题。而将需要超多项式时间才能求解的问题看作是难处理的问题。而将需要超多项式时间才能求解的问题看作是难处理的问题。n n有有有有许许许许多多多多问问问问题题题题，从从从从表表表表面面面面上上上上看看看看似似似似乎乎乎乎并并并并不不不不比比比比排排排排序序序序或或或或图图图图的的的的搜搜搜搜索索索索等等等等问问问问题题题题更更更更困困困困难难难难，然然然然而而而而至至至至今今今今人人人人
3、们们们们还还还还没没没没有有有有找找找找到到到到解解解解决决决决这这这这些些些些问问问问题题题题的的的的多多多多项项项项式式式式时时时时间间间间算算算算法法法法，也也也也没没没没有有有有人人人人能够证明这些问题需要超多项式时间下界。能够证明这些问题需要超多项式时间下界。能够证明这些问题需要超多项式时间下界。能够证明这些问题需要超多项式时间下界。n n在图灵机计算模型下，这类问题的计算复杂性至今未知。在图灵机计算模型下，这类问题的计算复杂性至今未知。在图灵机计算模型下，这类问题的计算复杂性至今未知。在图灵机计算模型下，这类问题的计算复杂性至今未知。n n为为为为了了了了研研研研究究究究这这这这类
4、类类类问问问问题题题题的的的的计计计计算算算算复复复复杂杂杂杂性性性性，人人人人们们们们提提提提出出出出了了了了另另另另一一一一个个个个能能能能力力力力更更更更强强强强的的的的计计计计算算算算模模模模 型型型型，即即即即 非非非非 确确确确 定定定定 性性性性 图图图图 灵灵灵灵 机机机机 计计计计 算算算算 模模模模 型型型型，简简简简 记记记记 为为为为NDTM(Nondeterministic Turing Machine)NDTM(Nondeterministic Turing Machine)。n n在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。在非确定性图灵机计算模型
5、下，许多问题可以在多项式时间内求解。在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。2NPNPNPNP完全问题完全问题完全问题完全问题 NP NP NP NP完全问题是不确定性图灵机在完全问题是不确定性图灵机在完全问题是不确定性图灵机在完全问题是不确定性图灵机在P P P P时间内能解决的问题，时间内能解决的问题，时间内能解决的问题，时间内能解决的问题，是是是是世界七大数学难题世界七大数学难题世界七大数学难题世界七大数学难题之一。之一。之一。之一。数学上著名的数学上著名的数学上著名的数学上著名的NPNPNPNP问题，完整的
6、叫法是问题，完整的叫法是问题，完整的叫法是问题，完整的叫法是NPNPNPNP完全问题，也即完全问题，也即完全问题，也即完全问题，也即“NP COMPLETE”NP COMPLETE”NP COMPLETE”NP COMPLETE”问题，简单的写法，是问题，简单的写法，是问题，简单的写法，是问题，简单的写法，是 NP=PNP=PNP=PNP=P？的问题。的问题。的问题。的问题。问题就在这个问号上，到底是问题就在这个问号上，到底是问题就在这个问号上，到底是问题就在这个问号上，到底是NPNPNPNP等於等於等於等於P P P P，还是，还是，还是，还是NPNPNPNP不等於不等於不等於不等於P P
7、P P。也就是说，也就是说，也就是说，也就是说，NPNPNPNP问题到底是问题到底是问题到底是问题到底是PolynomialPolynomialPolynomialPolynomial（意思是多项式的）（意思是多项式的）（意思是多项式的）（意思是多项式的），还是，还是，还是，还是Non-PolynomialNon-PolynomialNon-PolynomialNon-Polynomial，尚无定论。，尚无定论。，尚无定论。，尚无定论。3 NPNPNPNP里面的里面的里面的里面的N N N N，不是，不是，不是，不是Non-PolynomialNon-PolynomialNon-Polynom
8、ialNon-Polynomial的的的的N N N N，是，是，是，是Non-Non-Non-Non-DeterministicDeterministicDeterministicDeterministic（意思是非确定性的），（意思是非确定性的），（意思是非确定性的），（意思是非确定性的），P P P P代表代表代表代表PolynomialPolynomialPolynomialPolynomial倒是对的。倒是对的。倒是对的。倒是对的。NPNPNPNP就是就是就是就是Non-deterministic PolynomialNon-deterministic PolynomialNon-d
9、eterministic PolynomialNon-deterministic Polynomial的问题，的问题，的问题，的问题，也即是多项式复杂程度的非确定性问题。也即是多项式复杂程度的非确定性问题。也即是多项式复杂程度的非确定性问题。也即是多项式复杂程度的非确定性问题。什么是非确定性问题呢？有些计算问题是确定性的，什么是非确定性问题呢？有些计算问题是确定性的，什么是非确定性问题呢？有些计算问题是确定性的，什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步比如加减乘除之类，你只要按照公式推导，按部就班一步比如加减乘除之类，你只要按照公式推导，
10、按部就班一步比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班步来，就可以得到结果。但是，有些问题是无法按部就班步来，就可以得到结果。但是，有些问题是无法按部就班步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公直接地计算出来。比如，找大质数的问题。有没有一个公直接地计算出来。比如，找大质数的问题。有没有一个公直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应式，你一套公式，就可以一步步推算出来，下一个质数应式，你一套公式，就可以一步步推算出来，
11、下一个质数应式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分该是多少呢？这样的公式是没有的。再比如，大的合数分该是多少呢？这样的公式是没有的。再比如，大的合数分该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直解质因数的问题，有没有一个公式，把合数代进去，就直解质因数的问题，有没有一个公式，把合数代进去，就直解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。接可以算出，它的因子各自是多少？也没有这样的公式。接可以算出，它的因子各自是多少？也没有
12、这样的公式。接可以算出，它的因子各自是多少？也没有这样的公式。4 这种问题的答案，是无法直接计算得到的，只能通过间这种问题的答案，是无法直接计算得到的，只能通过间这种问题的答案，是无法直接计算得到的，只能通过间这种问题的答案，是无法直接计算得到的，只能通过间接的接的接的接的“猜算猜算猜算猜算”来得到结果。这也就是非确定性问题。而这些来得到结果。这也就是非确定性问题。而这些来得到结果。这也就是非确定性问题。而这些来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可问题的通常有个算法，它不能直接告诉你答案是什么，但可问题的通常有个算法，它不能直接告诉你答案是
13、什么，但可问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个以告诉你，某个可能的结果是正确的答案还是错误的。这个以告诉你，某个可能的结果是正确的答案还是错误的。这个以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你可以告诉你可以告诉你可以告诉你“猜算猜算猜算猜算”的答案正确与否的算法，假如可以在多的答案正确与否的算法，假如可以在多的答案正确与否的算法，假如可以在多的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这项式时间内算出来，就叫做多项式非确定性问题。而如果这项式时间内算出来，就叫做多项式
14、非确定性问题。而如果这项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确个问题的所有可能答案，都是可以在多项式时间内进行正确个问题的所有可能答案，都是可以在多项式时间内进行正确个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。与否的验算的话，就叫完全多项式非确定问题。与否的验算的话，就叫完全多项式非确定问题。与否的验算的话，就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到答案，一个个完全多项式非确定性问题可以用穷举法得到答案，一个个完全多项式非确定性问题可以用穷举法得到答案，一个个
15、完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，检验下去，最终便能得到结果。但是这样算法的复杂程度，检验下去，最终便能得到结果。但是这样算法的复杂程度，检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增是指数关系，因此计算的时间随问题的复杂程度成指数的增是指数关系，因此计算的时间随问题的复杂程度成指数的增是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。长，很快便变得不可计算了。长，很快便变得不可计算了。长，很快便变得不可计算了。5 人们发现，所有的完全多项式
16、非确定性问题，都可以转换为一类叫人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定在多项式时间内计算，人
17、们於是就猜想，是否这类问题，存在一个确定在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的是著名的是著名的是著名的NP=PNP=PNP=PNP=P？的猜想。？的猜想。？的猜想。？的猜想。解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要解决这个猜想，无非两种可能，一
18、种是找到一个这样的算法，只要解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定针对某个特定针对某个特定针对某个特定NPNPNPNP完全问题找到一个算法，所有这类问题都可以迎刃而解完全问题找到一个算法，所有这类问题都可以迎刃而解完全问题找到一个算法，所有这类问题都可以迎刃而解完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在
19、的。那么就要从数学理论上证明它为什么不存在。法是不存在的。那么就要从数学理论上证明它为什么不存在。法是不存在的。那么就要从数学理论上证明它为什么不存在。法是不存在的。那么就要从数学理论上证明它为什么不存在。6 对对对对P P P P类，类，类，类，NPNPNPNP类及类及类及类及NPNPNPNP完全问题的研究推动完全问题的研究推动完全问题的研究推动完全问题的研究推动 了计算复杂性理了计算复杂性理了计算复杂性理了计算复杂性理论的发展，产生了许多新概念，提出了许多新方法。但是论的发展，产生了许多新概念，提出了许多新方法。但是论的发展，产生了许多新概念，提出了许多新方法。但是论的发展，产生了许多新概
20、念，提出了许多新方法。但是还有许多难题至今没有解决，还有许多难题至今没有解决，还有许多难题至今没有解决，还有许多难题至今没有解决，P=NP?P=NP?P=NP?P=NP?就是其中之一。许多就是其中之一。许多就是其中之一。许多就是其中之一。许多学者猜想学者猜想学者猜想学者猜想PNPPNPPNPPNP，但无法证明。，但无法证明。，但无法证明。，但无法证明。7非确定性图灵机非确定性图灵机 非确定性图灵机（非确定性图灵机（NDTMNDTM ）：一个）：一个k k带的非确定性图灵机带的非确定性图灵机M M是一个是一个7 7元组：元组：(Q Q，T T，I I，b b，q q0 0，q qf f)。与确定
21、性图灵机不与确定性图灵机不同的是非确定性图灵机允许移动函数同的是非确定性图灵机允许移动函数具有不确定性，即对于具有不确定性，即对于Q Q T Tk k中的每一个值中的每一个值(q;xq;x1 1,x,x2 2,x,xk k)，当它属于当它属于的定义域时，的定义域时，Q Q(T(T LL，R R，S)S)k k中有唯一的一个子集中有唯一的一个子集(q;x(q;x1 1,x,x2 2,x,xk k)与之对应。与之对应。可以在可以在(q;x(q;x1 1,x,x2 2,x,xk k)中随意选定一个值作为它的函数值。中随意选定一个值作为它的函数值。在图灵机计算模型中，移动函数在图灵机计算模型中，移动函
22、数是单值的，即对于是单值的，即对于Q Q T Tk k中的每一个值，当它属于中的每一个值，当它属于的定义域时，的定义域时，Q Q(T(T LL，R R，S)S)k k中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为记为DTM(Deterministic Turing Machine)DTM(Deterministic Turing Machine)。8 P P类与类与NPNP类语言类语言 P P类和类和NPNP类语言的定义：类语言的定义：P=L|L P=L|L是一个能在多项式时间内被一台是一个能在多项式时间内被一台DTMDTM所接
23、受的语言所接受的语言 NP=L|L NP=L|L是一个能在多项式时间内被一台是一个能在多项式时间内被一台NDTMNDTM所接受的语言所接受的语言 由于一台确定性图灵机可看作是非确定性图灵机的特例，由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故多项式时间内被非确定性图灵机接受。故P P NP NP。9 NPNP类语言举例类语言举例无向图的团问题无向图的团问题。该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全
24、子完全子图图(团团)，即判定是否存在VV，|V|=k，且对于所有的u，vV，有(u，v)E。若用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可以用长度为 的二进位串表示。因此，团问题可表示为语言：CLIQUE=w#v|w，v0，1*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。10 接受该语言接受该语言CLIQUECLIQUE的非确定性算法：用非确定性选择指令选的非确定性算法：用非确定性选择指令选出包含出包含k k个顶点的候选顶点子集个顶点的候选顶点子集V V，然后确定性地检查该子集是否然后确定性地检查该子集是否是团问题的一个解。算法分为是团问题的一个解。算法分
25、为3 3个阶段：个阶段：算法的第一阶段将输入串算法的第一阶段将输入串w#vw#v分解，并计算出分解，并计算出n=n=，以及以及用用v v表示的整数表示的整数k k。若输入不具有形式若输入不具有形式w#vw#v或或|w|w|不是一个平方数就不是一个平方数就拒绝该输入。显而易见，第一阶段可拒绝该输入。显而易见，第一阶段可 在时间内完成。在时间内完成。在算法的第二阶段中，非确定性地选择在算法的第二阶段中，非确定性地选择V V的一个的一个k k元子集元子集VV V V。算法的第三阶段是确定性地检查算法的第三阶段是确定性地检查VV的团性质。若的团性质。若VV是一个是一个团则接受输入，否则拒绝输入。这显然
26、可以在团则接受输入，否则拒绝输入。这显然可以在 时间内完成。时间内完成。因此，整个算法的时间复杂性为因此，整个算法的时间复杂性为 。非确定性算法在多项式时间内接受语言非确定性算法在多项式时间内接受语言CLIQUECLIQUE，故故CLIQUENPCLIQUENP。11多项式时间验证多项式时间验证 VP=L|L*VP=L|L*，为一有限字符集，存在一个多项式为一有限字符集，存在一个多项式p p和一和一个多项式时间验证算法个多项式时间验证算法A(XA(X，Y)Y)使得对任意使得对任意X*X*，XLXL当且仅当且仅当存在当存在Y*Y*，|Y|p(|X|)|Y|p(|X|)且且A(XA(X，Y)=1Y
27、)=1。多项式时间可验证语言类多项式时间可验证语言类VPVP可定义为：可定义为：定理定理9-19-1：VP=NPVP=NP。例如例如(哈密顿回路问题哈密顿回路问题)：一个无向图：一个无向图G G含有哈密顿回路吗含有哈密顿回路吗?无无向向图图G G的的哈哈密密顿顿回回路路是是通通过过G G的的每每个个顶顶点点恰恰好好一一次次的的简简单单回回路。可用语言路。可用语言HAM-CYCLE HAM-CYCLE 定义该问题如下：定义该问题如下：HAM-CYCLE=G|GHAM-CYCLE=G|G含有哈密顿回路含有哈密顿回路 12NP完全问题n nP P NPNP。n n直直观观上上看看，P P类类问问题题
28、是是确确定定性性计计算算模模型型下下的的易易解解问问题题类类，而而NPNP类类问问题题是是非非确确定性计算模型下的易验证问题类。定性计算模型下的易验证问题类。n n大多数的计算机科学家认为大多数的计算机科学家认为NPNP类中包含了不属于类中包含了不属于P P类的语言，即类的语言，即PNPPNP。n nNPNP完完全全问问题题有有一一种种令令人人惊惊奇奇的的性性质质，即即如如果果一一个个NPNP完完全全问问题题能能在在多多项项式式时时间间内得到解决，那么内得到解决，那么NPNP中的每一个问题都可以在多项式时间内求解，即中的每一个问题都可以在多项式时间内求解，即P=NPP=NP。n n目前还没有一
29、个目前还没有一个NPNP完全问题有多项式时间算法。完全问题有多项式时间算法。13多项式时间变换多项式时间变换 定义：语言定义：语言L L是是NPNP完全的当且仅当完全的当且仅当 (1)(1)LNPLNP；(2)(2)对于所有对于所有LNPLNP有有L L p p L L。如果有一个语言如果有一个语言L L满足上述性质满足上述性质(2)(2)，但不一定满足性质，但不一定满足性质(1)(1)，则称该语言是，则称该语言是NPNP难的。所有难的。所有NPNP完全语言构成的语言类称为完全语言构成的语言类称为NPNP完全语言类，记为完全语言类，记为NPCNPC。设设 ，是是2 2个语言。所谓语言个语言。所
30、谓语言 能在多项式能在多项式时间内变换为语言时间内变换为语言 (简记为简记为 p p )是指存在映身是指存在映身f:f:，且且f f满足：满足：(1)(1)有一个计算有一个计算f f的多项式时间确定性图灵机；的多项式时间确定性图灵机；(2)(2)对于所有对于所有x x ，x x ，当且仅当当且仅当f(x)f(x)。14多项式时间变换 定理定理9-29-2：设L是NP完全的，则 (1)LP当且仅当PNP；(2)若Lp ，且 NP，则 是NP完全的。定理的定理的(2)(2)可用来可用来证明问题的证明问题的NPNP完全完全性。但前提是：要性。但前提是：要有第一个有第一个NPNP完全问完全问题题L L
31、。15一些典型的NP完全问题部分NP完全问题树16 迄今为止，所有的迄今为止，所有的NPNP完全问题都还没有多项式时间算法。完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。对于这类问题，通常可采取以下几种解题策略。(1)(1)只对问题的特殊实例求解只对问题的特殊实例求解(2)(2)用动态规划法或分支限界法求解用动态规划法或分支限界法求解 (3)(3)用概率算法求解用概率算法求解 (4)(4)只求近似解只求近似解(5)(5)用启发式方法求解用启发式方法求解 NP完全问题的近似算法完全问题的近似算法17近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算
32、法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比近似算法的性能比定义为=。在通常情况下，该性能比是问题输入规模n的一个函数(n)，即 (n)。该近似算法的相对误差近似算法的相对误差定义为=。若对问题的输入规模n，有一函数(n)使得 (n)，则称(n)为该近似算法的相对误差界近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系：(n)(n)-1(n)(n)-1。18 顶点覆盖问题的近似算法顶点覆盖问题的近似算法 问题描述：无向图问题描述：无向图G=(V,E)G=(V,E)的顶点覆盖是它的顶点集的顶点覆盖是它的顶点集V V的一个子集的一个子集VV V V，
33、使得若使得若(u,v)u,v)是是G G的一条边，则的一条边，则vVvV或或uVuV。顶点覆盖顶点覆盖VV的大小是它所包含的顶点个数的大小是它所包含的顶点个数|V|V|。VertexSet approxVertexCover(Graph g)VertexSet approxVertexCover(Graph g)cset=cset=；e1=g.e e1=g.e；while(e1!=while(e1!=)从从e1e1中任取一条边中任取一条边(u,v)u,v)；cset=csetu,v cset=csetu,v；从从e1e1中删去与中删去与u u和和v v相关联的所有边；相关联的所有边；retur
34、n creturn c Cset Cset用来存储顶点用来存储顶点覆盖中的各顶点。初覆盖中的各顶点。初始为空，不断从边集始为空，不断从边集e1e1中选取一边中选取一边(u,v)u,v)，将边的端点加入将边的端点加入csetcset中，并将中，并将e1e1中已中已被被u u和和v v覆盖的边删去，覆盖的边删去，直至直至csetcset已覆盖所有已覆盖所有边。即边。即e1e1为空。为空。19顶点覆盖问题的近似算法 图图(a)a)(e)(e)说明说明了算法的运行过程了算法的运行过程及结果。及结果。(e)e)表示表示算法产生的近似最算法产生的近似最优顶点覆盖优顶点覆盖csetcset，它由顶点它由顶点
35、b,c,d,e,f,gb,c,d,e,f,g所组所组成。成。(f)f)是图是图G G的一的一个最小顶点覆盖，个最小顶点覆盖，它只含有它只含有3 3个顶点：个顶点：b,db,d和和e e。算法approxVertexCoverapproxVertexCover的性能比为2。20旅行售货员问题近似算法旅行售货员问题近似算法 问题描述：给定一个完全无向图问题描述：给定一个完全无向图G=(V,E)G=(V,E)，其每一边其每一边(u,v)Eu,v)E有一非负整数费用有一非负整数费用c(u,v)c(u,v)。要找出要找出G G的最小费用的最小费用哈密顿回路。哈密顿回路。比如，费用函数比如，费用函数c c
36、往往具有三角不等式性质，即对往往具有三角不等式性质，即对任意的任意的3 3个顶点个顶点u,v,wVu,v,wV，有：有：c(u,w)c(u,v)+c(v,w)c(u,w)c(u,v)+c(v,w)。当图当图G G中的顶点就是平面上的点，任意中的顶点就是平面上的点，任意2 2顶点间的费用就顶点间的费用就是这是这2 2点间的欧氏距离时，费用函数点间的欧氏距离时，费用函数c c就具有三角不等式就具有三角不等式性质。性质。旅行售货员问题的一些特殊性质：旅行售货员问题的一些特殊性质：211 1 满足三角不等式的旅行售货员问题满足三角不等式的旅行售货员问题满足三角不等式的旅行售货员问题满足三角不等式的旅行
37、售货员问题 对于给定的无向图对于给定的无向图G G，可以利用找图可以利用找图G G的最小生成树的的最小生成树的算法设计找近似最优的旅行售货员回路的算法。算法设计找近似最优的旅行售货员回路的算法。void approxTSP(Graph g)void approxTSP(Graph g)(1)(1)选择选择g g的任一顶点的任一顶点r r；(2)(2)用用PrimPrim算法找出带权图算法找出带权图g g的一棵以的一棵以r r为根的最小生成树为根的最小生成树T T；(3)(3)前序遍历树前序遍历树T T得到的顶点表得到的顶点表L L；(4)(4)将将r r加加到到表表L L的的末末尾尾，按按表表
38、L L中中顶顶点点次次序序组组成成回回路路H H，作作为为计计算结果返回；算结果返回；当费用函数满足三角不等式时，算法找出的旅行售货员回路当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的的费用不会超过最优旅行售货员回路费用的2 2倍。倍。22(b)b)表示找到的最小生成表示找到的最小生成树树T T；(c)c)表示对表示对T T作前序作前序遍历的次序；遍历的次序；(d)(d)表示表示L L产产生的哈密顿回路生的哈密顿回路H H；(e)(e)是是G G的一个最小费用旅的一个最小费用旅行售货员回路。行售货员回路。232 2 一般一般一般一般的的的的旅行售货员
39、问题旅行售货员问题旅行售货员问题旅行售货员问题 在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NPP=NP。换句话说，若PNP，则对任意常数1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。24集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题的近似算法 问题描述：给定一个完全无向图问题描述：给定一个完全无向图G=(V,E)G=(V,E)，其每一边其每一边(u,v)Eu,v)E有一非负整数费用有一非负整数费用c(u,v)c(u,v)。要找出要找出G G的最小费用的最小费用哈密顿回路。哈密顿回路。集
40、合覆盖问题的一个实例集合覆盖问题的一个实例X,FX,F由一个有限集由一个有限集X X及及X X的一个子集族的一个子集族F F组成。子集族组成。子集族F F覆盖了有限集覆盖了有限集X X。也就是说也就是说X X中每一元素至少属于中每一元素至少属于F F中的一个子集，即中的一个子集，即X=X=。对于。对于F F中中的一个子集的一个子集C C F F，若若C C中的中的X X的子集覆盖了的子集覆盖了X X，即即X=X=，则，则称称C C覆盖了覆盖了X X。集合覆盖问题就是要找出集合覆盖问题就是要找出F F中覆盖中覆盖X X的最小子的最小子集集C C*，使得使得|C C*|=min|C|C|=min|
41、C|C F F且且C C覆盖覆盖X X 25集合覆盖问题举例：用用1212个黑点表示集个黑点表示集合合X X。F=S1,S2,S3,S4,SF=S1,S2,S3,S4,S5,S6,5,S6,，如图所示。如图所示。容易看出，对于这容易看出，对于这个例子，最小集合个例子，最小集合覆盖为：覆盖为：C=S3,S4,S5,C=S3,S4,S5,。26集合覆盖问题的近似算法集合覆盖问题的近似算法集合覆盖问题近似算法贪心算法 算法的循环体最多算法的循环体最多执行执行min|X|min|X|，|F|F|次。次。而循环体内的计算显然而循环体内的计算显然可在可在O(|X|F|)O(|X|F|)时间内完时间内完成。
42、因此，算法的计算成。因此，算法的计算时间为时间为O(|X|F|min|X|O(|X|F|min|X|，|F|)|F|)。由此即知，该由此即知，该算法是一个多项式时间算法是一个多项式时间算法。算法。Set greedySetCover(X,F)Set greedySetCover(X,F)U=X U=X；C=C=；while(U!=while(U!=)选择选择F F中使中使|SU|SU|最大的子集最大的子集S S；U=U-S U=U-S；C=CS C=CS；return C return C；27子集和问题的近似算法子集和问题的近似算法 问题描述：设子集和问题的一个实例为问题描述：设子集和问题的
43、一个实例为S,tS,t。其中，其中，S=xS=x1 1，x x2 2，x xn n 是一个正整数的集合，是一个正整数的集合，t t是是一个正整数。子集和问题判定是否存在一个正整数。子集和问题判定是否存在S S的一个子集的一个子集S1S1，使得使得 。28int exactSubsetSum(S,t)int exactSubsetSum(S,t)int n=|S|int n=|S|；L0=0 L0=0；for(int i=1 for(int i=1；i=ni=n；i+)i+)Li=mergeLists(Li-1,Li-1+Si)Li=mergeLists(Li-1,Li-1+Si)；删去删去Li
44、Li中超过中超过t t的元素；的元素；return max(Ln)return max(Ln)；算法以集合算法以集合S=xS=x1 1，x x2 2，x xn n 和目标值和目标值t t作为输入。算法中作为输入。算法中用到将用到将2 2个有序表个有序表L1L1和和L2L2合并成为一个新合并成为一个新的有序表的算法的有序表的算法mergeLists(L1,L2)mergeLists(L1,L2)。292 2 子集和问题的完全多项式时间近似格式子集和问题的完全多项式时间近似格式子集和问题的完全多项式时间近似格式子集和问题的完全多项式时间近似格式 基于算法基于算法exactSubsetSumexac
45、tSubsetSum，通过对表通过对表LiLi作适当的修整建立一个子集作适当的修整建立一个子集和问题的完全多项式时间近似格式。和问题的完全多项式时间近似格式。在对表在对表LiLi进行修整时，用到一个修整参数进行修整时，用到一个修整参数，0 01 1。用参数用参数修整一个表修整一个表L L是指从是指从L L中删去尽可能多的元素，使得每一个从中删去尽可能多的元素，使得每一个从L L中删去的元素中删去的元素y y，都有一个修整后的表都有一个修整后的表L1L1中的元素中的元素z z满足满足(1-(1-)yzy)yzy。可以将可以将z z看作是看作是被删去元素被删去元素y y在修整后的新表在修整后的新表
46、L1L1中的代表。中的代表。举例：若举例：若=0.1=0.1，且且L=L=10,11,12,15,20,21,22,23,24,2910,11,12,15,20,21,22,23,24,29，则用则用对对L L进行修整后得到进行修整后得到L1=L1=1010，1212，1515，2020，2323，2929。其中被删去的数其中被删去的数1111由由1010来代表，来代表，2121和和2222由由2020来代表，来代表，2424由由2323来代表。来代表。302 2 子集和问题的完全多项式时间近似格式子集和问题的完全多项式时间近似格式子集和问题的完全多项式时间近似格式子集和问题的完全多项式时间近
47、似格式对有序表对有序表L L修整算法修整算法List trim(L,List trim(L,)int m=|L|int m=|L|；L1=L1=L1L1；int last=L1 int last=L1；for(int i=2 for(int i=2；i=mi=m；i+)i+)if(last(1-if(last(1-)*Li)*Li)将将LiLi加入表加入表L1L1的尾部；的尾部；last=Lilast=Li；return L1 return L1；子集和问题近似格式子集和问题近似格式int approxSubsetSum(S,t,int approxSubsetSum(S,t,)n=|S|n=|S|；L0=L0=0 0；for(int i=1 for(int i=1；i=ni=n；i+)i+)Li=Merge-Lists(Li-1,Li=Merge-Lists(Li-1,Li-1+Si)Li-1+Si)；Li=Trim(Li,Li=Trim(Li,/n)/n)；删去删去LiLi中超过中超过t t的元素；的元素；return max(Ln)return max(Ln)；31