《第九章NP问题》由会员分享，可在线阅读，更多相关《第九章NP问题（30页珍藏版）》请在金锄头文库上搜索。
1、205第九章 NP-完全问题1 关于问题及算法的描述为了应用算法复杂性理论，首先要对问题、问题的一般描述、计算模型、算法、算法的复杂性给出严格的定义。但在给出精确定义之前，我们先回顾一下有关概念的粗略解释。所谓一个问题(problem)是指一个有待回答、通常含有几个取值还未确定的自由变量的一个一般性提问(question)。它由两部分构成：一是对其关于参数的一般性描述；二是对该问题的答案所应满足的某些特性的说明。而一个问题的某个实例则可通过指定问题中所有参数的具体取值来得到。以下用表示某个问题，用表示其实例。旅行商问题的参数是由所需访问城市的一个有限集合和中每对城市之间的距离所组成。它的一个解
2、是对所给城市的一个排序 使得该排序极小化下面表达式（目标函数）的值 旅行商问题的一个实例是通过指定城市的数目，并指定每两个城市之间的具体距离而得到的。例如：，就是旅行商问题的一个实例，这个实例的一个解是排序，因为四个城市的这个排序所对应旅行路线是所有可能环游路线中长度最小的，其长度为27。目前广泛采用的描述问题的方法主要有两种：一是将任一问题转化为所谓的可行性检验问题(feasibility problem)；二是把问题转化为判定问题(decision problem)。实际中几乎所有问题都可直接或间接地转述为判定问题。判定问题是答案只有“是”与“非”两种可能的问题。一个判定问题可简单地由其所
3、有例子的集合与答案为是的例子所构成的子集来刻画。不过，为了反映实际问题所具有的特性，通常所采用的描述方法由两部分组成。第一部分用诸如集合、图、函数等各种描述分量来刻画判定问题的一般性例子，以下用“例”表示这一部分；第二部分则陈述基于一般性例子所提出的一个“是非”提问，以下简称“问”。因此，一个具体例子属于当且仅当它可通过用具有特定性质的某些对象替代一般性例子的所有一般性描述分量而得到，而一个例子属于当且仅当限定于该例子时，它对所述提问的回答为“是”。例 待访问城市的有限集合、每对城市之间的距离以及一个界。问 在中存在一个总长不超过的、通过所有城市的旅行路线吗？也就是说，存在的一个排序，使得 这
4、是一个将优化问题转化成判定问题的例子。一般地，一个优化问题可以看作是其所有实例的集合，而每一个实例为一个元素对，其中是可行解集，是目标函数。一个最优化问题可以提出下述三种模式： 最优化模式：求最优解； 求值模式：求出最优值； 判定模式：给定一个实例和一个整数，问是否存在一个可行解 ，使得？显然，在求解最优值不太困难的假设下，上述三种模式的每一种都不比前一种困难。一般而且比较现实的假设是：最优值是一个整数，且这个整数或其绝对值的对数被输入长度的一个多项式所界定。在这种情况下，用二分搜索(或叫折半搜索)技术证明，只要判定模式存在多项式时间算法，求值模式也存在多项式时间算法。所谓算法(algorit
5、hm)是指用来求解某一问题的、带有一般性的一步一步的过程。它是用来描述可在许多计算机上实现任一计算流程的抽象形式，其一般性可以超越任何具体实现时的细节。注意，复杂性理论中对算法的定义与我们通常理解的具体算法(即用某种计算机语言编写的、可在某一特定计算机上实现的计算机程序)有所不同。不过，将算法想象为某个具体的计算机程序，在许多情况下可以帮助我们理解有关概念和理论。附：一个算法的严格定义直到1936年才出现，丘奇(Alonzo Church)和图灵(Alan Turing)分别在他们的文章中给出。丘奇使用称为演算的记号系统来定义算法，图灵用机器(图灵机)来定义算法，后来证明两者是等价的。此前，希
6、尔伯特的第10问题就是要设计一个算法来测试多元多项式是否有整数根。不过他不用算法，而是用一句短语：“通过有限次运算就可以决定的过程”.我们这里采用图灵的定义,即借用图灵机计算模型来给出算法的精确定义。到目前为止，关于算法的描述大致有三种不同的程次：一是形式描述，即详尽的写出图灵机的状态、转移函数等等，这是最底的最详细的描述；二是实现描述，使用日常语言来描述图灵机的运行，如怎么移动读写头，怎么在带上存储数据等，但是不给出状态和转移函数的细节；三是高层的描述，它也使用日常语言来描述算法，但是忽略实现的模型，这种描述不需要提及机器是怎样管理它的带子或读写头的。称一个算法求解一个问题，是指该算法可以应
7、用到的任一实例，并保证能找到该实例的一个解。一个算法的有效性可以用执行该算法所需要的各种计算资源的量来度量。最典型、也是最主要的两个资源就是所需要的时间和内存空间。但时间需求常常是决定某一特定算法在实际中是否真正有用和有效的决定性因素。应该注意到，由于计算机速度和指定系统的不同，同一算法所需时间的多少随着计算机的不同可能有很大差别。为使算法分析具有一般性和在实际中有用，所给时间的度量不应该依赖于具体计算机，即是说，如果它们用不同的编程语言来描述，或在不同的计算机上运行，好的算法仍然保持为好的。另一点需要注意的是，即使同一算法和同一计算机，当用它来求解某一问题的不同例子时，由于有关参数取值的变化
8、，使得所运行时间也有很大差别。对于前一个问题的解决，人们提出了一些简单但又能反映绝大多数计算机的基本运作原理的计算模型，如各种形式的图灵(Turing)机、随机存储机(RAM)等，然后基于这些计算模型来研究算法。对于第二个问题的解决，人们引进了问题例子大小(size)的概念。所谓一个问题例子的大小是指为描述或表示它而需要的信息量。只要表示的合适，可望例子的大小的值应该与求解的难易程度成正比。并称相应的表示法为编码策略(encoding scheme)。事实上，作为输入提供给计算机的对任一问题例子的描述可以看作是从某一有限字母表中选取所需的字符而构成的有限长字符串。通常称该字母表中的字符为码，而
9、由其中之字符如何组成描述问题例子的字符串的方法则称为编码策略。合理的编码策略应该具有可解码性(decodability)和简洁性(conciseness)。一种典型的方法就是利用所谓的结构化字符串，通过递归、复合的方式来给出所考虑问题的合理编码策略。给定一个问题，假设已经找到描述问题例子的一个合理编码策略e，则对的任一实例，称其依编码策略e所得的描述相应问题实例的字符串中所含有字符的个数为其输入长度，并将该输入长度的具体值作为例子的大小的正式度量。例如，若用字母表 中的字符表示旅行商问题的具体例子，则前面所给该问题的具体例子可以用字符串来描述，其相应的输入长度为32。我们说旅行商问题的这个例子
10、的大小为32。为了给出算法的严格定义，我们借助于“语言”这一术语。设是一个字符集，用表示由中的字符组成的所有有限长字符串的集合。的任何非空子集都称为上的一个语言(language)。例如01,001,111,1010110就是字符集0,1上的一个语言。判定问题与语言之间的对应关系是通过编码策略来实现的。一旦选定了某个字符集，则对于任一个判定问题及其编码策略e，和e将会把中的所有字符串划分为三部分：那些不是的例子的编码、那些对的回答为“非”的例子的编码和那些对的答案为“是”的例子的编码。这后一类编码正是要与通过e来联系的语言。定义：如果一个结论对语言成立，则说它在编码策略e下对问题成立（计算复杂
11、性理论所直接考虑的是对语言或字符串集的分析）。对于任何两个合理的编码策略e和e，问题的某个性质要么对和均成立，要么对二者均不成立。因此，可以直接说某个性质对成立或不成立，也常常将简记为。但是，这样的省略却失去了对输入长度的具体确定办法，而我们还需要象这样的一个参变量以便能确切表述复杂性的概念。为此，以后总是隐含假定：对每个判定问题，均有一个不依赖于编码方式的函数Length：该函数的值将与从任一合理的编码策略所得的关于的任一例子的输入长度多项式相关。这里，多项式相关是指：对于的任一合理编码策略e，都存在两个多项式和，使得如果且为在e下的编码，则有这里，表示字符串的长度。易知，的任何两个合理的编
12、码策略将导出多项式相关的输入长度。例如，对于旅行商问题，对应的判定问题的任一例子，可以定义 这里，表示。在下面的陈述中，我们也交替地使用(判定)问题、语言这两个术语而不加区分。2 图灵机与确定性算法为了算法复杂性分析具有普适性，即一个算法的效能与具体的计算机无关，我们需要选定一种可用于描述计算的计算模型。第一个给出这种模型的是英国数学家图灵，后人称他所提出的模型为图灵机。图灵机本质上是一个具有存储载体（通常用一个有无限多个方格线性带表示）的、按照具体指令可完成向左或右移动、放置标记、抹去标记以及在计算终止时停机等四种基本操作的、用于描述算法的语言。在原理上，与我们用于和计算机交流的更为复杂的各
13、种程序语言同样有力。由于其简单性，图灵机及其各种变形已被广泛用于计算复杂性的理论研究。首先选择确定性单带图灵机(deterministic one-tape Turing machine)，简称确定图灵机，记为DTM。一个DTM由一个有限状态控制器、一个读写头和一条双向的具有无限多个格的线性带所组成。 有限状态控制器 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 读写头 图9-2-1 单带确定性图灵机示意一个DTM程序(program)应详细规定下列信息：(a).带中所用字符的一个有限集合，它应包含输入字符表子集和一个特别的空白符号 ；(b).一个有限状态集，它包括初始状态
14、和两个特有的停机状态。(c).一个转移函数。（状态变化和读写头移动方向）一个DTM程序运行很简单。假设对DTM的输入为字符串，则该字符串首先被一格一个字符地存放在带格1到带格中。所有其它的带格均存放空白字符。该程序从初始状态开始它的运算，并且，读写头先位于带格1，然后按下述规则一步一步地进行：若当前状态为或，则计算终止，且如果，就回答“是”，否则回答“非”。若当前状态为，且为读写头当前扫描带格中的字符，而转移函数此时对应的取值为，那么，该程序将执行这样的几个操作：读写头抹去当前带格中的，并写上字符；同时，如果，则读写头左移一格；如果，则读写头右移一格。最后，有限状态控制器将从状态变到状态。这样就完成了程序的一步计算，并为下一步计算做好准备，除非已处于停机状态。可见，当前状态、带格的内容以及读写头所在的位置是图灵机的要素，这三者的整体称为一个格局，图灵机的运行就是根据转移函数发出的指令从一个格局转移的另一个唯一的格局。有了DTM这个计算模型以及定义于它上面的程序概念，就可以给出算法及其复杂性函数的严格定义。设M是一个DTM程序，输入字符表为。我们说程序M接受字符串，如果它作用于时停机于状态，并称为程序M所识别的语言。因此，若，则M的计算要么停机于状态，要么永不停机（不是该问题的实例）。只有当一个DTM程序对定义于其输入字符表
