计算复杂性的概念

11网络优化第1章概论NetworkOptimization1.4计算复杂性的概念2定义1.3所谓组合(最)优化(CombinatorialOptimization)又称离散优化（DiscreteOptimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：优化问题三要素:(Min,f,F)或(Max,f,F)min()s.t.()0,,fxgxxD其中D表示有限个点组成的集合(定义域),f为目标函数,F={x|xD,g(x)0}为可行域1.4.1组合优化问题1、定义3给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：D={0,1}n1maxniiicx1..niiistaxb{0,1},1,...,.ixin2、例子例1.70-1背包问题(knapsackproblem)4一个商人到n城市推销商品，两个城市之间的距离为dij，如何选择一条道路使得商人每个城市走一遍之后回到起点，且所走的路径最短？其数学模型描述为：minijijijdx1..1,1,2,,nijjstxin{0,1},,1,2,,,.ijxijnij例1.8旅行商问题(TSP)11,1,2,,nijixjn,||1,2||2,{1,2,,}nijijSxSSnSnD={0,1}n×(n-1)对称的TSP问题：ijjidd；否则，称为不对称的TSP.5例1.9整数线性规划(IntegerLinearProgramming)(ILP).mincxTstAxb..xxZn0,•我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).•ILP中系数是有理数时，都可以处理成整数的情况。6以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，物品的尺寸为wj，如何使所用的箱子个数最少?说明：许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁，故，大量的组合优化问题是通过文字语言叙述的。例1.10装箱问题(BinPacking)71.4.2多项式时间算法对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？完全枚举法可以求得最优解,但枚举时间有时不可能接受ATSP:(n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+102.65e+22(秒)即2.65e+22/(365*24*60*60)8.4e+13(年)8问题（Problem）：是需要回答的一般性提问，通常含有若干个满足一定条件的参数.实例(instance)：问题中的参数赋予了具体值的例子。一、问题与实例的定义：问题通过下面的描述给定：（1）描述所有参数的特性（2）描述答案所满足的条件.问题实例TSP问题中各参数:100个城市，城市间距离已知.背包问题问题中各参数:4个物品，大小分别为4,3,2,2.价值分别为8,7,5,7.包的大小为6.整数线性规划问题中的n,A,b,c已知.9构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例。衡量一个算法的好坏，通常由以下两个要素的关系来衡量：(1)C(I)：求解实例I的计算时间，即算法中的加、减、乘、除和比较等基本运算的总次；(2)d(I)：实例I的输入规模/长度，即实例I在计算机计算时的二进制输入数据的大小.输入长度/规模的计算方法：对于一个正整数x，其二进制为：1110222ssssxaaaa一般用二进制系数110(,,,,)ssaaaa来表示数x，其中0,{0,1}siaa。二、多项式时间算法10正整数x输入长度的估计：由不等式22loglog112222xxssx，可得：22log1log1xsx.故，数x的二进制输入的位数为21logsx或2log1x。说明:整数0和1的二进制位数均为1，规定2log00后，此二进制表示方法和输入长度的结论可推广到非负整数。对实例I的(I)C和(I)d一般是进行粗略估计，给出一个上限。它们的关系通常用符号()=(())=((()))CIfdIOgdI来表示，其含义为：存在一个函数()gx和一个非负常数使得：()(())CIgdI，函数()gx的特性决定了计算总次数的性能，即计算的复杂性。11定义1.4假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间成立，则称该算法为解决该问题的多项式(时间)算法(Polynomialtimealgorithm).输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢。()(())CIgLI（其中为常数）当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或指数(时间)算法(Exponentialtimealgorithm)注：在定义中，要求对该问题的任意一个实例均成立()(())CIgdI，这种分析方法称为最坏性能分析（Worst-CaseAnalysis）.12例1：上述的非对称ATSP问题，设城市数为n，第1个城市为始终点。2(1)log||,LnnP{|0}ijijPdd其中假设每一个数据(距离)的绝对值都有上界K，则：说明：输入长度不超过n的一个多项式函数。22(1)log||(1)(1log)LnnPnnK（1）输入数据为城市之间的距离(,1,2,,;)ijdijnij。对任意一个ijd，其二进制输入长度不超过2log||1ijd，于是输入的总长度不超过：13所以，枚举算法对TSP来说，不是一个多项式时间的算法。（2）枚举算法的计算总次数为：①计算一条路径2(1,,,)nii的长度，其基本运算为两两城市间距离的n个求和；②总共有(-1)!n条路径需要计算。故枚举算法的基本计算总次数为:(-1)!=!nnn，是n的阶乘函数，比指数函数增加的速度还快。TSP问题至今没有找到多项式时间算法,但尚未证明其不存在TSP是否存在多项式时间算法?----这是21世纪数学和计算机科学的挑战性问题之一14例2：构造算法将n个自然数从小到大排列起来算法输入自然数a(1),a(2),…,a(n).for(i=1;in;i++)for(j=i+1;j=n;j++)if(a(i)a(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)/215三、强多项式算法和伪多项式算法算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中n,m)问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(StronglyPolynomial)时间算法.1122()(,,log)()(())LIgmnKCIgLI33()(,,log)CIgmnK一般来说，伪多项式算法并不是多项式算法.16定义1.5对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).同样道理,可以定义强多项式问题,伪多项式问题等.1.4.3多项式问题17布置作业目的掌握图与网络的基本概念掌握算法复杂性的基本概念内容《网络优化》第18页5;7(星形表示法);9;11;