组合数学第8章组合算法与计算复杂性

第八章组合算法与计算复杂性8.1回溯、剪枝与分治算法8.2动态规划技术8.3试探〔启发式〕算法8.4作业安排问题8.5图灵机与特殊语言类8.1回溯、剪枝与分治算法8.1.1回溯法〔Backtracking〕回溯法有“通用解题法〞的美称。用回溯法可以求得问题的所有解或任意解。回溯法按深度优先搜索策略搜索状态空间树，从而改进了对解空间所有向量进行穷举，并检查约束条件搜索解的朴素做法，减少了搜索工作量。其根本思想如下：设问题的解x所属的解空间为E={x=(x1,x2,…,xn)|xi∈Si,i=1,2,…,n}，构造一棵状态空间树T，解x所满足的约束条件为Pn(x1,x2,…,xn)。若k元组(x1,x2,…,xn)使Pk(x1,x2,…,xk)成立(k＜n)，则称(x1,x2,…,xk)为部分解，即T中的一个状态节点，激活该点。对已有部分解(x1,x2,…,xk)，在Sk+1中按序选取xk+1；若xk+1∈Sk+1，均不能使Pk+1(x1,x2,…,xk+1)成立，即把状态节点(x1,x2,…,xk)删去（或杀死），回溯到(x1,x2,…,xk-1)，在Sk\{xk}中选取新的xk，激活新的状态节点(x1,x2,…,xk)，检查Pk(x1,x2,…,xk)是否成立。按这种方法对T搜索求解，直至得到解，或者问题无解。对应问题P的状态空间树T可动态构造，也可作为一棵实际中并不出现的虚拟树存在。例1(Gauss八后问题)8×8国际象棋棋盘上放置8个皇后。为使各个皇后不能互相攻击，要求任两个皇后都不在同一行、同一列或同一对角线上。共有92种放法，用回溯法可求出全部92种方案。为简化问题，将8×8棋盘上的八后问题缩小到4×4棋盘上的四后问题。用向量(x1,x2,x3，x4)表示问题的一个解，即要求第i行上皇后放在第xi列。为方便计，称第i行上皇后为第i个皇后。先放第1个皇后，再依次放第2、第3、第4个皇后。由国际象棋棋子攻击规那么可知，问题的约束条件为任意二后不能在同行、同列或同一对角线上。首先四后问题有解。〔1〕第1个皇后最初置于第1列，以后根据回溯要求依次取第2、第3、第4列。〔2〕第2个皇后考虑约束条件最初只能置于第3列，依次还可取第4列，以后根据回溯要求后移1列，或依第1个皇后回溯结果再确定满足约束条件的新位置。〔3〕因对1后与2后确定的位置，第3个皇后无论放在哪个位置都违反约束条件，故回溯。〔4〕第3个皇后依1后居第1列，2后居第4列而置于第2列。〔5〕对〔4〕中结果，因第4个皇后无论放在哪个位置都违反约束条件。又3后右移1个，2个方格都违反约束条件，加之2后已居第4列，故回溯。〔6〕回溯结果1后置于第2列。〔7〕1后居第2列，2后只能选第4列。〔8)3后置于第1列，4后因放于第1、2列均违反约束条件，故放到第3列；从而得到四后问题的一个解〔2，4，1，3〕。接着第4个皇后右移一格继续求解……，又可得到另一解〔3，1，4，2〕。回溯法求解问题时，要求假设Pk(x1,x2,…,xk)不成立，那么一定有Pk+1(x1,x2,…,xk+1)不成立。从而，当断定(x1,x2,…,xk)已不满足Pi(x1,x2,…,xk)时，由局部解不可能搜索到问题的解。因而没必要继续求余下的分支，从而可以减少计算的工作量。设xi∈Xi，(x1,x2,…,xk)是局部解，xk+1的可选范围是xk+1的子集Sk+1。例如上述四后问题中取x1=1之后，S2={3,4}。

·回溯算法№1若Sk非空，选xk是Sk中还未选过的最小值；若k<n，则kk+1,并重复№1；若k=n，则(x1,x2,…,xn)为一解；若要求出所有的解，则kk-1,并重复№1；№2若Sk为空，且k=1，停止；若Sk为空，且k≠1，则kk-1，转№1。例2求如下不等式的正整数解：3x1+2x2+x3≤8，i=1,2,3，1≤xi≤3解对i=1,2,3，令Xi={1,2,3}，那么P1(x1):3x1≤8,1≤x1≤3P2(x1，x2):3x1+2x2≤8,1≤x1,x2≤3P3(x1，x2,x3):3x1+2x2+x3≤8,1≤xi≤3,i=1,2,3因假设(x1，x2,x3)满足P3(x1，x2,x3)，那么(x1，x2,)一定满足P2(x1，x2)，且x1一定满足P1(x1)。即问题的解对约束条件具有完备性或具有多米诺性质，故适于用回溯法求解。显见(x1=1)满足P1(1):3×1≤8,即(1）为一部分解；取(x1=1,x2=1),P2(1，1):3×1+2×1≤8,1≤1,1≤3亦成立；再取(x1=1,x2=1,x3=1),P3(1，1,1):3×1+2×1+1=6≤8(1,1,1)为一解；(x1=1,x2=1,x3=2),P3(1，1,2):3×1+2×1+2=7≤8(1,1,2)为一解；(x1=1,x2=1,x3=3),P3(1，1,3):3×1+2×1+3=8≤8(1,1,3)为一解；

x3=4已违反约束条件。取(x1=1,x2=2),P2(1，2)=3x1+2x2=3×1+2×2=7≤8,1≤x1,x2≤3亦成立；再取(x1=1,x2=2,x3=1),P3(1，2,1)=3×1+2×2+1=8≤8(1,2,1)为一解，x3=2已违反约束条件。取(x1=1,x2=3),P2(1，3)=3×1+2×3=9＞8已不满足原不等式。不难验证，对(x1=2)，(x1=3)，采用回溯法均已求不出问题的解。故例2仅有4个解：(1，1，1)，(1，1，2)，(1，1，3)，(1，2，1)

注意1：回溯法能一个不漏地求出问题的解，因为它只跳过对状态空间树中T不可能通向解的状态节点的搜索。

注意2：回溯法求解问题P的过程是系统地、动态地搜索激活、检查约束和回溯杀死状态空间树T的一个状态节点序列的过程。注意3：可以采用回溯法求解的问题须满足完备性或多米诺性质。对如下问题求整数解：3x1+4x2-x3≤10,i=1,2,3,1≤xi≤3因为3x1+4x2≥10，但3x1+4x2-x3≤10，即P2(x1,x2)不满足P3(x1,x2,x3)不满足，多米诺性质不成立，故不能采用回溯法。这时可令x3′=3-x3，那么原问题变为3x1+4x2+x3′≤13,i=1,2,1≤xi≤3，0≤x3′≤2，时问题就满足了多米诺性质，可用回溯法求出解向量(x1,x2,x3′)，进而转为原问题的解(x1,x2,x3)。注意4：改进回溯算法的途径。〔1〕回溯算法对于比较复杂的问题因执行时间太长而无法实现。但有些问题〔如八后〕所求状态，其位置从几何上看具有对称性，从而可考虑改进算法，减少工作量。〔2〕把一个较大问题分解为几个子问题，并利用子问题的解进行组合来求得原问题的解。参见1.4节分治算法。8.1.2分支界限法〔BranchandBound〕分支界限方法是从回溯法演变而来的，也是一种在状态空间树T上搜索解的过程。二者的不同之处在于搜索目标。回溯法旨在搜索T中满足约束的所有叶状态；而分支界限法的求解目标那么是找出T中满足约束且使某一目标函数到达极大〔或极小〕的叶状态，即问题在某种意义下的最优解。回溯法只通过约束条件，分支界限法除要通过约束条件，还要通过目标函数的界限来减少无效搜索，提高搜索效率。回溯法采用的是深度优先搜索策略，即先检查扩展节点的每个子节点，并把满足约束条件且不越过目标函数当前界限者都激活，然后从中选出一个扩展节点继续搜索。分支界限法中把满足约束条件的解称为可行解，最后要求的最优解是指在最大〔最小〕化问题中，求目标函数值取最大〔最小〕的可行解。因为最大、最小是可以相互转化的，如下仅讨论目标函数值取最小的情形。状态空间树的每个分支点对应(x1,x2,…,xk)，k＜n，仍用(x1,x2,…,xn)表示解。分支界限法求最小解时，对每个局部解，都有一相应的“代价〞，且“代价〞函数应满足关系：C(x1,x2,…,xk)≤C(x1,x2,…,xk,xk+1)即父节点的代价不得超过子节点的代价。还要求代价函数和目标函数在叶状态的值相同。当找到一个可行解Y时，设Y的代价为B。对状态空间树中搜索到的某个分支点X，假设X的代价大于B，那么其子孙的代价会更大，故不可能成为最优解，因此，没有必要再搜索X的子孙。可将X为根的子树剪去，减少计算工作量。一般将可行解的代价作为上界B，当找到一个更优〔代价更小〕的解时，B就修改成这个解的代价。求最大解可类似讨论。对有些问题，代价函数C(x1,x2,…,xk-1)往往不易求得，但可用一个容易计算的函数C*(x1,x2,…,xk-1)代替C(x1,x2,…,xk-1)。

例3(分配问题)设有4个零件P1，P2，P3，P4，要在4台机器m1，m2，m3，m4上加工。矩阵A=(aij)中，(aij)表示Pj在mi上加工的时间。规定每个零件只能在一台机器上加工，且每台机器只能加工一个零件，这是约束条件。求耗时最少的加工安排方案。m1m2m3m4A=(aij)=P1P2P3P4用向量(x1,x2,x3,x4)表示Pi在mxi上加工，i=1,2,3,4。由问题的约束条件知x1,x2,x3,x4是{1,2,3,4}的一个排列。满足约束条件的解称为可行解，使目标函数ax1,1+ax2,2+ax3,3+ax4,4取最小值的可行解为最优解。因m1加工P1耗时最少，可取C*(1)=4为下界，并取x1=1，其余xi值待定，局部解为〔1〕，因P1在m1上加工，在矩阵A中不再考虑第1行、第1列。从A中删去第1行、第1列,得子矩阵：m2m3m4P2P3P4图8.1.1例3插图例4(背包问题)设xj为放入背包内Pj类物件的件数，b为背包内允许装入物件的最大重量，wj，vj(1≤j≤n)分别为Pj类物件的重量和价值,那么背包问题〔在不超重前提下装入物件价值最大〕可归结为如下整数规划问题：即求满足约束条件并使目标函数值取最大的解(x1,x2,…,xn)。解背包问题之前先将物件按价值比重量进行排序并编号，考虑把单位重量价值高的物件排在前边优先装包，使得对物件重新编号后有vi/wi≥vi+1/wi+1。背包问题的解由n元组(x1,x2,…,xn)表示，属状态空间树T的叶节点。k元组(k<n)(x1,x2,…,xk)为部分解，是树T的分支点。此时，对已装入背包内物件的重量 ，有如下2种情况：〔1〕存在j>k，使得这说明背包内还可装入物件xj(j>k)而不超重。其中，假设全部放Pk+1类物件自然要比放其它物件价值高。从而，对局部解(x1,x2,…,xk)，相应的函数值C*(x1,x2,…,xk)就取为由于vi/wi≥vi+1/wi+1，上式给出的值就是前缀为(x1,x2,…,xk)的可行解的目标函数值的一个上界。且这样确定的C*值满足C*(x1,x2,…,xk)≥C*(x1,x2,…,xk,xk+1)〔2〕对所有j>k，这说明背包内已无法放入任一Pj(j>k)类物件，否那么就会超重。它对应的可行解为解空间中的向量(x1,x2,…,xk,0,0,…,0)，故在树T的这个状态点上不必再生成子节点。C*(x1,x2,…,xk)就取设背包内可放4种物件P1,P2,P3,P4，w1=8,w2=6,w3=5,w4=2；v1=10,v2=7,v3=5,v4=1。限制背包内总重不超过10。求把物件放入背包在不超重的前提下使装入物件价值最大的方案。解根据题意，可得如下整数规划问题:约束条件：8x1+6x2+5x3+2x4≤10目标函数：z=10x1+7x2+5x3+x4求4元组(x1,x2,x3,x4)，xi为非负整数(i=1,2,3,4)，满足约束条件且使目标函数z取最大值。一般情况下需要对物件先进行排序编码，因本例所给物件已满足v1/w1>v2/w2>v3/w3>v4/w4，即10/8>7/6>5/5>1/2，就按P1,P2,P3,P4先后排列的优先顺序向背包内放物件。背包容纳物件重量限制为10，w1=8，放入背包的物件数只能是0个或1个。记X1={0,1}，同理可得X2={0,1}，X3={0,1,2}，X4={0,1,2,3,4,5}。在要生成的状态空间树T中，根节点只有2个子节点(1)及(0)。第1层节点也有2个子节点，第2层节点有3个子节点，第3层节点有6个子节点。由根生成子节点〔0〕和〔1〕，有图8.1.2例4插图8.1.3游戏树与α-β剪裁在博弈游戏中，对弈双方需要根据当前弈局分析预见以后的格局，选择自己的对策，希望能战胜对方，战平对方，或在最不利的情况下，输得最少。决策树是处理对弈乃至一般竞争的工具。设有2个人F〔First，先手〕与S〔Second，后手〕玩棋子游戏，一共6枚棋子，2人轮流取，每次可取1枚、2枚、3枚，但不能不取；谁最后取完棋子算谁赢，且取到几枚赢几分。图8.1.36子游戏树参见图8.1.3，方框表示轮F取子，圆圈表示轮S取子，其中的数字表示剩余棋子数，边上的数字表示取走的棋子数，叶节点处标F表示F赢，标S表示S赢。叶节点中的数值表示F〔或S〕赢得的分值。现从对策树中要选出估计可能是“最好〞的一系列对策。这种估计是由树叶的估计函数值通过最大最小过程进行的。树叶的估价函数值是静态的估价函数值，这是从现在的格局以及对将来的影响综合得到的。由于游戏是F、S双方轮流进行，决策树以一方〔如F〕考虑每个分支的估价函数值。图8.1.4是一棵假象对策树。树叶上的值是事先对格局综合考虑后给出的。其中方框节点表示由F作决策，圆圈节点表示由S作决策。如果以赢x分表示F赢x分，当然F希望赢的分值越大越好，故称F为极大化者。对S而言，自然希望这个x越小越好，甚至一直小到-x，即F赢-x分或看作S赢|x|分，故称S为极小化者。图8.1.4由叶节点导出的决策树从而对F而言，给每个方框节点都从子节点选最大值填入；而对S而言，给每个圆圈节点都从子节点中选最小值填入。对于一个比较复杂的游戏，如果采用上述分析方法，从树叶开始一步一步向回推，直到树根为止，这实际上几乎是不可能的。从而对某些问题考虑采用分支界限的方法，对决策树而言，就称这种技术为α-β剪裁。图8.1.5α-β剪裁在图8.1.5〔a〕中，r为极大化点，u是r的子节点且u值为α。当v<α时，在搜索中就可删去v及以它为根的子树。亦即，可把v为根的子树从决策树中剪掉，常称其为α[CD*2]剪裁。值α称为r的下剪裁值。对于r的后裔，但凡小于r的下剪裁值者都要剪掉。不难发现，如果r的下剪裁值为α，那么r的所有后裔的下剪裁值也是α。因为对r的后裔，比方v，它是极小化点，只有当v的所有儿子都大于等于α时，v的值才能大于等于α。故对v的所有小于α的子节点根本不必考虑。类似地，可定义r的上剪裁值β。在图8.1.5(b)中，r是极小化点，u是r的一个子节点，且u值为β。如果v值>β，那么可以把以v为根的树从决策树中剪裁掉,常称其为β-剪裁，并称β为上剪裁值。不难看出，当r的上剪裁值为β时，r的所有后裔的上剪裁值也是β。如图8.1.6所示的对策树，采用α-β剪裁技术后变为图8.1.7。图8.1.6剪裁树图8.1.7α-β剪裁实例8.1.4分治算法分治算法是一种重要的设计算法的方法。一般将一个规模大的问题分割成假设干个子问题，解出这些子问题后，再把它们组合成原问题的解。往往子问题和原来问题的类型相同，这就可与递归过程结合使用。分治算法中一个著名的例子是Strassen的矩阵相乘算法。设A,B为两个n×n矩阵，乘积C=A·B也是n×n矩阵,计算C(i,j)要n次乘法,n-1次加法。矩阵C一共有n2个元素，因此总共需要作n2(n-1)次加法,n3次乘法。分治算法提出了另一种计算矩阵的方法。为简单起见，假设n=2k，把矩阵分别划分为4个n/2×n/2的子矩阵，矩阵A和B相乘为通常矩阵乘法是Strassen计算Cij的方法，仅需要7次矩阵乘法和18次矩阵加减法，公式如下：设T(n)是两个n×n矩阵乘积所需的元素运算〔乘法，加减法〕次数。依上述Strassen方法，可得递推公式:于是其中，n=2k,k=lbn。因此Strassen矩阵相乘算法的时间复杂性是O(nlb7)≈O(n)证明恰有36种方法计算Cij，每种方法仅使用7次乘法。以下再介绍一种。S1=A21+A22,S2=S1-A11,S3=A11-A21,S4=A12-S2S5=B12-B11,S6=B22-S5,S7=B22-B12,S8=S6-B21M1=S2S6,M2=A11B11,M3=B21,M4=S3

S7;M6=S4B22,M7=A22

S8,T1=M1+M2,T2=M1+M4;C11=M2+M3,C12=T1+M5+M6,C21=T2-M7,C22=T2+M5

一共7次矩阵乘法和15次矩阵加减法。假设能找到一个方法，少于7次矩阵乘法，那么时间复杂性O(n)能进一步减少。但是，Hopcroft和Kerr证明7次乘法是必需的，再也不能减少。Victorpan发现新方法，时间复杂性是O(n)。8.2动态规划技术所谓动态规划,是相对于静态规划而言的。一般的线性或非线性规划问题，不涉及与时间有关的因素，故称之为静态规划。在动态规划中，要处理的问题可以分成多个子问题，子问题互相关联，形成多个阶段，多阶段的决策策略只与有关阶段的因素有关，因此可以独立处理，为随后的处理提供先决条件，连锁反响到下一个阶段，最终导致整个问题获解。从整体上看，连锁反响的各阶段间增添了一种伪时间因素，故称之为动态规划。许多静态规划问题假设按照动态规划思想划分成阶段处理，也可用动态规划的方法予以解决，效果会更好。动态规划是设计组合算法的一个重要技术，在求解最优化问题上非常有用。正是由于它是用于许多问题的一种普遍技术，因而在求解某些具体问题上不如专门精心设计的算法效率高。尽管如此，动态规划仍不失为求解最优化问题的一种重要的方法。下面通过求最短路的例子来说明动态规划的思想。

例1(最短路问题)图8.2.1(a)是一个街道的平面图。直线表示街道，顶点表示街道的交叉口。边上的权表示对应一段街道的长度。一个人要从S走到T，走向只能是向下、向右。求最短的行走路线。图8.2.1街道平面图转换为多阶段图(a)街道平面图；(b)多阶段图用d表示向下走，r表示向右走。从S到T的一条路对应3个d与3个r的排列。因此一共有C(6,3)=20条从S到T的路。假设列举出每一条路，分别求出它们的长度，从中选出一条最短路，这是一个朴素的方法。在街道数增长时，计算量与C(2n,n)成正比，其中n为d(r)的个数。这样计算量是指数级。使用动态规划方法，计算量可以降到多项式级。在图8.2.1(a)中，L=SA1B2C3D3E2T是从S到T的最短路，任取最短路l的一局部路，从这局部路的起点到它的终点，沿着这段路走一定是最短的。例如,l1=SA1B2C3是l的局部路，是从S到C3的最短路。假设还有一条从S到C3的更短的路，在l中用它来代替l1，将得到一条比l更短的路，这与l是最短路矛盾。因此，只有最短的局部路才能组合为从S到T的最短路。在图8.2.1(a)中,顶点集合划分为{S},{A1,A2},{B1,B2,B3},{C1,C2,C3,C4},{E1,E2}和{T}。图中每条弧都是由前一个集合中的1个顶点到后一个集合中1个顶点。这种有向图称为多阶段图。从S到T分为假设干个阶段，每个阶段都是前一个顶点集到后一个顶点集。多阶段过程用多阶段图表示，如图8.2.1〔b〕所示。由最后一段开始计算，逐段由后向前计算,直到出发点S。最后一段是由{E1,E2}到T的路，在图8.2.1(b)中处于第6段。令fk(v)表示第k段中顶点v到T的最短距离。有f6(E1)=6,f6(E2)=7,并在顶点E1上标“d〞，顶点E2上标“r〞。在第6段上，顶点D1和D3到T只有1条路，d5(D3)=12。分别标上“d〞和“r〞。从D2出发那么有两种选择。从两条路中选择短的一条:f5(D2)=min{d(D2,E1)+f6(E1),d(D2,E2)+f6(E2)}=min{4+6,5+7}=10选择E1，在顶点D2上标“r〞。D2→E1→T2是从D2到T的最短路。在第4段上,C1和C2到T只有一条路，f4(C1)=14，在C1上标“d〞。f4(C4)=15，在C4上标“r〞。从C2出发那么有两种选择，从中选择最短的路:f4(C2)=min{d(C2,D1)+f5(D1),d(C2,D2)+f5(D2)}=min{3+13,5+10}=15选择D2，在顶点C2上标“d〞，C2→D2→E1→T是从C2到T的最短路。从C3出发也有两种选择，从中选择最短的一条:f4(C3)=min{d(C3,D2)+f5(D2),d(C3,D3)+f5(D3)}=min{6+10,5+10}=15选择D3，在顶点C3上标“d〞，C3→D3→E2→T是从C3到T的最短路。用同样的方法继续求第3段,第2段,第1段各顶点到T的最短路，所得结论如下：f3(B1)=18,顶点B1标“d〞;f3(B2)=17，顶点B2标“d〞;f3(B3)=19，顶点B3标“d〞;f2(A1)=19，顶点A1标“d〞;f2(A2)=21，顶点A2标“r〞;f1(S)=21，顶点S标“r〞。从S到T的最短路长度是21。沿各顶点上的标号指出的方向走，SA1B2C3D3E2T是一条最短路。由上述求解过程可见，fk和fk+1满足递推关系式:上例中，k=5,4,3,2,1。hk(v)是第k阶段中所作的下一个顶点的选择。称上式为函数方程。函数方程是根据动态规划的最优原理得出的。动态规划的最优化原理，作为整个过程的最优化策略具有性质：对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。对于最短路问题，假定l=v1v2…vk是从v1到vk的最短路，开始于顶点v1，多了一个决策之后到顶点v2。现在的状态由顶点v2决定。l=v2v3…vk应是一条从v2到vk的最短路，因此，对于最短路问题，最优原理成立。使用动态规划求解多阶段决策问题时，首先要求对于该问题最优化原理成立，然后列出函数方程，从后向前逐步计算，最后求出整个问题的最优解。例2(投资分配问题)假设有4万元资金，准备给4种产品投资。设第i种产品的投资数为xi，年利润为fi(xi),i=1,2,3,4,如表8.2.1所示。问如何将4万元投资给这4种产品使年利润综合最大？〔以万元为单位)表8.2.1资金分配表解首先投资分配问题可以化成以下数学问题：约束条件：x1+x2+x3+x4=4目标函数：z=f1(x1)+f2(x2)+f3(x3)+f4(x4)使得目标函数z取最大值，其中xi为非负整数，i=1,2,3,4。设Fk(x)是x〔万元〕投资在前k个产品后所得的最大的年利润。显然F1(x)=f1(x)。设xi(x)是取得最大年利润的第I个产品的投资数。F2(x)是x投资到第1,2两个产品上所得的最大年利润。投资在第2个产品上的资金是x2，那么投资在第1个产品上的资金是x-x2，所以同理可得从F1(x)=f1(x)开始，逐步地求F2(x),F3(x),F4(x)。Fk(x)(k=1,2,3,4)都是〔局部〕问题的最优解。对于投资问题，最优策略是确定对每个产品的投资，使4个产品的年利润之和最大。假设对4个产品的投资是x，第4个产品的投资是x4，还剩下x-x4要对其余3个产品投资。假设对3个产品分配的投资不能取得年利润最大值，那么这样对4个产品的投资也一定不是最优策略。所以只要求出局部问题的最优解，就可将其组合成整个问题的最优解。当x=1时，由 ，有①x2=1,x1=x-x2=0,f2(1)+f1(0)=0+0=0②x2=0,x1=x-x2=1,f2(0)+f1(0)=0+9=9就取F2(1)=max{0,9)=9，相应于x1=1,x2=0。继续求F2(2),F2(3),F2(4)。然后求F3(x)和F4(x)。F1(x),F2(x),F3(x),F4(x)以及x1(x),x2(x),x3(x),x4(x)的值如表8.2.2所示。表8.2.2Fi(x)和xi(x)值F4(4)=23，即4〔万元〕投资给4个产品，年利润最大值是23〔万元〕。相应地，x4(4)=1，可知第4个产品的投资为1万元，3〔万元〕投资给了前3个产品，查表知F3(3)=13，相应地，x3(3)=0,2。即取最大的利润有以下两种方案。〔1〕在第3个产品上不投资，3〔万元〕投资在前2个产品上，查表得F2(3)=13，相应地，x2(3)=2，第2个产品得到2〔万元〕投资。故知第1个产品得到1〔万元〕投资，因此有解(x1=1,x2=2,x3=0,x4=1)。〔2〕在第3个产品上投资2〔万元〕，1〔万元〕投资在前两个产品中，查表得F2(1)=9，相应地，x2(1)=0，在第2个产品上不投资，即第1个产品上投资1〔万元〕。因此，有解〔x1=1,x2=0,x3=2,x4=1〕。现讨论对投资问题动态规划算法的复杂性。设有m〔万元〕对n个产品投资xk取值：0,1,2,…,x-1,x

此求Fk(x)需要作x+1次加法和x次比较。由于x取1至m，因此需要次加法以及次乘法。因k取1至n，因此求Fk(x)的所有值需要O(m2n)次运算。8.3试探〔启发式〕算法对求最优解的问题，有些问题的求最优解算法是有效的。但是，对有些问题，目前的求最优解算法的时间复杂性是指数的。由于需要太长的时间,以至在实际中无法使用。人们发现试探算法〔HeuristicAlgorithm〕，对有些问题也能得到最优解,这一点在直观上似乎是明显的。但是，由于试探算法并不一定得到最优解，自然提出两个问题：(1)试探算法在什么条件下得到最优解？(2)假设试探算法不能够得到最优解，最大的相对误差是多少？希望得到充要条件以保证算法求得最优解。在不能得到最优解时，假设一个试探算法对问题的大局部实例求解所需时间比较适宜，并且最大相对误差也在一定范围内，那么人们还是比较愿意用试探算法。在试探算法中，贪心〔Greedy〕算法往往被列于首位。这里把试探算法作为设计算法的技术进行讨论，在NP完全问题的近似算法中还可见到试探算法。日常生活中，有的小孩吃东西总挑大个的，有的家长要求子女啥话都要听，有些专制领导要求职工什么事情都要按他的意图办，有些人见啥廉价就想沾。这些都属于贪心行为，其结果姑且不管。在数学中也有依照一种最优度量法那么每步都取局部最优最后求得解的方法，该法对某些问题也能取得最优解。例如求连通无向图的最小生成树，但有些问题不能求得最优解。设vs到v1,v2距离分别是1,50,v1,v2到vt的距离分别是100,50,v1到v2的距离是200，求从vs到vt的最短路。按照贪心算法的思路，先选定距离vs最近的顶点v1，然后再到vt，所得的一条路长101。但从vs经v2到vt是一条更短的路。每次选一个最邻近的顶点不一定能够求得最短路。尽管如此，贪心算法仍不失为一种常用的试探算法。例1(背包问题)规定背包内物件的重量不超过b。有n类物件a1,a2,…,an，物件ai的重量与价值分别是wi,vi。背包问题如前所述，这里允许物件可局部放入，并设第i类物件放入背包，局部占整个物件的比例为xi，那么这种背包问题的数学描述为约束条件：目标函数：求解(x1,x2,…,xn)，使z取最大（0≤xi≤1,vi,wi>0）。显然，当 时，则（1,1,…,1）是最优解；当时，xi不能全部为1。对于具体例子，(v1,v2,v3)=(50,48,30),(w1,w2,w3)=(36,30,20),b=40，有以下四个可行解:(x1,x2,x3)(1/2,1/3,1/4)3348.5②(1,2/15,0)4056.4③(0,2/3,1)4062④(0,1,1/2)4063使用贪心算法首先要确定按照哪个量排序。对于背包问题有3种排序的方法：〔1〕依照物件的价值排序。由于(v1,v2,v3)=(50,48,30)，先把第1个物件放入背包内，x1=1,w1<b，b-w1=4，取x2=4/30=2/15，得到可行解(x1,x2,x3)=(1,2/15,0)，装入背包物件价值56.4，不是最优解。〔2〕依物件重量轻者优先，得解〔0,2/3,1〕。装入背包物件价值为62，仍非最优解。（3）依照vi/wi的大小把物件进行排序，v1/w1=50/36=1.39，v2/w2=48/30=1.6，v3/w3=30/20=1.5。物件的次序应排为2,3,1。即先取第2个物件，x2=1，b-w2=40-30=10，再取x3=1/2，得到一个可行解（0,1,1/2），。以下证明（0，1，1/2）是最优解。为了方便起见，设有n个物件，它们的次序已经满足下列不等式:使用贪心算法，按照1,2,…,n次序把物件放入背包内。假设全部n个物件都能够放入，当然是最优解。假设第j个物件放不下整个，只能局部放入背包。背包的重量刚到达b，以后的物件不再考虑。设X=(x1,x2,…,xn)是由贪心算法得到的解。假设所有的xi都等于1，这是最优解。否那么，设j是xi≠1的最小下标，有xi=1,i<j;xi=0,j<i≤n。若X不是最优解，则必存在另一可行解Y=(y1,y2,…,ym)，使得∑viyi>∑vixi。不失一般性，假设∑wiyi=b,k是使xi≠yi的最小下标。因为X≠Y，这样的k一定存在。往证yk<xk。为此，考虑以下三种情形：（1）若k<j，则xk=1，又xk≠yk，有yk<1，所以yk<xk。（2）若k=j，由于 和xi=yi,1≤i<j。假设yk>xk，也有yj>xj这与Y是可行解矛盾。〔3〕假设k>j，那么现在把yk增加到xk，同时减少yk+1,…,yn中的一些值，得到新的可行解Z=(z1,z2,…,zn)，zi=xi,1≤i≤k因背包内的物件重量仍为b，有且有因Y是最优解，且有故Z也是最优解。但Z比Y多1个与X相同的分量。继续上述过程，可推出X是最优解。一般情况得证。上例〔0,1,1/2〕是最优解。例2(Huffman最优树)设T是一棵有t片树叶的二叉树，分配给树叶的权分别是w1,w2,…,wt。设l(wi)是权为wi的树叶到根的路长。定义树T的权在树叶的权为w1,w2,…,wt的所有二叉树中，权最小的一个二叉树称为最优二叉树。例如给定权5,6,7,8，图8.3.1〔a〕是最优二叉树，图8.3.1〔b〕不是最优二叉树。图8.3.1两种二叉树的比较Huffman提出了一个求最优二叉树的方法，并且这个方法可推广到求最优6元树上。设有t个权w1,w2,…,wt。先把权按照从小到大次序排好。不妨假设w1≤w2≤w3≤…≤wt先构造t个顶点，每一个顶点是树，分别带权w1,w2,…,wt。其中找出2个最小的权w1,w2，构造一棵二叉树，它的权为w1+w2。现有t-1棵二叉树，权分别为w1+w2,w3,…,wt。再在这t-1棵二叉树中找出2棵权最小的二叉树，合并成1棵二叉树，权为原2棵树权的和。原来的2棵二叉树成了合并后树的左子树、右子树。在每一步上选择2棵权最小的二叉树，合并成1棵二叉树，权是原来2个权的和，该过程进行到1棵二叉树为止。假设把权小的看成优，由于每步都择优选取，这样的方法属于贪心算法。图8.3.2最优二叉树假设w1+w2,w3,w4,w5,w6分别是2,3,5,7,9,11。使用Huffman方法的过程如下所示:2

357911

5

57911107

911

101611

16

21

37数字下带一划指出最小的权。所得的最优二叉树如图8.3.2所示。现在用数学归纳法证明Huffman方法求得的二叉树是最优二叉树。设t=2，有两个权w1和w2，树叶上权分别为w1、w2，树高为1的二叉树是最优树。根到树叶的路长为1。

归纳假设：有k个权，k<t，用Huffman方法求得的二叉树是有k个权的最优二叉树。现设有t个权，w1≤w2≤…≤wt。设T是用Huffman方法求得的一棵二叉树，用W(T)表示该二叉树的权。设T1是树叶上带权w1,w2,…,wt的一棵最优二叉树。要证明W(T)=W(T1)，从而，T也是一棵最优二叉树。在二叉树T1中，设v0是离树根最远的分支点。v0有两个儿子顶点〔树叶〕va和vb，假设它们的权不是w1和w2，就把这两片树叶与带权w1和w2的树叶交换。这样交换后，由于va和vb是长度最大的树叶，而w1和w2是最小的权，因而不会增加树的权。所得的二叉树依然是最优二叉树。该树记为T2，有W(T2)=W(T1)。在T2中删除v0的两个儿子节点va和vb，v0成为一片树叶，带权w1+w2，新得到的二叉树记为T2′，是带权w1+w2,w3,…,wt的最优二叉树。用Huffman方法求w1+w2,w3,…,wt的二叉树。由归纳假设，可以得到最优的二叉树T′，在T′中，把带权的w1+w2的树叶改成分支点，生成两个带w1和w2儿子的顶点〔树叶〕。这样的二叉树就是树T。有W(T)=W(T′)+w1+w2。由于T′和T2′都是最优二叉树，因而W(T2′)=W(T′)，故有因此，T是一棵最优二叉树。8.4作业安排问题本节中考虑在n个相同处理器的计算机系统上执行一批作业的安排问题。设P1,P2,…,Pn是n个相同的处理器。设J={T1,T2,…,Tm}是作业的集合。有以下假设：（1）一个作业可以在任一台处理器上执行。作业一旦在一台处理器上开始执行，直到作业完成，中间不得中断。（2）在J上有一偏序关系，TiTj当且仅当作业Ti执行完毕后才能执行Tj。偏序集合用Hasse图表示，顶点代表作业，圆圈旁注作业名，圆圈内数字表示完成作业的时间。

〔3〕一旦有一台处理器空闲，并且有一个作业需要执行，作业应在处理器上立即执行。用t(Ti)表示完成作业Ti的时间，φ1,φ2,…表示处理器空闲时期，T(φi)表示空闲时期φi的时间。一台处理器有时因为没有可以执行的作业而处于空闲，也可成心让它空闲。假设让所有的处理器同时都空闲，这只能延长完成m个作业的时间。但有时成心让某些处理器空闲待命反而使完成全部作业的时间提前。由w表示完成全部作业的时间。例1由偏序图8.4.1〔a〕可知，系统只有完成了作业T1和T2后，才能执行T4和T5。也只有在完成了T4和T5之后才能执行T6。在图8.4.1〔b〕中，当t=9时，虽然可以执行T3，但P2在9与10之间成心空闲1个单位，这样整个完成时间w=24。在图8.4.1〔c〕中,P2没有成心空闲，在完成了T2后，因T1还没有完成，只能执行T3，结果完成时间w=29。图8.4.1例1图例2设有3台处理器p1,p2,p3，有9个作业T1,T2,…,T9。完成作业时间写在相应的圆圈内。执行先后的偏序关系如图8.4.2〔a〕所示。一种安排如图8.4.2〔b〕所示。完成时间是12。假设处理器数目由3增加到4，其余条件不变，完成时间反而增加到15，如图8.4.3所示。假设减少先后次序的约束，也可能增加完成时间。如对图8.4.4〔a〕所示偏序图，T5和T6一定要在T4完成之后才能执行这一约束条件取消。比较图8.4.5与图8.4.2可知，减少作业执行时间，有时也会增加完成所有作业的时间。尽管作业安排有着复杂异常的现象，但其数量关系还是有一些规律可循。图8.4.2例2图(一)图8.4.3例2图(二)图8.4.4例2图(三)图8.4.5例2图(四)命题给定一批作业，对这些作业的安排没有成心让处理器处于空闲状态，设w是这样完成的时间，w0是最小完成时间，那么w/w0≤2-1/n，其中n是处理器的个数。而且这个上界是可以到达的。证明因为没有成心让一台处理器处于空闲时期，只要有作业可执行，而且有处理器处于空闲时，就立即将作业在处理器上执行。因此，一台处理器pi上的一个空闲期结束的时刻，恰好与另一台处理器pj上的1个作业执行完成时刻重合。一个作业完成促使其他作业可以执行，从而结束pi的空闲时期。设处理器pk有一个空闲时期φj，在φj后有执行作业Tj的时期，则一定存在作业Ti，TiTj。表明Tj完成后才能够执行Tj，否则Tj可以提前执行。若Ti的时期长于φj的时期，则Ti可以盖住φj。若Tj的时期短于φj的时期，一定存在TqTi，否则Ti可以提前在pk上执行。重复论述，存在一列作业，它们在图上盖住φj,如图8.4.6所示。这里n=2，φj是一个空闲时期，T6,T7,T8盖住φj，T3,T4盖住φj。图8.4.6存在盖住空闲时间的作业安排用J*表示所有覆盖空闲时期的作业序列，在图8.4.6中，J*是T6T7T8T3T4。设J是所有作业的集合;w0是最小完成时间，它对应着最优的作业安排，其中也可能有处理器处于空闲状态。有J*是一个作业序列，不管作业如何安排，J*内作业只能够依照次序进行。因此又因为至多有n-1台处理器同时处于空闲时期，对于作业的一段覆盖，最多对应n-1个空闲时期，所以有所以这说明在有n给出了n=2,3,4的实例，说明可到达这个界。图8.4.7n=2,3,4时的执行作业实例8.5图灵机与特殊语言类8.5.1图灵机图灵机〔TuringMachine，TM〕模型由一条向右无限伸长的带子〔作为无限存储〕，一个读写头和一组控制读写头工作的命令〔控制器〕组成，如图8.5.1所示，读写头能在带子上读写和移动。开始时，带子上只有输入串，其它地方都是空的。如果需要保存信息，图灵机能将信息写在带子上。为了读已经写下的信息，图灵机可将读写头往回移动到信息所在位置。机器不停地计算，直到产生输出为止。图灵机在事先设置了2种状态：接受或拒绝状态。如果进入这两种状态之一，就产生输出：接受或拒绝；如果不进入任何接受或拒绝状态，就继续执行下去，永不停机。图8.5.1图灵机模型示意图形式上说，任何一个对所有有效输入总要停机的图灵机是一个算法。图灵机与有限自动机的这类计算模型的区别在于：〔1〕图灵机在带子上既能读又能写；〔2〕读写头既能左移又能右移；〔3〕带子无限长；〔4〕进入拒绝或接受状态立即停机。例1考虑TMM1，它检查语言A={w＃w|w∈{0,1}*}与其元素的隶属关系，即要设计M1，使得如果输入是A的成员，它就接受。事实上，M1的任务是要检查输入串是否有符号＃，并逐个检查＃号两边对应位置的符号是否同为0〔或同为1〕。设计M1，使之以上述方式工作，读写头在输入串上屡次通过，每一次匹配＃号两边对应位置的一对字符。可将扫描过的符号打上记号，为了跟踪哪些字符已经被检查过，M1消去所有已检查过的符号。如果所有的符号均已被消去，就意味着匹配成功，M1进入接受状态；如果发现有一个不匹配，那么M1进入拒绝状态。M1的算法如下：M1=“对输入串w：№1扫描输入，确认其包含的＃号只有一个，否那么拒绝；№2在两边对应位置来回移动，检查这些对应位置的符号是否匹配；如有一对不匹配那么拒绝；为跟踪对应符号，消去所有检查过的符号〔用×号代替〕；№3当＃左边的符号都被消去时，检查＃号右边是否还有符号，假设是那么拒绝，否那么接受。〞

定义1一个图灵机是一个7元组M=(Q,Σ,Γ,δ,q0,qaccept,qreject)，其中，Q，Σ，Γ都是有穷集合，并且（1）Q是状态集；（2）Σ是输入字母表，空白符Σ；（3）Γ是带字母表，其中：∈Γ,ΣΓ；（4）δ:Q×Γ→Q×Γ×{L,R}为转移函数；（5）q0∈Q是起始状态；（6）qaccept∈Q是接受状态；（7）qreject∈Q是拒绝状态，且qaccept≠qreject。图灵机M的计算方式如下：首先，M从最左端接收输入串w=w1w2…wn∈Σ*，带的其余局部为空白〔即填入空白符〕。读写头从输入的第一个符号所在位置开始运行。注意到Σ不含空白符，故输入串最右端字符后的第一个空白符表示输入的结束。M启动后根据转移函数所描述的规那么运行，当计算持续到它进入接受或拒绝状态时，即停机;否那么,M永远运行下去。图灵机计算时，当前状态，带的当前内容和读写头当前位置会发生改变，这三项构成的整体叫做图灵机的格局〔或称描述〕。格局常以特殊方式表示。对于状态q和带字母表上的两个串u和v，以uqv表示格局：当前状态为q，当前带内容为uv，读写头的当前位置是v的第一个符号例如，1011q70111表示格局：当前状态为q7，带的当前内容为10110111，读写头指向第2个0图8.5.2处于格局10110111(q7指向第2个0)的图灵机现在对图灵机的计算方式进行形式化。如果图灵机能合法地从格局C1一步进入格局C2，那么称C1产生格局C2。这个概念形式定义如下：设a,b,c∈Γ，u,v∈Γ*，qi,qj∈Q，那么uaqibr和uqjbcv是两个格局。注意到δ:Q×Γ→Q×Γ×{L,R}意指，假设机器处于q状态，读写头所指带方格内的符号为a，那么当δ(q,a)=(q′,b,L)时，机器写上符号b以取代a，并进入状态q′。第三个分量是L还是R指出，在写带之后，读写头是向左还是向右移动。从而，如果δ满足δ(qi,b)=(qj,c,L)，那么称格局uaqibv产生格局uqjacv如果δ满足δ(qi,b)=(qj,c,R)，那么称格局uaqibv产生格局uacqjvM在输入串w上的起始格局是q0w，表示机器处于起始状态q0。在接受格局里，状态为qaccept；在拒绝格局里，状态是qreject。接受和拒绝状态都是停机状态,它们将不再产生新格局。TMM接受输入w，如果存在格局序列C1,C2,…,Ck，那么使得：〔1〕C1是M在输入w上的起始格局；〔2〕每个Ci产生Ci+1(i=1,2,…,k-1)；〔3〕Ck是接受格局。TMM接受的字符串的全体称为M的语言，记为L(M)。定义2如果有图灵机识别一个语言，那么称该语言是图灵机可识别的。在输入w上运行一个图灵机TM时，可能出现三种结果：接受、拒绝或循环。这里的循环可能是简单的，也可能是复杂的，但都不会导致停机状态。对于一个输入，图灵机有两种方式不接受它：一是指拒绝，另一种是指进入循环。有时，很难区分机器是进入了循环，还是需要长时间运行。对所有输入，称总能停机的图灵机为判定器，也称识别某个语言的判定器判定该语言。定义3称一个语言是图灵可判定的，如果有图灵机可判定它。例2设计TMM2，它识别的语言是由0组成D的、长度为2的方幂的字符串，即M2判定语言B={02n|n≥0}。M2=“对于输入串w：№1从串的起始位开始，扫描整个带子，隔一个格子消去一个0；№2如果在第一步之后，带子上只剩下惟一的一个0，那么接受；№3如果在第一步之后，带子上包含不止一个0，并且0的个数是奇数，那么拒绝；№4让读写头返回带子的最左端；№5返回第一步;〞TMM2=(Q,Σ,Γ,δ,q1,qaccept,qreject)的形式描述：Q={q1,q2,q3,q4,q5,qaccept,qreject}∧Σ={0}∧Γ={0,×,］}例1给出了判定语言A={w＃w|w∈{0,1}*}的TMM1。TMM1=(Q,Σ,Γ,δ,q1,qaccept,qreject)的形式描述：Q={q1,q2,q3,q4,q5,qaccept,qreject}∧Σ={0,1,＃}∧Γ={0,1,＃,×,］}例3设计TMM3,M3判定语言C={aibjck|i*j=k;i,j,k≥1}。M3=“对于输入串w：№1从左向右扫描输入，确认输入具有形式a*b*c*;假设不然，拒绝；№2让读写头回到输入串的最左端；№3消去一个a，并向右扫描直到b出现;在b与c之间来回移动，成对消去b与c，直到消去所有的b;№4如果还有a未消去，那么恢复所有已消去的b，再重复第三步;如果所有的a都已被消去，那么检查所有的c是否都已被消去;如果是，那么接受，否那么拒绝。〞

例4(元素区别问题)设有语言E={＃x1＃x2＃…＃xn|xi,xj∈{0,1}*,i≠jxi≠xj}，设计TMM4的任务是：若E中＃号隔开的字符串均不相同，则接受。M4的工作方式为：将x1与x2,x3,…,xn进行比较，若有一次相同则拒绝;将x2与x3,x4,…,xn比较,若有一次相同则拒绝，依次类推。TMM4的非形式描述：M4=“对于输入w：№1找最左端的带符号，如果此带符号是空白符，则接受；如果是＃，则在其上做个标记（变＃为＃，“＃”应事先设进带字母表Γ），并进行下一步，否则，拒绝；№2向左扫描下一个＃，并在其上做第二个标记，如果在遇到空白符之前，没有遇到＃，那么只有x1，因此接受；№3通过来回移动，比较做了标记的＃号右边的两个字符串，如果相等那么拒绝；№4对两个有标记的＃，把右边的记号向右移到下一个＃上;如果碰到空白字符之前没有遇到＃，那么将左边的标记右移到下一个＃上，也将右边标记移到后面的＃上;这时右边标记假设找不到＃，那么所有字符串均已比较过，因而接受；№5转№3。〞定义4(多带图灵机)一个多带图灵机是一个7元组M={Q,Σ,Γ,δ,q0,qaccept,qreject)，其中，δ为转移函数，设k为带的条数，那么δ:Q×Γk→Q×Γk×{L,R}k定义为δ(qi,a1,a2,…,ak)=(qj,b1,b2,…,bk,d1,d2,…,dk)表达式意指：假设机器处于状态qi，读写头1到k所指符号分别为a1,a2,…,ak，那么转移到状态qj，写出符号b1,b2,…,bk,并按di=R或L(i=1,2,…,k)所指方向移动每个读写头。多带图灵机看上去比普通〔单带〕图灵机能力强，但可证明二者是等价的。

命题1每个多带图灵机都有一个与之等价的单带图灵机。证明思路是通过用单带图灵机S模拟多带图灵机M，将一个多带TMM,转换为与之等价的单带TMS。具体作法是对M的k条带上的信息，S将其都存储在一条带上，并对其模拟k条带的效果。S可用＃号作定界符，以分隔k条带的内容，S还要记录读写头的地址，这可利用对多带TMM的读写头所指位置的元素加标记的方法解决。S将自己的带视为虚拟带，并把有标记符处视为虚拟读写头所指位置。图8.5.3用1条带表示3条带

S=“对于输入w=w1w2…wn：№1S在自己的虚拟带子上放入＃w1w2…wn＃＃＃…＃这种格式表示了M的全部k条带子的内容；№2为了模拟一步移动，S在其带上从标记左端点的第一个＃开始扫描，一直扫描到标记右端点的第k+1个＃，其目的旨在确定虚拟读写头下的符号；№3然后S进行第二次扫描，并根据m的转移函数指示的运行方式更新带子。”任何时候，只要S将某个虚拟读写头向右移动到空白区域〔即以前没有读过的区域〕，S就在这个带方格上写下空白符，并将这个带方格到最右端的带方格中的内容都向右移动一个单位，然后再像以前一样继续模拟。单带图灵机是多带图灵机当k=1时的特殊情况。推论一个语言是图灵机可识别的，当且仅当有多带图灵机识别它。证明略。定义5(确定图灵机DTM)假设一图灵机的转移函数δ:Q×Γk→Q×Γk×{R,L}k为一单值映射，即在图灵机运行的每一步，都可根据当前状态，惟一地确定后继状态，那么称该图灵机为确定图灵机，记为DTM。定义6(非确定图灵机NDTM)假设一图灵机的转移函数δ:Q×Γk→Q×Γk×{R,L}k为一多值映射，即在图灵机运行的某些步骤上，对于当前状态，需要在多个后继状态下选择一种，那么称该图灵机为非确定图灵机，记为NDTM。命题2每个非确定图灵机都有一个与之等价确实定图灵机。证明略。推论1一个语言是图灵机可识别的，当且仅当有非确定图灵机识别它。图灵机的输入总是一个串。如果想以一个不是串的对象作为输入，必须先将该对象表示成串。串能很容易地表示多项式、图、文法、自动机及这些对象的任意组合。可以设计一个图灵机对这些表示进行适当的解码，使之被解释为所希望的对象。对象O的编码表示〔即串〕的记号是<O>。如果有多个对象O1,O2,…,Ok，它们的编码是串，记为<O1,O2,…,Ok>，可用多种合理的方式编码。原因是图灵机总能将一种编码翻译成另一种。定义7对于长度为n的输入：〔1〕存在一个确定图灵机M，M执行T(n)步后停机，称函数T(n)是时间可构造的；〔2〕存在一个确定图灵机M，M在某一条带上第S(n)个单元上打印1个特殊的标识，且任一带上使用的单元数小于等于S(n)，称S(n)是空间可构造的。n2，2n，n!等都是时间〔空间〕可构造函数。命题3设M是时间复杂性为T(n)的不确定图灵机，那么存在常数C>1和确定图灵机M′，使得L(M)=L(M′)，且M′的时间复杂性为O(CT(n))。证明不确定图灵机M的δ是多值映射，设对每个k+1之组，δ的值不超过d个。对于输入x，考虑M在x上操作，任一个瞬时格式的后继有多个，数目不超过d;依δ的定义，可构造一棵树T，树根是初始瞬时格式，后继瞬时格式是前一格式的子节点。对树T的每一层给一顶点的子节点自左向右以一个序，并给树中每个节点一个标号：根节点标1，假设某一分支点的编号为(n1,n2,…,nt)，该分支点第t个儿子的编号为(n1,n2,…,nt,t)。每个节点都对应着A={1,2,…,d}上一个序列。因M的时间复杂度为T(n)，假设M接受长为n的输入串，那么一定存在长度不超过T(n)的瞬时格式序列，它对应于T中一条由根开始的长度小于等于T(n)的路。T中这种路总共不超过(d+1)T(n)条。对于长度为n的任一串x，构造M′模拟M的行为。M′依词典序生成A上所有长度不超过T(n)的串。对已生成的A上任一串w，相应的w在T中有瞬时格式序列σw，确定图灵机M′在σw上模拟M，假设在σw上M接受输入串x，那么M′接受x。假设对w，在T中不存在瞬时格式序列σw，或M不接受x，那么M′就选下一个A上的串。产生一个串w要消耗O(T(n))时间。模拟M的动作要消耗O(T(n))时间，因A上串的总数不超过(d+1)T(n)，因而M′模拟M的总消耗时间为O(T(n)(d+1)T(n))。因此，存在常数C>1，模拟时间至多为O(CT(n))。8.5.2几个特殊语言类定义8(P类语言与NP类语言)

P={L|存在DTMM和多项式P(n)，使得M的时间复杂性为P(n)且L(M)=L};NP={L|存在NDTMM和多项式P(n)，使得M的时间复杂性为P(n)+且L(M)=L}。称P与NP分别为多项式时间复杂性囿界下被确定与不确定图灵机所接受的语言类。一个问题属于P或属于NP，当且仅当该问题的一种编码语言属于P或属于