网络优化-第1章+概论.ppt

1,网络优化,第1章概论（第1讲）,NetworkOptimization,清华大学数学科学系谢金星办公室：理科楼2206#（电话Email:jxie,清华大学数学科学系研究生专业课（课号：70420133）,2,网络优化简介,网络：网络社会-计算机信息网络？,电话通信网络运输服务网络能源和物质分派网络人际关系网络等等,网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益,3,网络优化简介,网络：数学模型、数学结构-图,从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为（最）优化(Optimization)问题,运筹学（OperationsResearch-OR）的一个分支,网络优化就是研究与（赋权）图有关的最优化问题,4,应用数学,（纯粹）数学,分析,代数,应用数学基础理论,数学-其他学科交叉,数学应用(经济-军事-社会),.,数学学科的另一种分类,学科门类：理学,一级学科：数学,二级学科,.,几何,注国外一般认为：统计学、运筹学不属于数学学科(商学院、工业工程),注还有一种观点：数学不属于自然科学（理学），而是属于思维科学（如哲学）,网络优化：计算机科学系、电子工程系等,5,OperationsResearchandManagementScience(OR/MS)Theprofessionaldisciplinesthatdealwiththeapplicationofinformationtechnologyforinformeddecision-makingProviderationalbasesfordecisionmakingbyseekingtounderstandandstructurecomplexsituationsandtousethisunderstandingtopredictsystembehaviorandimprovesystemperformance.Muchofthisworkisdoneusinganalyticalandnumericaltechniquestodevelopandmanipulatemathematicalandcomputermodelsoforganizationalsystemscomposedofpeople,machines,andprocedures.Thefieldiscloselyrelatedtoseveralotherfieldsinthedecisionsciences-appliedmathematics,computerscience,economics,industrialengineering,andsystemsengineering.,From/Join/Orms.html,6,运筹学与其他相关学科的关系,广义：管理科学/决策科学(MS/DS)、系统科学/工程(SS/SE)、工业工程(IE)与工程管理(EM)、运作管理(OM)狭义：运筹数学(MathematicsofOR)规划论（最优化）对策论排队论仿真（Simulation,模拟）,管理科学的三大基础：数学；经济学；行为科学成思危,7,运筹数学（MathematicsofOR）,最优化(数学规划)连续优化(数学规划)：数学规划（线性规划、非线性规划）、非光滑优化、全局优化、锥优化等离散优化：网络优化、组合优化、整数规划等不确定规划：随机规划、模糊规划等,网络优化也是计算机科学的入门课程之一,8,OptimizationTree,/otc/Guide/OptWeb/,张立平,刘宝碇,邢文训谢金星,白峰杉,9,OR/MS建模的一般步骤,模型准备,模型假设,模型构成,模型求解,模型分析,模型检验,模型应用,AppliedMathematicsMathematicalModeling:Motivation,Formulation,Solution,Validation,“源”远“流”长,林家翘(C.C.Lin),数据准备,实际问题,10,网络优化简介,教材：谢金星、邢文训，网络优化，清华大学出版社，2000年8月；2003年9月。参考书：Ahuja,R.K.,MagnantiT.L.,OrlinJ.B.NetworkFlows:Theory,Algorithms,andApplications.PrenticeHall,1993:EnglewoodCliffs,NewJersey.教学资源：网络学堂;本人主页,成绩：作业-50%左右考试-50%左右如何学习？认真看书、完成习题(有些习题难度较大)助教:王振波(wzb01),内容：网络优化模型、算法及其复杂性,对象：数学、计算机科学、管理科学、工程科学等,11,例1.1公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,1.1网络优化问题的例子,例1.2最短路问题（SPP-ShortestPathProblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.,12,例1.3运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？,1.1网络优化问题的例子,例1.4指派问题(AssignmentProblem)一家公司经理准备安排N名员工去完成N项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的.如何分配工作方案可以使总回报最大？,13,例1.5中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何为他(她)设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.,1.1网络优化问题的例子,例1.6旅行商问题/货郎（担）问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.,14,1.1网络优化问题的例子,例稳定婚配问题(StableMarriageProblem)假设有n个男人和n个女人,每人都希望从n个异性中选择一位自己的配偶.假设每人都对n个异性根据自己的偏好进行了排序,以此作为选择配偶的基础.当给定一种婚配方案(即给每人指定一个配偶)后,如果存在一个男人和一个女人不是互为配偶,但该男人喜欢该女人胜过其配偶,且该女人喜欢该男人也胜过其配偶,则该婚配方案称为不稳定的.安排稳定的婚配方案的问题称为稳定婚配问题。,15,1.1网络优化问题的例子,网络优化或网络流（NetworkFlows)或网络规划（NetworkProgramming)与图论课程的联系与区别,特点：（1）与图形有关，或易于用图形方式表示（2）优化问题：从若干可能的安排或方案中寻求某种意义下的最优安排或方案,16,1.2图与网络定义,定义1.1一个有向图(DirectedGraph或Digraph)G是由一个非空有限集合V(G)和V(G)中某些元素的有序对集合A(G)构成的二元组，记为有向图G=(V(G)，A(G).其中V(G)称为图G的顶点集(VertexSet)或节点集(NodeSet)，V(G)中的每一个元素称为该图的一个顶点(Vertex)或节点(Node)；A(G)称为图G的弧集(ArcSet)，A(G)中的每一个元素(即V(G)中某两个元素的有序对)称为该图的一条从到的弧(Arc).在不引起混淆的情况下，记号V(G)和A(G)中也可以省略G，即分别记顶点集、弧集为V和A，而记有向图G=（V，A）.如果对有向图G中的每条弧赋予一个或多个实数，得到的有向图称为赋权有向图或有向网络,简称为网络(Network).,17,1.2图与网络例,图G=(V，A)，其中顶点集V=弧集A=弧,18,弧的端点(Endpoint)，尾(Tail)，头(Head)；顶点相邻(Adjacent)，邻居(Neighbor)；弧与顶点关联(Incident)，出弧(OutgoingArc)，入弧(IncomingArc)；弧相邻(Adjacent)；环(Loop)，孤立点(IsolatedVertex)；图的阶(Order)顶点的度（Degree），出度，入度，奇点，偶点,没有环、且没有多重弧的图称为简单图(SimpleGraph),1.2图与网络基本概念,19,1.2图与网络子图,称为G的子图(Subgraph),图的支撑子图(SpanningSubgraph，又称生成子图)是包含G的所有顶点的子图,（顶点、弧）导出子图(InducedSubgraph),图的导出子图是唯一的；图的支撑子图一般是不唯一的,有向图中的途径(Walk)是该图的一些顶点和弧所组成的子图，这些顶点与弧可以交错排列成点弧序列其中或,如果该序列中的所有弧都指向同一方向，即，则该途径称为有向途径(DirectedWalk).,20,1.2图与网络路、圈,有向图中的路(Path)是该图的不包含重复顶点的途径.,方向与路的起点到终点的方向一致的弧称为路的前向弧(ForwardArc)；否则称为后向弧或反向弧(BackwardArc).P,P+,P-,有向图中的有向路(DirectedPath)是该图的不包含重复顶点的有向途径，即不包含反向弧的路.,有向图的圈(Cycle)是起点和终点重合，且不含其他重复顶点的途径.C,C+,C-,有向图中的有向圈(DirectedCycle)是该图的不包含反向弧的圈.,不包含有向圈的图称为无圈图(AcyclicGraph).,21,1.2图与网络路、圈,对于有向图中的两个顶点，如果在图中至少存在一条路把它们连接起来，则称这两个顶点是连通的(Connected).如果图中任意两个顶点都是连通的，则称该图为连通的(Connected)；否则称为不连通的(Disconnected).,不连通图可以分解成一些连通分支的并，而连通图只有一个连通分支.所谓连通分支(Component)，就是图中的极大连通子图。,如果有向图中从任意一个顶点出发，都存在至少一条有向路到达任意另一个顶点，则称该图为强连通的(StronglyConnected).同样可以类似地定义强连通分支.,若，则称两个端点分别位于S，T的弧为一个割（cut），记为S，T=,22,1.2图与网络无向图,定义1.2一个无向图(UndirectedGraph)G是由一个非空有限集合V和V中某些元素的无序对集合E构成的，即G=(V，E).其中V=V(G)仍称为图G的顶点集(VertexSet)或节点集(NodeSet)，V中的每一个元素称为该图的一个顶点(Vertex)或节点(Node)；E=E(G)=通常称为图G的边集合(EdgeSet)，E中的每一个元素(即V中某两个元素的无序对)称为该图的一条边(Edge).边上赋权的无向图称为赋权无向图或无向网络(UndirectedNetwork).,本课程中，在不引起混淆的情况下，有时将有向图和无向图都简称为图(Graph)；也不再对弧和边的概念作严格区分。并且，对图和网络的概念也不再作严格区分。,23,1.2图与网络两种特殊的图,若图G=(V，E)的顶点集V可以表示成两个互不相交的非空子集S，T的并集，且使得G中每一条边的一个端点在S中，另一端点在T中，则称G为二部图/二分图(BibartiteGraph).当|S|=p，|T|=q，且S与T中任意两对顶点都相邻时，称G为完全二部图，记为Kp,q.,类似地，也可以定义有向的完全图和有向的完全二部图.,Kn的弧的数量为n(n-1)/2,若无向图G的任意两个顶点间有且只有一条边相连，则称其为完全图(CompleteGraph).n阶完全图记为Kn.,Kp,q的弧的数量为pq,24,1.3图与网络的数据结构,1.3.1邻接矩阵(AdjacencyMatrix)表示法,图G=(V，A)的邻接矩阵C是如下定义的：C是一个的0-1矩阵，即,每行元素之和正好是对应顶点的出度，每列元素之和正好是对应顶点的入度.,G=(V，A)是一个简单有向图|V|=n，|A|=m,在邻接矩阵的所有元素中，只有m个为非零元.,25,1.3图与网络的数据结构,1.3.1邻接矩阵表示法,对于网络中的权，也可以用类似邻接矩阵的矩阵表示.只是此时一条弧所对应的元素不再是1，而是相应的权而已.如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权.,26,1.3图与网络的数据结构,1.3.2关联矩阵(IncidenceMatrix)表示法,图G=(V，A)的邻接矩阵C是如下定义的：C是一个的矩阵，即,每行元素1的个数正好是对应顶点的出度，每行元素-1的个数正好是对应顶点的入度.,G=(V，A)是一个简单有向图|V|=n，|A|=m,在关联矩阵的所有元素中，只有2m个为非零元.,27,1.3图与网络的数据结构,1.3.2关联矩阵表示法,如果网络中每条弧赋有一个权，我们可以把关联矩阵增加一行,把每一条弧所对应的权存贮在增加的行中.如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存贮在增加的行中.,28,1.3图与网络的数据结构,1.3.3弧表（ArcList)表示法,所谓图的弧表,也就是图的弧集合中的所有有序对.弧表表示法直接列出所有弧的起点和终点.,G=(V，A)是一个简单有向图|V|=n，|A|=m,特点:共需2m个存贮单元，当网络比较稀疏时比较方便.,29,1.3图与网络的数据结构,1.3.3弧表表示法,30,1.3图与网络的数据结构,G=(V，A)是一个简单有向图|V|=n，|A|=m,1.3.4邻接表(AdjacencyLists)表示法,图的邻接表是图的所有节点的邻接表的集合;而对每个节点，它的邻接表就是它的所有出弧.,对于有向图G=（V，A），一般用A（i）表示节点i的邻接表，即节点i的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）.这种记法我们在本课程后面将会经常用到.,31,1.3图与网络的数据结构,1.3.4邻接表表示法,单向链表(指针数组),A(1)=2,3,A(2)=4,A(3)=2,A(4)=3,5,A(5)=3,4,32,1.3图与网络的数据结构,1.3.5星形（Star）表示法,前向星形(ForwardStar)表示法,节点对应的出弧的起始地址编号数组（记为point）为,记录弧信息的数组为,33,1.3图与网络的数据结构,1.3.5星形（Star）表示法,反向星形(ReverseStar)表示法,节点对应的入弧的起始地址编号数组（记为rpoint）为,记录弧信息的数组为,34,1.3图与网络的数据结构,几点说明,（1）星形表示法和邻接表方法常用.星形表示法的优点是占用的存贮空间较少;邻接表方法增加或删除一条弧所需的计算工作量很少,（2）当网络不是简单图，而是具有平行弧(即多重弧)时，邻接矩阵法是不能采用的.其他方法则可以推广到可以处理平行弧的情形.,（3）无向图处理类似.如无向图的关联矩阵只含有元素0和+1.在邻接表和星形表示中，每条弧会被存贮两次;反向星形表示显然是没有必要的，等等.,35,1.4计算复杂性的概念,定义1.3所谓组合(最)优化(CombinatorialOptimization)又称离散优化（DiscreteOptimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：,优化问题三要素:(Min,f,F)或(Max,f,F),其中D表示有限个点组成的集合(定义域),f为目标函数,F=x|xD,g(x)0为可行域,1.4.1组合优化定义,36,1.4计算复杂性的概念,1.4.1组合优化例,例1.70-1背包问题(knapsackproblem)给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：,D=0,1n,例1.10装箱问题(BinPacking)以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，如何使所用的箱子个数最少?,37,1.4计算复杂性的概念,1.4.1组合优化例,例1.9整数线性规划(IntegerLinearProgramming),(IP).,我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁,38,1.4计算复杂性的概念,1.4.2多项式时间算法,对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？,完全枚举法可以求得最优解,但枚举时间有时不可能接受,ATSP:(n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+102.65e+22(秒)即2.65e+22/(365*24*60*60)8.4e+13(年),39,1.4计算复杂性的概念,1.4.2多项式时间算法,构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例,问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件.,问题中的参数赋予了具体值的例子称为实例(instance).,衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量.计算模型,C(I)=f(d(I):该函数关系称为算法的计算复杂性（度）,40,1.4计算复杂性的概念,1.4.2多项式时间算法,对于一个正整数x，二进制表示是以,如ATSP:二进制输入长度总量不超过(不考虑正负号、分隔符等),的系数来表示，其中，,x的二进制数的位数不超过,假设每一个数据(距离)的绝对值都有上界K,输入长度是n的多项式函数所以网络优化中常用n,m等表示输入规模,41,1.4计算复杂性的概念,1.4.2多项式时间算法,例构造算法将n个自然数从小到大排列起来,算法输入自然数a(1),a(2),a(n).for(i=1;ia(j)k=a(i);a(i)=a(j);a(j)=k;,即该算法的计算复杂性（度）为O(n2),基本运算的总次数(最坏情形）：2n(n-1)=O(n2)比较：（n-1)+(n-2)+1=n(n-1)/2赋值：3(n-1)+(n-2)+1=3n(n-1)/2,42,1.4计算复杂性的概念,定义1.4假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间,成立，则称该算法为解决该问题的多项式(时间)算法(Polynomialtimealgorithm).当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或指数(时间)算法(Exponentialtimealgorithm),输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.,1.4.2多项式时间算法,注：上面定义中，要求对该问题的任意一个实例均成立，这种分析方法称为最坏性能分析（Worst-CaseAnalysis）,43,1.4计算复杂性的概念,1.4.2多项式时间算法,44,1.4计算复杂性的概念,1.4.2多项式时间算法,算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中n,m),以及问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系,如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.,实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.,特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(StronglyPolynomial)时间算法.,一般来说，伪多项式算法并不是多项式算法.,45,1.4计算复杂性的概念,TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存在,定义1.5对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).,同样道理,可以定义强多项式问题,伪多项式问题等.,TSP是否存在多项式时间算法?-这是21世纪数学和计算机科学的挑战性问题之一,1.4.3多项式问题,46,布置作业,目的,掌握图与网络的基本概念掌握算法复杂性的基本概念,内容,网络优化第49-51页5;9;14;16,更正(第1次印刷版):第14题“”改为,47,网络优化,第1章概论(第2讲),NetworkOptimization,清华大学数学科学系谢金星办公室：理科楼2206#（电话Email:jxie,1.5NP,NPC和NP-hard概念(计算复杂性理论）,48,运筹学的ABC-A2B2C2（至少是组合优化、理论计算机科学的ABC）,ApproximationAlgorithm(近似算法)；HeuristicBranchandBound（分枝定界）ComputationalComplexity（计算复杂性）,口莫开，开口常说错。理论在监督，众目睽睽难逃脱。,计算复杂性理论的“Bible”GareyMR.andJohnson.DS,Computersandintractability:aguidetothetheoryofNP-completeness.SanFrancisco:.W.H.FreemanandCo.,1979(中译本:计算机和难解性：NP-C理论导论.张立昂等译,科学出版社，1987),49,1.5.1问题、实例与输入规模,评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入规模的关系：,比多项式问题类可能更广泛的一个问题类是非确定多项式(NondeterministicPolynomial，简记NP)问题类,存在多项式算法的问题集合：多项式问题类（P）,存在多项式函数g(x)满足上式时，算法为多项式算法,NP类是通过判定问题引入的。,50,对任何一个优化问题，可以考虑其三种形式：最优化形式（原形：最优解）计值形式（最优值）判定形式（上界）,定义1.6如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题(Decision/recognition/feasibilityproblem).称有肯定答案的实例为“是”实例(yes-instance).称答案为“否”的实例为“否”实例或非“是”实例(no-instance).,1.5.2判定问题-定义,例1.13线性规划问题(LP)的判定形式LP判定问题：给定一个实数值z，(LP)是否有可行解使其目标值不超过z？即：给定z，是否有?,难度降低,就有效算法的存在性而言，通常认为三种形式等价！,51,文字集,例1.15适定性问题(Satisfiabilityproblem)在逻辑运算中，布尔变量x的取值只有两个：“真”(1)和“假”(0)，逻辑运算有“或（+）”，“与（）”和“非（）.,1.5.2判定问题-例,存在真值分配的表达式称为适定的(可满足的),文字集的任意一个子集中各元素（布尔变量）的“或”运算组成一个句子,多个句子的“与”运算组成一个表达式，如,适定性问题：给定布尔表达式，（SAT）是适定的吗？,52,1.5.2判定问题-例,例1.16三精确覆盖(3-ExactCovering：X3C)已知的n个子集构成的子集族，其中每个子集包含S中三个元素，F中是否存在m个子集，使得？若m个子集满足上式，则称这m个子集精确覆盖S.,53,定义1.7若存在一个多项式函数g(x)和一个验证算法H，对一类判定问题A的任何一个“是”实例I，都存在一个字符串S是I的可行解，满足其输入长度d(S)不超过g(d(I)，其中d(I)为I的输入长度，且算法H验证S为实例I的可行解的计算时间f(H)不超过g(d(I)，则称判定问题A是非确定多项式的。,考虑将求解判定问题的算法分为两个阶段：（1）猜测阶段：求出或猜测该问题的一个解（2）检查或验证阶段：一旦解已经选定，将猜测的解作为输入，验证此解是否为该实例“是”的回答.我们称实例“是”回答的解为实例的可行解，否则称为不可行解.,所有非确定多项式问题的集合用NP表示.,1.5.3非确定多项式问题类(NP)定义,构造字符串（解）的过程及验证算法H一起构成一个算法，称为非确定多项式（时间）算法。,54,所以，可以从讨论基本可行解的性质入手,整系数问题等价于有理系数问题,1.5.3非确定多项式问题类(NP)例,例1.17整系数（或有理系数）的LP判定问题属于NP.,其实，LPP，所以LPNP.下面考虑通过定义来说明LPNP,分析与思考：(注意：第1次印刷版教材上的证明可能有漏洞),（不）等式组有可行解，等价于它有基本可行解,LP判定问题等价于验证如下（不）等式组的可行解问题因此可以不考虑目标函数问题，仍记为,55,1.5.3非确定多项式问题类(NP)例,引理1.1LP问题的约束的基本可行解的各分量值有界，其二进制字符串表达式的输入长度不超过,例1.17整系数（或有理系数）的LP判定问题属于NP.（续）,输入长度不超过,又，分量值不超过,56,验证时最多需(m+1)n个乘，(m+1)(n-1)个加或减，n+m+1个比较，共计,LP实例的输入长度d(I)满足,1.5.3非确定多项式问题类(NP)例,LP的一个基本可行解的输入长度不超过,例1.17整系数（或有理系数）的LP判定问题属于NP.（续）,对LP判定问题的一个“是”实例，上述约束组（等式和不等式组）一定存在一个基本可行解.当给定一个基本可行解x，只要验证是否满足？,取多项式函数g(x)=2x2，则满足定义，所以LPNP.,57,F中m个元素是S的一个精确三覆盖的充分必要条件为：相应的m个向量满足,集合S中共有3m个元素，子集族F中的每个子集合对应一个3m维向量：向量的3m个分量对应3m个元素，元素包含在对应子集中的分量为1，余下的为0.例如：S=，F中的一个元素，对应向量为=(1,1,0,0,0,1)，表示为一个字符串(110001).,1.5.3非确定多项式问题类(NP)例,按字符串向量问题，精确三覆盖“是”实例的任何一个解可以用长度为3m2的字符表示.验证是否可行解的算法最多需3m2个加法和3m个比较，算法的计算时间为3m2+3m.,例1.19三精确覆盖属于NP,三精确覆盖问题任何一个实例的输入长度d(I)3m.,选g(x)=x2/3+x，则定义条件满足，所以三精确覆盖属于NP.,58,1.5.3非确定多项式问题类(NP),问题A2的难度不低于问题A1,定义1.8给定问题A1和A2，若存在一个多项式算法满足：对A1的任何一个实例I1，算法将实例I1的输入转换为A2的一个实例I2的输入；这种转换过程使得实例I1和I2的解一一对应，即将实例I1的一个解x1的输入转换为实例I2的一个解x2的输入，且x1为I1的“是”答案x2是I2的一个“是”答案；则称A1问题多项式转换为A2问题，算法称为问题A1到问题A2的一个多项式转换（算法）(Transformation).,常用的研究方法-多项式转换(变换)、多项式归约(归结),若A1多项式转换为A2，且A2P，则A1P若A1多项式转换为A2，且A2NP，则A1NP,多项式转换(定义),59,进一步，该映射可以在SAT实例的输入长度mn的多项式时间内完成,SAT的一个实例是由n个逻辑变量和m个句子组成，输入长度是mn.,1.5.3非确定多项式问题类(NP)多项式转换,等价于一个整数（0-1）线性规划问题（目标可以任意）。,例1.20适定性问题多项式转换为整数（0-1）线性规划问题.,将“真”对应“1”，“假”对应“0”，令逻辑变量x对应整数0或1，对应1-x.含n个变量的句子(j=1,2,.,m)为“真”，对应下列不等式组有可行解：,适定性问题多项式转换为整数（0-1）线性规划（判定）问题,60,进一步，该映射可以在X3C实例的输入长度的多项式时间内完成,特殊0-1背包判定问题（本书后面简称0-1背包判定问题）:对给定的整数和b，是否存在1,2,.,n的子集B，使得?,例1.21三精确覆盖多项式转换为0-1背包判定问题,1.5.3非确定多项式问题类(NP)多项式转换,所以，三精确覆盖问题多项式转换为0-1背包判定问题,61,1.5.4NP完全问题类(NPC)-,定义1.9已知判定问题A1和A2，若存在多项式函数和，使得对A1的任何实例I，在多项式时间内构造A2的一个实例，其输入长度不超过，并对A2的任何一个算法H2，都存在问题A1的一个算法H1，使得H1算法调用H2算法且使得计算时间，其中fH1(x)和fH2(x)分别表示算法H1和H2的计算时间与实例输入长度x之间的关系，则称问题A1多项式归约为问题A2.,根据A2的算法H2，构造A1的算法H1的过程，即映射：H2H1称为从A1到A2的一个多项式归约(reduction).,多项式归约(定义),62,问题A2的难度不低于问题A1(注：第1次印刷版有误),若A1多项式归约为A2，且A2P，则A1P若A1多项式归约为A2，且A2NP，则A1NP,若A1多项式归约为A2，则当把H1对H2的一次调用当成一次基本运算时，H1是A1的多项式算法。,1.5.4NP完全问题类(NPC)-多项式归约,多项式转换是多项式归约的特例,归约映射可以如下构造：H1：STEP1用多项式转换将A1的实例转换为A2的实例STEP2用H2算法求解A2的实例,即多项式转换可以认为是只允许调用一次H2的多项式归约,63,1.5.4NP完全问题类(NPC)-多项式归约（例）,例1.22适定问题多项式归约为三精确覆盖问题,（证明较繁，略）课后自己看书体会证明技巧,64,定义1.10（1）对于判定问题A，若ANP且NP中的任何一个问题可在多项式时间内归约为A，则称A为NP完全问题(NP-Complete或NPC).可以表示为ANPC.,NPC和NP-hard两者的区别是:验证一个问题A是否为NP-hard无须判断A是否属于NP.根据定义可知NPCNPH.,当已知一个问题属于NPC或NPH时，如果再遇到一个新问题：（1）若已知问题多项式归约为新问题，则新问题属于NPH;,1.5.4NP完全问题类(NPC)定义,（2）对于判定问题A，若NP中的任何一个问题可在多项式时间归约为判定问题A，则称A为NP困难问题(NP-hard或NPH).可以表示为ANPH.,（2）若还可以验证新问题属于NP，则新问题属于NPC.,65,1.5.4NP完全问题类(NPC)证明,例1.23(Cook定理，1971）SATNPC.,前面已经证明SATNP，所以尚需证明：任何一个NP问题可以多项式归约为SAT,计算复杂性理论的奠基性工作之一：第一个被证明的NPC问题！是证明许多其他NPC问题的出发点,基本思想：若ANP，则A存在非多项式时间算法（猜测解、验证解）。对猜测解、验证解的过程进行分析，构造一个SAT问题！,（证明细节较繁，略）,66,1.5.4NP完全问题类(NPC)证明（例）,例1.24整数线性规划（ILP）的判定问题属于NPC,例1.20已证明适定问题多项式转换为0-1线性规划(ZOLP)的判定问题ZOLP判定问题属于NPH,与线性规划的判定问题属于NP的证明类似，可以证明：整数线性规划的判定问题属于NP,引理如果ILP有可行解，则它有一个可行解,推论：ZOLP多项式等价于ILP；ILP的判定问题属于NPC,易知：ZOLP的判定问题属于NPZOLP判定问题属于NPC,67,1.5.4NP完全问题类(NPC)证明（例）,例1.25三精确覆盖（X3C）属于NPC.,SAT多项式归约为X3C(例1.22),X3CNP（例1.19）,X3CNPC,例1.26（特殊）（0-1）背包判定问题属于NPC.,X3C多项式变换为背包判定问题（例1.21）,背包判定问题NP（易证）,背包判定问题NPC,68,1.5.4NP完全问题类(NPC)证明（例）,例1.27（集合）划分（PARTITION）问题是NPC.,PARTITION问题：给定整数，是否存在1,2,.,n的一个子集S，使得？,要证明PARTITIONNPC，尚需证明：,这是（特殊）（0-1）背包判定问题的一个特殊情况，包的容积背包判定问题NPPARTITIONNP,所有NP问题多项式转换/归约为集合划分问题，或：,某个NPC问题多项式转换/归约为集合划分问题,可以证明：背包问题多项式转换为集合划分问题,69,观察：,1.5.4NP完全问题类(NPC)证明（例）,例1.27PARTITION问题是NPC.（续）,这个映射满足“转换”定义的性质-转换的多项式性,证明：背包问题多项式转换为集合划分问题,给定0-1背包判定问题的任何一个实例构造集合划分问题的实例其中,这个映射满足“转换”定义的性质-解的一一对应性,70,1.5.4NP完全问题类(NPC)证明（例）,例1.27PARTITION问题是NPC.（续）,存在1,2,.,n的子集S，使得的充分必要条件是存在1,2,.,n+2的一个子集S使得.,于是存在1,2,.,n的子集S，使得即,71,1.5.4NP完全问题类(NPC)证明（例）,易证：装箱判定问题属于NP易证.,例1.28装箱(BP)判定问题是NPC.(注：第1次印刷版有漏洞),给定正整数K及n个物品，尺寸为(正整