计算机算法基础 第2版 课件 第14章 NP-完全问题.pptx

1第14章NP-完全问题序言 2预备知识 4P和NP语言类 20NPC语言类和NPC问题 29第一个NPC问题 32若干著名NPC问题的证明 43

1.序言2有些看似容易的问题找不到多项式算法。例如，在图中找一条两点间最长的简单路径。不论k多大，都找不到O(nk)的算法。这引起人们对问题本身固有的难易程度的探讨兴趣，也是这一章讨论的课题。问题分类。有多项式算法的问题称为可驾驭的(tractable)问题，或称为容易问题，否则称为不可驾驭的(intractable)问题，或难问题。NP完全问题(NP-complete问题，简称NPC问题)简单说，是至今还无法判断属于容易问题，还是难问题的一类问题。为了理解NPC问题，我们将先介绍P类和NP类问题。

3P类问题有多项式算法的问题属于P类。也可认为，在一个确定的图灵机上有多项式算法。(后面会定义图灵机)NP类问题在非确定的图灵机上有多项式算法的问题属于NP类。许多难以判断的问题都属于这一类，例如哈密尔顿回路问题、最小顶点复盖问题、图的三着色问题等。NPC类问题NPC类是NP类中最困难的问题，NPC?NP。如果NPC中有一个有多项式算法，那么所有NP问题都有多项式算法。反之，如有一个没有多项式算法，那么所有NPC问题都没有多项式算法。P?NP猜想已证明P?NP，猜想P?NPC=?，即P?NP，但至今未能证明。

4图灵机图灵机TM，通常指确定的图灵机(DeterministicTuringMachine)，是一个简单的计算模型。10B101BB??????有限状态控制器(q,a)?(q’,a’,D)2.预备知识由一个有限状态控制器和一条右端无限长的读写带组成。读写带从左到右划分为无限多个连续的方格，每个方格可存放字符集?中的一个符号。空白的格子由特殊符号B表示。Q是个有限个状态的集合。有限状态控制器在任一时刻处于Q中的一个状态q并控制读写头的读写操作。一开始在初始状态q0。(接下页)

5如果有限状态控制器当前的状态是q?Q，其读写头正在扫描的字符是a??，那么，有限状态控制器做三件事：更改下一时刻的状态为q’更新所扫描的字符为a’决定读写头向左(L)移动一个方格，或向右(R)移动一个方格，或停留不动(N)。上述三件事都是确定好的，可以表示为(q,a)?(q’,a’,D)，或者?(q,a)=(q’,a’,D)，这里D可以是L，R，或者N。?称为状态转换函数，允许q’=q和a’=a。因为集合Q和?都是有限集合，?(q,a)转換函数可以用一个有限长的表格表示。集合Q有子集F?Q，子集F中的状态称为终止状态。第13章的有限状态自动机是图灵机的特殊情况。它不改变读写带上的字符，没有输出值，停机在接收状态表示接收输入字符串。

6图灵机计算一个函数或识别一个字符串的过程开始时，输入数据或字符串从左边第一个方格开始放在读写带上，图灵机处在开始状态q0，而读写头指向第一个方格。·然后，根据转換函数不断地变更状态、修改符号、和移动读写头。当进入了一个终止状态qf?F时，计算停止。这时，在带子上的字符串或在某些指定格子上符号就是输出的函数值。如果用来识别一个字符串，可以输出一个特定符号(比如1)表示接收这个字符串，输出另一特定符号(比如0)表示拒绝这个字符串。图灵机有可能永远不能进入终止状态，这时我们说函数对输入数据无定义或者说图灵机对输入字符串不能判定。图灵机的计算复杂度定义为其状态转换的次数T(n)，这里n是输入字符串的长度，并且只对停机的情况才考虑复杂度。

7符号集和编码对计算复杂度的影响用不同的符号集合会影响输入规模的大小。比如整数98，用十进制，只要两个符号9和8表示；如果用2进制，98=则需要7个符号表示；如果用1进制，则需要98个0表示。设某图灵机T使用的符号集是?，|?|=d，d?2。现在假设有另一个图灵机T’，它做一次状态转换所需时间与T相同，但字符集?’与?不同，|?’|?2。我们可用?’中两字符a和b(可视为0和1)来对?中每个字符编码，长为k=?lgd?。这样一来，对?中一个字符的操作变成了对一个长为k的序列的操作。因为d和k都是常数，图灵机T’的渐近复杂度与T的相同。所以，除一进制的编码外，用不同的符号集不影响算法的复杂度。为方便起见，以下讨论中，我们就假定?={0,1}。

8判断型问题和优化型问题及其关系如果一个问题的答案只有两种，是(yes)或不是(no)，则称为一个判断型问题。例如，判断一个图是否有一条哈密尔顿回路就是一个判断型问题。一个问题被称为优化