《计算复杂性的概念ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算复杂性的概念ppt课件.ppt（17页珍藏版）》请在三一办公上搜索。
1、1,1,网 络 优 化,第 1 章 概 论,Network Optimization,1.4 计算复杂性的概念,2,定义1.3 所谓组合(最)优化(Combinatorial Optimization)又称离散优化（Discrete Optimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等. 这类问题可用数学模型描述为：,优化问题三要素: (Min, f, F)或 (Max, f, F),其中D表示有限个点组成的集合(定义域) , f为目标函数,F=x|xD, g(x)0为可行域,1.4.1 组合优化问题,1、定义,3,给定n个容积分别为ai，价值分别为ci的物
2、品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：,D= 0,1n,2、例子,例1.7 0-1背包问题(knapsack problem),4,一个商人到n城市推销商品，两个城市之间的距离为dij，如何选择一条道路使得商人每个城市走一遍之后回到起点，且所走的路径最短？其数学模型描述为：,例1.8 旅行商问题(TSP),D= 0,1n(n-1),5,例1.9 整数线性规划(Integer Linear Programming),(ILP) .,我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).ILP中系数是有理数时，都可以处理成整数的情况。,6,以尺寸
3、为1的箱子装进给定的n个尺寸不超过1的物品，物品的尺寸为wj ，如何使所用的箱子个数最少?,说明：许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁，故，大量的组合优化问题是通过文字语言叙述的。,例1.10 装箱问题(Bin Packing),7,1.4.2 多项式时间算法,对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解. 那么如何衡量算法的优劣、有效与无效呢？,完全枚举法可以求得最优解,但枚举时间有时不可能接受,ATSP: (n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30! / 10e+10
4、 2.65e+22 (秒)即 2.65e+22 / (365*24*60*60) 8.4e+13 (年),8,问题（Problem）：是需要回答的一般性提问，通常含有若干个满足一定条件的参数.,实例(instance)：问题中的参数赋予了具体值的例子。,一、问题与实例的定义：,问题通过下面的描述给定：（1）描述所有参数的特性 （2）描述答案所满足的条件.,9,构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例。,衡量一个算法的好坏，通常由以下两个要素的关系来衡量：(1) C(I)：求解实例I的计算时间，即算法中的加、减、乘、除和比较等基本运算的总次；(2) d(
5、I)：实例I的输入规模/长度，即实例I在计算机计算时的二进制输入数据的大小.,输入长度/规模的计算方法：,对于一个正整数x，其二进制为：,二、多项式时间算法,10,正整数 x 输入长度的估计：,11,定义1.4 假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间,成立，则称该算法为解决该问题的多项式(时间)算法(Polynomial time algorithm).,输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢。,当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法, 或指数(时间)算法(Expon
6、ential time algorithm),12,例1：上述的非对称ATSP问题，设城市数为n，第1个城市为始终点。,假设每一个数据(距离)的绝对值都有上界K，则：,说明：输入长度不超过n的一个多项式函数。,13,所以，枚举算法对TSP来说，不是一个多项式时间的算法。,TSP问题至今没有找到多项式时间算法,但尚未证明其不存在,TSP是否存在多项式时间算法? - 这是21世纪数学和计算机科学的挑战性问题之一,14,例2： 构造算法将n个自然数从小到大排列起来,算法 输入自然数a(1),a(2),a(n). for (i=1;ia(j) k=a(i);a(i)=a(j);a(j)=k;,即该算法
7、的计算复杂性（度）为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,15,三、强多项式算法和伪多项式算法,算法复杂性研究中:常将算法的计算时间表示为： 问题中的简单而典型的参数(如网络优化中n,m) 问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系,如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.,实际问题的输入规模/长度一定是
8、m,n和logK的一个多项式函数. 所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.,特别地, 如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）, 则称相应的算法为强多项式(Strongly Polynomial)时间算法.,一般来说，伪多项式算法并不是多项式算法.,16,定义1.5 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).,同样道理, 可以定义强多项式问题,伪多项式问题等.,1.4.3 多项式问题,17,布 置 作 业,目的,掌握图与网络的基本概念掌握算法复杂性的基本概念,内容,网络优化第18页 5; 7(星形表示法); 9; 11;,
